Should I publish a linear programming method despite my advisor's advice?
It is good to have publications. It is also good to follow the advice of your advisor for many reasons. Advisors have some say over your future, of course, so caution is indicated, at least, in every case. 

Note first that it has been many years since I was current with the algorithms of integer and linear programming. I suspect you are more current and your advisor more so, so be a bit careful in analyzing what I say below. 

The field in general is quite mature and the existing algorithms are very sophisticated. This was true 30 year ago, in fact. If the field has settled down since then there is little urgency in publishing now, as it is unlikely that you would be beaten to publication if you wait. You can make your advisor happy and, indeed, make progress on your main work without abandoning what you have. 

However, I think that a real advance should be questioned and you should be the one to question it. In particular, it may be that the reason for such good results is that your specific problem has characteristics that make this possible and your algorithm is nicely tailored to a special case. The possibility of that actually opens a door for your future work. If it is true, then knowing and describing that special case would be very useful, along with the algorithm. 

Also, if it is, indeed, a special case and you have tested only with the confines of this case then your results may not apply generally. It would be good to know, before you publish, whether this is true or not. And it would be especially good for you if you are the one to discover this. Fortunately, you can test your algorithm on a wider class of problems found in the literature. Thus, you can, perhaps, rule out the situation in which you have an anomaly. But your primary work should likely come first.