Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Suboptimal MIP solution reported as optimal #74

Closed
jamespltan opened this issue Nov 28, 2023 · 2 comments
Closed

Suboptimal MIP solution reported as optimal #74

jamespltan opened this issue Nov 28, 2023 · 2 comments

Comments

@jamespltan
Copy link

jamespltan commented Nov 28, 2023 •
edited by svigerske
Loading

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
Copy link
Member

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
Copy link
Contributor

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!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@svigerske @jamespltan @DominikKamp