SCIP giving two optimal solutions for same problem using different formulations

[ggsdc]

Hi!

I've been doing some tests to try to solve som TSP instances using SCIP with different formulations (MTZ and DFJ).

With one of the instances I'm running into a problem. When solving with the DFJ formulation and row generation I reach a certain optimum value (checked by other solvers and other methods), but with the same instance using the MTZ formulation SCIP tells me an optimal solution has been reached but it is different from the one found by the other method.

If I print the solution proposed by bothe methods I get the following graphs.
MTZ:

DFJ:

Attached are the mps and sol files (converted to .txt) generated by PuLP for both methods (for DFJ is the last iteration)

TSP_problem_(DFJ)-pulp-mps.txt
TSP_problem_(DFJ)-pulp-sol.txt
TSP_problem_(MTZ)-pulp-mps.txt
TSP_problem_(MTZ)-pulp-sol.txt

Thanks in advance for any help!

[ambros-gleixner]

Hi! If the MTZ formulation is correct, then this could be a bug in SCIP, cutting off the optimal solution. How I would debug that is to

1. take the solution from the DFJ model, convert it to a solution for the MTZ model and store it in a sol file.
2. Then you can specify this solution as a debug solution in the MTZ run and SCIP will hopefully tell you why it was cut off.

To run with a debug solution, first compile SCIP in debug-mode (flag: -DCMAKE_BUILD_TYPE=Debug) and with the option of using a debug solution (flag: -DDEBUGSOL=true). Now give the path to the debug solution to SCIP by setting the parameter misc/debugsol, e.g.

bin/scip -c "read /path/to/MZT.mps set misc debugsol /path/to/debug.sol"

This is on the command line, not sure whether you can get that through PuLP.

[ggsdc]

I think that the MTZ formulation is correct as in other isntances it gives back the same solution as the DFJ with SCIP and other solvers. Even the isntance that SCIP gives back two different solutions CBC, HiGHS or Gurobi give back the same solution with both formulations.

I will try your approach but I haven't been able to build SCIP from source in previous attempts. If I were not able to do it should I also send this issue to the mailing list?

Thank you for your help!

[DominikKamp]

The MTZ formulation is correct and with it we could reproduce and resolve an issue with the patch

conflict.patch

You have three options:

1. Apply the patch and build from source.
2. Disable conflict analysis with the parameter conflict/enable = FALSE.
3. Avoid unbounded variables by providing valid bounds.

A proper fix will be merged into v80-bugfix soon. It would be nice to know whether any of the above options resolves the issue in your setup.

[ggsdc]

The MTZ formulation is correct and with it we could reproduce and resolve an issue with the patch

conflict.patch

You have three options:

1. Apply the patch and build from source.
2. Disable conflict analysis with the parameter conflict/enable = FALSE.
3. Avoid unbounded variables by providing valid bounds.

A proper fix will be merged into v80-bugfix soon. It would be nice to know whether any of the above options resolves the issue in your setup.

Thank you. I couldn't try the first option but I tried approach 2 and 3.

Approach 2 doe snot seem to work, as even if I gave it 10 minutes as time limit the solver does not find one solution to rhe problem.

Approach 3 did the trick, setting up a strict upper bound in the variable definition, instead of the constraint, seem to be able to make the solver work. I haven't been able (a quick test) to find the optimal solution, but the reported integer solution is below the value reported as optimal before, so the real optimal solution is not cut out of the problem.

Thank you for your response and help. I am glad that the bug was found and soon it will be fixed.

Will leave it open till fix is merged.

[DominikKamp]

Thanks for your feedback!

With approach 2 in the latest bugfix release I get feasible solutions early but disabling conflict analysis can of course impact performance in general. Approach 3 could improve performance again, so to be safe you can also try both 2 and 3 if valid lower and upper bounds are not available for all variables.

Should you experience further trouble, just let us know.

[ggsdc]

Hi!

Is this bug fixed on version 8.0.4?

[DominikKamp]

No but it might be that you experience a random workaround on this instance. Also a fix is not merged yet due to server issues. I expect this will happen next week.

[DominikKamp]

A fix is merged now and will be part of the next bugfix release corresponding to the change

- respect unboundedness in the computation of activity bounds in conflict.c to avoid invalid huge bounds due to small coefficients on unbounded variables