search

scipopt / scip

SCIP - Solving Constraint Integer Programs
Other
366 stars 63 forks source link

Suboptimal MIP solution reported as optimal #74

Closed jamespltan closed 6 months ago

jamespltan commented 7 months ago

Version: 8.0.4

Problem

\*  *\
Maximize
objective: 2.42260797536 x1 - 1.40244497025 x2 - 1.79442858595 x3 + 1.27993632648 x4 + 0.671036131762 x5 + 1.22512613484 x6 - 1.64795529655 x7 + 0.463422687207 x8 + 1.66547673372 x9

Subject To
constraint_0: 0.218339734154 x1 - 1.32950779675 x2 + 2.4634990055 x3 + 1.64158303089 x4 - 0.0695051166321 x5 + 0.252238239808 x6 - 1.8645732963 x7 - 2.42063040453 x8 + 0.0188111646313 x9 <= 1.43538532349

constraint_1: 0.446026221538 x1 + 0.907938821356 x2 - 1.25996529828 x3 - 2.06249182097 x4 + 0.677886502448 x5 + 0.564902020915 x6 - 2.26167843033 x7 - 0.288537429087 x8 + 1.07812833444 x9 <= -1.39357470318

constraint_2: 1.8845137297 x1 - 0.206595984073 x2 + 2.31007071429 x3 - 0.755138364915 x4 + 2.39842131875 x5 - 1.94826799266 x6 - 2.099880238 x7 + 1.52000281463 x8 - 2.47487895327 x9 <= 0.829740380345

constraint_3: - 1.40737822051 x1 - 1.09799340533 x2 - 1.56676860756 x3 - 0.879176966596 x4 + 0.244240373982 x5 + 1.62547316847 x6 + 1.92538222303 x7 + 0.357942052077 x8 + 0.92697370115 x9 <= 1.45112645728

constraint_4: - 0.0714868952715 x1 + 1.5642310642 x2 + 1.83665258579 x3 - 0.101395436161 x4 + 2.0645407008 x5 + 2.20921426929 x6 + 0.952432349585 x7 + 1.51238865271 x8 + 0.944864868744 x9 <= 2.06177620264

Bounds
 0 <= x4
 0 <= x5
 0 <= x6
 0 <= x7
 0 <= x8
 0 <= x9
Generals
x4
x5
x6
x7
x8
x9
End

Log

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl. 
  0.0s|     1 |     0 |    13 |     - |   662k |   0 |   9 |   5 |   5 |   0 |  0 |   7 |   0 | 1.333169e+01 |      --      |    Inf | unknown
  0.0s|     1 |     0 |    19 |     - |   665k |   0 |   9 |   5 |   5 |   0 |  0 |   7 |   0 | 1.333169e+01 |      --      |    Inf | unknown
  0.0s|     1 |     0 |    21 |     - |   673k |   0 |   9 |   5 |   7 |   2 |  1 |   7 |   0 | 1.281797e+01 |      --      |    Inf | unknown
  0.0s|     1 |     0 |    22 |     - |   674k |   0 |   9 |   5 |   8 |   3 |  3 |   7 |   0 | 1.171670e+01 |      --      |    Inf | unknown
  0.0s|     1 |     0 |    24 |     - |   675k |   0 |   9 |   5 |   9 |   4 |  4 |   7 |   0 | 1.057891e+01 |      --      |    Inf | unknown
r 0.0s|     1 |     0 |    24 |     - |shifting|   0 |   9 |   5 |   9 |   4 |  4 |   7 |   0 | 1.057891e+01 | 7.234849e+00 |  46.22%| unknown
  0.0s|     1 |     0 |    26 |     - |   688k |   0 |   9 |   5 |  10 |   5 |  5 |   7 |   0 | 1.015720e+01 | 7.234849e+00 |  40.39%| unknown
  0.0s|     1 |     0 |    26 |     - |   695k |   0 |   9 |   5 |  10 |   5 |  5 |   7 |   0 | 1.015720e+01 | 7.234849e+00 |  40.39%| unknown
  0.0s|     1 |     0 |    26 |     - |   695k |   0 |   9 |   5 |  10 |   5 |  6 |   7 |   0 | 7.234849e+00 | 7.234849e+00 |   0.00%| unknown
SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.00
Solving Nodes      : 1
Primal Bound       : +7.23484860466995e+00 (1 solutions)
Dual Bound         : +7.23484860466995e+00
Gap                : 0.00 %

The correct solution

x1=3.9218162
x2=0.46370957
x4=3
x7=2

Objective value: 9.39459446

svigerske commented 6 months ago

I can reproduce with SCIP 8.0.4, more precisely

SCIP version 8.0.4 [precision: 8 byte] [memory: block] [mode: debug] [LP solver: Soplex 6.0.4] [GitHash: a8e51afd1e]
Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB)

External libraries: 
  Readline 8.2         GNU library for command line editing (gnu.org/s/readline)
  Soplex 6.0.4         Linear Programming Solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: 950b1658]
  CppAD 20180000.0     Algorithmic Differentiation of C++ algorithms developed by B. Bell (github.com/coin-or/CppAD)
  ZLIB 1.3             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)
  AMPL/MP 4e2d45c4     AMPL .nl file reader library (github.com/ampl/mp)
  bliss 0.77           Computing Graph Automorphism Groups by T. Junttila and P. Kaski (www.tcs.hut.fi/Software/bliss/)

But changing to SCIP 8.1.0 seems to help:

SCIP version 8.1.0 [precision: 8 byte] [memory: block] [mode: debug] [LP solver: Soplex 6.0.4] [GitHash: b7635b560b]
Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB)

External libraries: 
  Readline 8.2         GNU library for command line editing (gnu.org/s/readline)
  Soplex 6.0.4         Linear Programming Solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: 950b1658]
  CppAD 20180000.0     Algorithmic Differentiation of C++ algorithms developed by B. Bell (github.com/coin-or/CppAD)
  ZLIB 1.3             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)
  AMPL/MP 4e2d45c4     AMPL .nl file reader library (github.com/ampl/mp)
  bliss 0.77           Computing Graph Automorphisms by T. Junttila and P. Kaski (users.aalto.fi/~tjunttil/bliss)
  sassy 1.1            Symmetry preprocessor by Markus Anders (github.com/markusa4/sassy)

reading user parameter file <scip.set>

read problem <../scip/74.lp>
============

original problem has 9 variables (0 bin, 6 int, 0 impl, 3 cont) and 5 constraints
      5 constraints of type <linear>
Reading Time: 0.00

solve problem
=============

LP Solver <Soplex 6.0.4>: barrier convergence tolerance cannot be set -- tolerance of SCIP and LP solver may differ
LP Solver <Soplex 6.0.4>: fastmip setting not available -- SCIP parameter has no effect
LP Solver <Soplex 6.0.4>: number of threads settings not available -- SCIP parameter has no effect
transformed problem has 9 variables (0 bin, 6 int, 0 impl, 3 cont) and 5 constraints
      5 constraints of type <linear>

original problem has 45 active (100%) nonzeros and 45 (100%) check nonzeros

presolving:
clique table cleanup detected 0 bound changes

presolved problem has 45 active (100%) nonzeros and 45 (100%) check nonzeros

presolving (1 rounds: 1 fast, 1 medium, 1 exhaustive):
 0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
 0 implications, 0 cliques
presolved problem has 9 variables (0 bin, 6 int, 0 impl, 3 cont) and 5 constraints
      5 constraints of type <linear>
Presolving Time: 0.00

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |frac |vars |cons |cuts |confs|strbr|  dualbound   | primalbound  |  gap   
  0.0s|     1 |     0 |     7 |     - |   641k |   0 |   3 |   9 |   5 |   0 |   0 |   0 | 1.333169e+01 |      --      |    Inf 
  0.0s|     1 |     0 |    15 |     - |   655k |   0 |   2 |   9 |   5 |   2 |   0 |   0 | 1.281797e+01 |      --      |    Inf 
  0.0s|     1 |     0 |    16 |     - |   659k |   0 |   2 |   9 |   5 |   3 |   0 |   0 | 1.171670e+01 |      --      |    Inf 
  0.0s|     1 |     0 |    18 |     - |   666k |   0 |   2 |   9 |   5 |   4 |   0 |   0 | 1.057891e+01 |      --      |    Inf 
