Another comment links to a paper explaining how to construct counter examples. To give an idea, here is a very simple example. x, y ∈ { 0, 1 } Constraints

Another comment links to a paper explaining how to construct counter examples. To give an idea, here is a very simple example. x, y ∈ { 0, 1 } Constraints 2x + y ≤ 2 -2x + y ≤ 0 Maximize x + 3y You can easily check that y = 0 must hold, for y = 1 one of the constraints gets violated whether you have x = 0 or x = 1. So the optimum is x = 1 and y = 0 with a value of 1. If we drop the integer constraint and have x, y ∈ [0, 1], then you will find that x = 0.5 and y = 1 also satisfies both constraints - together with many more pairs - and the optimum value is 3.5. To win the prize, you will have to do this with something like n⁶ variables and constraints where n is the number of cities in the problem. And I would guess that you might need maybe about 5 to 10 cities to construct a counter example, but that does not mean that you have to actually deal with all the constraint equations, the construction of the weights will do all the work.