Originally posted by: Jernej1

Hello!

As part of a course I am teaching, students must formulate certain LP problems and solve it using CPLEX. The attached LP file that was produced by one of the students should formulate the TSP problem on a (complete) graph with 8 vertices.

Some solvers give 2.638440000000e+00 as the solution to the lp. What is confusing is that CPLEX claims the solution to this lp is not feasible.

Can anyone explain what's going on? Is the lp formulation bogus?

Best,

Jernej

Originally posted by: max11

Hi Jernej,

It seems that you are using the MTZ formulation for the TSP. I suppose that in your lp file, variables x0 to x55 are the "arc" variables, while variables x56 to x62 are the "node" variables. Note

that the node variables are actually continuous variables, while in your lp file they are defined as general integer. Removing the integrality constraints on the node variables, CPLEX gives the solution 

reported in the attached file.

Regards

Originally posted by: Jernej1

Max11,

Thank you for your reply. You are correct, the formulation in question uses MTZ constraints. Do you actually know why other (not cplex) solvers actually find a solution in this scenario?

This is probably due to the fact that the different solvers have different implementations for LP readers (i.e., LP files are interpreted in slightly different ways by different venders).  In fact, the "Integers" section used in the LP file attached above is not even mentioned in the current CPLEX LP file format documentation (instead it mentions the "General" section).  I don't know the full history around this (it has been around for a very long time), but I think "Integers" is very old and even has slightly different behavior than "General" when interpreted and is maintained for backwards compatibility.  To gain insight into this you could read your file into memory and immediately write it out with the different solvers and see how they vary.

If you do what Ryan suggested you will see that CPLEX interprets the "Integers" section as "Binary". So all variables are binary and that explains why CPLEX claims the problem infeasible.