Obtain best feasible solution with SCIP

Question

I am using SCIP (SoPlex) to solve a MIP (mixed integer program) provided by a .mps file. I use SCIP via command line as follows:

SCIP> read file.mps
original problem has 1049 variables (471 bin, 0 int, 0 impl, 578 cont) and 638 constraints
SCIP> optimize    # so i am using default settings
... some solving information ...
SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.46
Solving Nodes      : 1
Primal Bound       : -6.58117502066443e+05 (2 solutions)
Dual Bound         : -6.58117502066443e+05
Gap                : 0.00 %
[linear] c_2_141>: x_2_73_141[C] - 1000000000 y_2_141[B] <= 0;
violation: right hand side is violated by 236.775818639799
best solution is not feasible in original problem

I do not want to have an infeasible solution – a want the best feasible. For your information: I used CPLEX with the same file and it confirmed that there is an optimal feasible solution with slightly worse obj value (like 0.05 % worse). I already tried to put emphasis on feasibility with SCIP> set emphasis feasibility but that did not help me – see for yourself:

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.42
Solving Nodes      : 3 (total of 5 nodes in 3 runs)
Primal Bound       : -6.58117502066443e+05 (4 solutions)
Dual Bound         : -6.58117502066443e+05
Gap                : 0.00 %
[linear] c_2_141>: x_2_73_141[C] - 1000000000 y_2_141[B] <= 0;
violation: right hand side is violated by 236.775818639799
best solution is not feasible in original problem

Kind regards.

EDIT: In response to the answer of user mattmilten, I have to share that using set numerics feastol 1e-9 alone did not bring a feasible solution, but using a lower tolerance like 1e-10 in combination with set emphasis feasibility, SCIP is able to provide a good feasible solution that is just 0.005 % worse than CPLEX’.

Thanks for your help mattmilten!

Answer 1

You could try to tighten the tolerances, especially the feasibility tolerance:

set numerics feastol 1e-9

The violated constraint contains a very large coefficient. This is likely the cause for this high absolute error. In CPLEX you should also try

display solution quality

to check whether the solution found by CPLEX is also violating the bounds.