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.

I do not know, who is "right". Your contributions look quite impressive, though. So I am trying here to come up with arguments that might lead your supervisor to his/her decision. I deliberately omit politics and strategising.

• Your new method seems to work very well on your data. Does it work well enough on other kinds of data? It might be the nature of your data that allows for such speedups. While this would still be of interest for your actual narrow topic, it might not qualify as a broad solution.
• You use MatLab. This is probably the correct tool for you to use. This might be not the right tool for the general claim. (In other words, you'd be more or less desk-rejected if you present your MatLab solution to the specialists in linear programming. I am not sure, this would happen, but this totally might happen. Your supervisor probably knows more.) Thus, you'd need to re-write your code in C and/or in CUDA, with major and non-trivial investments towards memory alignment, pointer juggling, low-level optimisations, bandwidth optimisation, and what not. Writing fast low-level code takes a lot of time. It might be that this time is better spent doing other things.
• This is a part of a publication build-up for a thesis, right? The way your supervisor envisions your thesis, this linear programming thing has no place there. (This is quite strange, as typically, as long as it is related (and it is) and successful, it does not really matter.)
• Your supervisor has little expertise in that other field, does not feel like he/she can provide sufficient guidance, and would rather give up on that direction completely. This is also quite untypical, even if own expertise is lacking, one would typically be acquainted with colleagues, who are experts in that particular area. If a PhD candidate slowly wanders to that area, one might even think of a joint supervision.

So, to re-iterate. I do not know the rationale of your supervisor behind his/her decision, but it might be one of these. Do you have a good and informal enough relationship to simply ask why?

Loops can be slower in MATLAB, so using matrix operations to apply a particular algorithm to all the values is going to be faster than looping through the values and applying the algorithm individually. Since the number of calculations doesn't change, you haven't come up with anything scientifically novel, you have just found a way to use MATLAB more efficiently.

When I profiled your demo code in MATLAB, I noticed that the built-in fminbnd spent a lot of its time fetching a termination string and loading the optimisation settings structure. Maybe if this function was streamlined to the bare bones it would be much faster. The point is, these things are all just implementation details of same algorithm. Unless you are coming up with some previously unknown way of leveraging the CPU or GPU instruction set to speed up things I don't think the implementation is scientifically interesting.

So, your advisor is correct. You should focus on your primary research. The vectorisation has technical merit, speeding up things is a huge help (I spent hours and hours in front of MATLAB doing similar things, speed up roots for me please hehe). So I think you should properly document your code (no "I don't know what is going on here" easter eggs) and share it on File Exchange so that other people can take advantage of the tricks you have learnt. (GitHub as well, which has greater exposure)