[SCIP] best solution is not feasible in original problem

Tobias Stengel Tobias.Stengel at locom.de
Tue Dec 4 15:42:58 CET 2018


Hello,

I'm solving set cover problems with SCIP 6.0.0. I have one instance where SCIP prints

  [linear] <c_276>: <x_1013>[B] (-0) +<x_1019>[B] (-0) +<x_1021>[B] (-0) +<x_1131>[B] (-0) +<x_1139>[B] (-0) +<x_1142>[B] (-0) +<x_1301>[B] (-0) +<x_1302>[B] (-0) +<x_1317>[B] (-0) +<x_1318>[B] (-0) +<x_1322>[B] (+0) +<x_1323>[B] (+0) +<x_1324>[B] (-0) +<x_1354>[B] (-0) +<x_1446>[B] (-0) +<x_1449>[B] (-0) +<x_1450>[B] (-0) +<x_1451>[B] (-0) +<x_1452>[B] (-0) +<x_1617>[B] (-0) +<x_1621>[B] (+0) +<x_1622>[B] (-0) +<x_1623>[B] (-0) +<x_1624>[B] (-0) +<x_1625>[B] (-0) +<x_1626>[B] (+0) +<x_1627>[B] (-0) +<x_1820>[B] (+0) +<x_1952>[B] (+0) >= 1;
;
violation: left hand side is violated by 1
best solution is not feasible in original problem

SCIPgetStatus returns SCIP_STATUS_OPTIMAL.

For some reason this error is not reproducible with LP or MPS files - most probably due to slight loss of numeric precision of the objective coefficients.
Therefore I attached a small C++ problem that reproduces the issue.
After compiling setcover.cpp you can run
./setcover sets.csv

Unfortunatetly the programm requires boost for splitting strings - sorry for that.

For my understanding there is either a bug involved or the presolver is turning a (as far as I can see) numerically stable MIP into something unstable. CBC solves this MIP without issues.
Obvious workaround would be to check the constraint violation and try a second run with the presolver turned of...

Tobias


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20181204/7b715598/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: setcover.zip
Type: application/x-zip-compressed
Size: 21518 bytes
Desc: setcover.zip
URL: <http://listserv.zib.de/pipermail/scip/attachments/20181204/7b715598/attachment.bin>


More information about the Scip mailing list