r 0.0s|     1 |     0 |    18 |     - |shifting|   0 |   2 |   9 |   5 |   4 |   0 |   0 | 1.057891e+01 | 7.234849e+00 |  46.22%
  0.0s|     1 |     0 |    20 |     - |   674k |   0 |   2 |   9 |   5 |   5 |   0 |   0 | 1.015720e+01 | 7.234849e+00 |  40.39%
  0.0s|     1 |     0 |    20 |     - |   674k |   0 |   2 |   9 |   5 |   5 |   0 |   0 | 1.015720e+01 | 7.234849e+00 |  40.39%
  0.0s|     1 |     0 |    21 |     - |   682k |   0 |   2 |   9 |   5 |   6 |   0 |   0 | 9.971166e+00 | 7.234849e+00 |  37.82%
r 0.0s|     1 |     0 |    21 |     - |shifting|   0 |   2 |   9 |   5 |   6 |   0 |   0 | 9.971166e+00 | 7.461294e+00 |  33.64%
  0.0s|     1 |     0 |    24 |     - |   689k |   0 |   2 |   9 |   5 |   7 |   0 |   0 | 9.809670e+00 | 7.461294e+00 |  31.47%
  0.0s|     1 |     0 |    25 |     - |   699k |   0 |   2 |   9 |   5 |   8 |   0 |   0 | 9.749885e+00 | 7.461294e+00 |  30.67%
  0.0s|     1 |     0 |    28 |     - |   723k |   0 |   2 |   9 |   5 |   9 |   0 |   0 | 9.691401e+00 | 7.461294e+00 |  29.89%
  0.0s|     1 |     0 |    30 |     - |   735k |   0 |   3 |   9 |   5 |  10 |   0 |   0 | 9.673910e+00 | 7.461294e+00 |  29.65%
  0.0s|     1 |     0 |    35 |     - |   757k |   0 |   3 |   9 |   5 |  11 |   0 |   0 | 9.592739e+00 | 7.461294e+00 |  28.57%
r 0.0s|     1 |     0 |    35 |     - |shifting|   0 |   3 |   9 |   5 |  11 |   0 |   0 | 9.592739e+00 | 9.381120e+00 |   2.26%
 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |frac |vars |cons |cuts |confs|strbr|  dualbound   | primalbound  |  gap   
  0.0s|     1 |     0 |    37 |     - |   759k |   0 |   3 |   9 |   5 |  12 |   0 |   0 | 9.574429e+00 | 9.381120e+00 |   2.06%
