Scip 9.0/9.2 displayed solution to MPS problem differs from ORTOOLS solution and does not satisfy at least one constraint

[prater27]

Version: SciOpt 9.0.0 and 9.2.0 Compiled by me, compiler version: gcc version 13.2.0 (Ubuntu 13.2.0-23ubuntu4) 64 bits

Steps to reproduce: The displayed solution for the provided MPS instance (see attachment) by SCIP differs from the one given by ORTools, and does not seem to satisfy at least one of the constraints. The resulting objective value between SciOpt and ORTools is the same in different instances I tested, and part of the solution is also the same, but ORTools and SciOpt partially differ. Additionally the solution of ORTools satisfies the constraints' check I have written (and it is what I know the solution to the problem in the provided case is), while the one of SciOpt seems to fail at least one of the constraints.

I provide detailed information in the attached file (sciopt_bug_report.txt), where info sections are separated by §§§§§§§§§: sciopt_bug_report.txt

• MPS instance
• CMakeCache.txt
• Failed constraint in the SciOpt solution
• SciOpt solution and commands I used
• ORTools solution and program to solve it

I do not rule out I could be using SciOpt incorrectly, or maybe my (automatically-generated-MPS) problem has a bug. But the fact that the ORTools' solution works exactly as expected makes me think that maybe there could be a problem with SciOpt. The same happened with SciOpt 9.0.0

Thank you very much!

[DominikKamp]

With

SCIP version 9.2.1 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: Soplex 8.0.0] [GitHash: f3eda21447]
Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB)

External libraries: 
  Readline EditLine w  GNU library for command line editing (gnu.org/s/readline)
  Soplex 8.0.0         Linear Programming Solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: 72aa3807]
  CppAD 20180000.0     Algorithmic Differentiation of C++ algorithms developed by B. Bell (github.com/coin-or/CppAD)
  ZLIB 1.2.12          General purpose compression library by J. Gailly and M. Adler (zlib.net)
  GMP 6.3.0            GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)
  ZIMPL 3.7.0          Zuse Institute Mathematical Programming Language developed by T. Koch (zimpl.zib.de)
  AMPL/MP 690e9e7      AMPL .nl file reader library (github.com/ampl/mp)
  PaPILO 2.4.1         parallel presolve for integer and linear optimization (github.com/scipopt/papilo) (built with TBB) [GitHash: 802ec692]
  Nauty 2.8.8          Computing Graph Automorphism Groups by Brendan D. McKay (users.cecs.anu.edu.au/~bdm/nauty)
  sassy 1.1            Symmetry preprocessor by Markus Anders (github.com/markusa4/sassy)
  Ipopt 3.14.16        Interior Point Optimizer developed by A. Waechter et.al. (github.com/coin-or/Ipopt)

the attached model is declared infeasible and for both solutions

  [linear] <3_3_2>: <Y_0_2>[B] (+0) +<Y_1_2>[B] (+0) +<Y_2_2>[B] (+0) == 1;
;
violation: left hand side is violated by 1

so could you a attach the whole SCIP log to see where this solution comes from?

[prater27]

Thank you very much for your response.

Sorry my bad, in the previous attached file I had mixed the MPS instance and the solutions. Find the corrected version of the MPS instance in sciopt_but_report and also as standalone file.

I have also included the output of SciOpt 9.0.0 when I solve it in case it helps.

sciopt_bug_report.txt problem.txt

[DominikKamp]

The given solution seems to be feasible for the updated problem. So maybe some constraints did not make it into the problem file. Actually, I can not find a constraint like

-( + 1*X_1_1 + 2*X_1_2 + 3*X_1_3 + 4*X_1_4 + 5*X_1_5 + 6*X_1_6 + 7*X_1_7 + 8*X_1_8 + 9*X_1_9 + 10*X_1_10 + 11*X_1_11 + 12*X_1_12 + 13*X_1_13 + 14*X_1_14 + 15*X_1_15 + 16*X_1_16 + 17*X_1_17 + 18*X_1_18 + 19*X_1_19 + 20*X_1_20 + 21*X_1_21 + 22*X_1_22 + 23*X_1_23 + 24*X_1_24 + 25*X_1_25 + 26*X_1_26 + 27*X_1_27 + 28*X_1_28 + 29*X_1_29 + 30*X_1_30 + 31*X_1_31) + 31*V_1_26 <= -26 + d_1 + 31

especially there are no variables starting with d, but there are constraints

  [linear] <3_6_51>:  +31<V_1_26>[B] -2<X_1_1>[B] -3<X_1_2>[B] -4<X_1_3>[B] -5<X_1_4>[B] -6<X_1_5>[B] -7<X_1_6>[B] -8<X_1_7>[B] -9<X_1_8>[B] -10<X_1_9>[B] -11<X_1_10>[B] -12<X_1_11>[B] -13<X_1_12>[B] -14<X_1_13>[B] -15<X_1_14>[B] -16<X_1_15>[B] -17<X_1_16>[B] -18<X_1_17>[B] -19<X_1_18>[B] -20<X_1_19>[B] -21<X_1_20>[B] -22<X_1_21>[B] -23<X_1_22>[B] -24<X_1_23>[B] -25<X_1_24>[B] -26<X_1_25>[B] -27<X_1_26>[B] -28<X_1_27>[B] -29<X_1_28>[B] -30<X_1_29>[B] -31<X_1_30>[B] -32<X_1_31>[B] <= 9;
  [linear] <3_7_51>:  +31<V_1_26>[B] +2<X_1_1>[B] +3<X_1_2>[B] +4<X_1_3>[B] +5<X_1_4>[B] +6<X_1_5>[B] +7<X_1_6>[B] +8<X_1_7>[B] +9<X_1_8>[B] +10<X_1_9>[B] +11<X_1_10>[B] +12<X_1_11>[B] +13<X_1_12>[B] +14<X_1_13>[B] +15<X_1_14>[B] +16<X_1_15>[B] +17<X_1_16>[B] +18<X_1_17>[B] +19<X_1_18>[B] +20<X_1_19>[B] +21<X_1_20>[B] +22<X_1_21>[B] +23<X_1_22>[B] +24<X_1_23>[B] +25<X_1_24>[B] +26<X_1_25>[B] +27<X_1_26>[B] +28<X_1_27>[B] +29<X_1_28>[B] +30<X_1_29>[B] +31<X_1_30>[B] +32<X_1_31>[B] <= 58;

where the coefficients of the X variables might be absolutely too high by one.