The LP solver we use in our experiments is CPLEX. To solve the problems efficiently, we normally use the Barrier Optimizer with crossover off. Though this can solve problems much quicker than the Primal or Dual Simplex Optimizers, we encountered various numerical issues with it. Below are some observations to be aware of.
Observation 1
Using the Barrier Optimizer with crossover off, there is almost always a small difference between the optimal solution obtained by the solver and the real integer solution. Below is an example. We do not recommend changing the accuracy settings in order to “hide” these differences.
Observation 2
We designed a simple test problem with 9 nodes and costs between every two nodes being 100. Using CPLEX with the Barrier Optimizer with crossover off, this problem solved with an objective function result equal to 887.8040686226748. Clearly, the real optimal value should be 900. The gap looked to us to be more significant than could be attributed to numerical issues only. However, we then tried the following things without changing the model, and solvers always obtained the correct result. That validated that this is just another numerical issue. A summary of the things we tried is:
- We exported the model into an lp file format and an mps file format, respectively, and then let CPLEX read them directly to solve. The test reading the lp file resulted in the erroneous value of 887.8040686226748, while the one reading the mps file obtained the correct result.
- We simply switched the sequence of some constraints in the lp-format file, and then CPLEX obtained the correct result.
- We ran the Barrier Optimizer with crossover on. We observed from the log that the solver corrected to 900 in an intermediate step. But it eventually stopped with an ‘infeasibility’ message.
- We tried the Gurobi solver on the original .lp file and it obtained the correct result. (No intention to compare commercial softwares).
- All the above trials are with the Barrier Optimizer. The Primal or Dual Simplex Optimizers always obtained the correct solution. However, for larger problems the interior point optimizer is vastly faster in solving this large-scale, highly degenerate model.
Observation 3
If we add expressions (42) and (43) (in the main paper) as constraints into the model, the numerical issues can be resolved significantly, though these two constraints are theoretically proved to be redundant. We have these two constraints in our source code package but commented them out. If testers are interested, they can recover them for use in testing.
Conclusion
In summary, the Barrier Optimizer could generate some gaps between its results and the true optimal solution values. Testers should be careful to judge whether it is a numerical issue or a counterexample. The only cases we’ve seen are like our example of all equal costs. Even just using random costs (in our 9-node problem) between 99.9999 and 100.0001 removed the numerical issues. While, simplex methods may be more reliable for problems with all intercity travel costs equal (or very-nearly so), unfortunately, they would take a very long time to finish even for small problems.