r 0.0s|     1 |     0 |    37 |     - |shifting|   0 |   3 |   9 |   5 |  12 |   0 |   0 | 9.574429e+00 | 9.393188e+00 |   1.93%
  0.0s|     1 |     0 |    37 |     - |   759k |   0 |   3 |   9 |   5 |  12 |   0 |   0 | 9.574429e+00 | 9.393188e+00 |   1.93%
  0.0s|     1 |     0 |    39 |     - |   761k |   0 |   3 |   9 |   5 |  13 |   0 |   0 | 9.495427e+00 | 9.393188e+00 |   1.09%
  0.0s|     1 |     0 |    40 |     - |   767k |   0 |   3 |   9 |   5 |  14 |   0 |   0 | 9.473015e+00 | 9.393188e+00 |   0.85%
  0.1s|     1 |     0 |    41 |     - |   769k |   0 |   3 |   9 |   5 |  15 |   0 |   0 | 9.469414e+00 | 9.393188e+00 |   0.81%
  0.1s|     1 |     0 |    43 |     - |   772k |   0 |   3 |   9 |   5 |  17 |   0 |   0 | 9.466086e+00 | 9.393188e+00 |   0.78%
  0.1s|     1 |     0 |    44 |     - |   786k |   0 |   3 |   9 |   5 |  19 |   0 |   0 | 9.463921e+00 | 9.393188e+00 |   0.75%
  0.1s|     1 |     0 |    48 |     - |   789k |   0 |   3 |   9 |   5 |  21 |   0 |   0 | 9.446350e+00 | 9.393188e+00 |   0.57%
  0.1s|     1 |     0 |    52 |     - |   792k |   0 |   3 |   9 |   5 |  22 |   0 |   0 | 9.433035e+00 | 9.393188e+00 |   0.42%
  0.1s|     1 |     0 |    54 |     - |   795k |   0 |   3 |   9 |   5 |  24 |   0 |   0 | 9.423123e+00 | 9.393188e+00 |   0.32%
  0.1s|     1 |     0 |    55 |     - |   800k |   0 |   3 |   9 |   5 |  25 |   0 |   0 | 9.421725e+00 | 9.393188e+00 |   0.30%
  0.1s|     1 |     0 |    56 |     - |   838k |   0 |   3 |   9 |   5 |  26 |   0 |   0 | 9.420835e+00 | 9.393188e+00 |   0.29%
  0.1s|     1 |     0 |    58 |     - |   838k |   0 |   3 |   9 |   5 |  27 |   0 |   0 | 9.413050e+00 | 9.393188e+00 |   0.21%
  0.1s|     1 |     0 |    60 |     - |   854k |   0 |   3 |   9 |   5 |  28 |   0 |   0 | 9.412483e+00 | 9.393188e+00 |   0.21%
 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |frac |vars |cons |cuts |confs|strbr|  dualbound   | primalbound  |  gap   
  0.1s|     1 |     0 |    62 |     - |   854k |   0 |   3 |   9 |   5 |  29 |   0 |   0 | 9.409107e+00 | 9.393188e+00 |   0.17%
  0.1s|     1 |     0 |    63 |     - |   854k |   0 |   3 |   9 |   5 |  30 |   0 |   0 | 9.407509e+00 | 9.393188e+00 |   0.15%
  0.1s|     1 |     0 |    64 |     - |   867k |   0 |   3 |   9 |   5 |  31 |   0 |   0 | 9.407354e+00 | 9.393188e+00 |   0.15%
  0.1s|     1 |     0 |    66 |     - |   867k |   0 |   3 |   9 |   5 |  32 |   0 |   0 | 9.406138e+00 | 9.393188e+00 |   0.14%
  0.1s|     1 |     0 |    67 |     - |   867k |   0 |   3 |   9 |   5 |  33 |   0 |   0 | 9.405883e+00 | 9.393188e+00 |   0.14%
  0.1s|     1 |     0 |    69 |     - |   867k |   0 |   3 |   9 |   5 |  34 |   0 |   0 | 9.405353e+00 | 9.393188e+00 |   0.13%
L 0.2s|     1 |     0 |    78 |     - |    rens|   0 |   2 |   9 |   6 |  34 |   3 |   0 | 9.403485e+00 | 9.394594e+00 |   0.09%
  0.2s|     1 |     0 |    80 |     - |   876k |   0 |   2 |   9 |   6 |  34 |   3 |   0 | 9.403316e+00 | 9.394594e+00 |   0.09%
  0.2s|     1 |     0 |    80 |     - |   876k |   0 |   2 |   9 |   6 |  34 |   3 |   0 | 9.403316e+00 | 9.394594e+00 |   0.09%
  0.2s|     1 |     0 |    83 |     - |   886k |   0 |   1 |   9 |   6 |  36 |   3 |   0 | 9.400863e+00 | 9.394594e+00 |   0.07%
  0.2s|     1 |     0 |    83 |     - |   886k |   0 |   1 |   9 |   6 |  36 |   3 |   0 | 9.400863e+00 | 9.394594e+00 |   0.07%
  0.2s|     1 |     0 |    86 |     - |   886k |   0 |   - |   9 |   6 |  37 |   3 |   0 | 9.394594e+00 | 9.394594e+00 |   0.00%
  0.2s|     1 |     0 |    86 |     - |   886k |   0 |   - |   9 |   6 |  37 |   3 |   0 | 9.394594e+00 | 9.394594e+00 |   0.00%

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.17
Solving Nodes      : 1
Primal Bound       : +9.39459445511721e+00 (27 solutions)
Dual Bound         : +9.39459445511721e+00
Gap                : 0.00 %

If updating SCIP does not help for you, then reopen and provide a full log (so we see what dependencies you are using).

DominikKamp commented 6 months ago

In the reproducing setup this is due to the same reason as in #63 which is indeed already resolved in 8.1.0. Merry Christmas!