search

scipopt / PyGCGOpt

Python interface and modeling environment for GCG
https://scipopt.github.io/PyGCGOpt/
MIT License
14 stars 4 forks source link

Different results of GCG and SCIP #26

Open haoyangliu123 opened 9 months ago

haoyangliu123 commented 9 months ago

Dear support team,

I solve a single instance (maximize) with pygcgopt and pyscipopt, but find different primal solutions. Pygcgopt terminates at 42.60s and outputs an "optimal" objective of +9.06769695399432e+04. Pyscipopt reaches the time limit of 100s and outputs the best objective of +9.35093089340221e+04, better than pygcgopt.

I wonder whether someone knows this problem. The code, instance file and log files are as follows.

Here is the .lp file (change the file type due to the platform support): instance.txt

The code:

from pygcgopt import Model

instance = f'instance.lp'
m = Model()
m.setParam('limits/time', 100)
m.setParam('randomization/randomseedshift', 0)
m.setParam('randomization/lpseed', 0)
m.setParam('randomization/permutationseed', 0)
m.readProblem(instance)
m.optimize()

Log file of pygcgopt:

original problem has 1500 variables (1500 bin, 0 int, 0 impl, 0 cont) and 2605 constraints
feasible solution found by trivial heuristic after 0.0 seconds, objective value 0.000000e+00
presolving:
(round 1, fast)       34 del vars, 627 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 1978 clqs
(round 2, fast)       58 del vars, 627 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 1978 clqs
(round 3, exhaustive) 58 del vars, 774 del conss, 0 add conss, 0 chg bounds, 147 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 1978 clqs
(round 4, exhaustive) 58 del vars, 774 del conss, 0 add conss, 0 chg bounds, 147 chg sides, 0 chg coeffs, 1831 upgd conss, 0 impls, 1978 clqs
(round 5, fast)       74 del vars, 776 del conss, 0 add conss, 0 chg bounds, 147 chg sides, 0 chg coeffs, 1831 upgd conss, 0 impls, 1974 clqs
(round 6, medium)     156 del vars, 779 del conss, 0 add conss, 0 chg bounds, 147 chg sides, 79 chg coeffs, 1831 upgd conss, 0 impls, 1969 clqs
(round 7, exhaustive) 167 del vars, 779 del conss, 0 add conss, 0 chg bounds, 147 chg sides, 79 chg coeffs, 1831 upgd conss, 0 impls, 1960 clqs
   (0.1s) probing: 51/1333 (3.8%) - 0 fixings, 0 aggregations, 0 implications, 0 bound changes
   (0.1s) probing aborted: 50/50 successive totally useless probings
presolving (8 rounds: 8 fast, 5 medium, 4 exhaustive):
 167 deleted vars, 780 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 147 changed sides, 79 changed coefficients
 0 implications, 1960 cliques
presolved problem has 1333 variables (1333 bin, 0 int, 0 impl, 0 cont) and 1825 constraints
   1825 constraints of type <setppc>
Presolving Time: 0.06
 Consclassifier "nonzeros" yields a classification with 10  different constraint classes 
 Consclassifier "constypes" yields a classification with 1 different constraint classes 
 Consclassifier "constypes according to miplib" yields a classification with 2 different constraint classes 
 Consclassifier "gamsdomain" yields a classification with 1  different constraint classes 
 Conspartition "gamsdomain" is not considered since it offers the same structure as "constypes" conspartition
 Consclassifier "gamssymbols" yields a classification with 1  different constraint classes 
 Conspartition "gamssymbols" is not considered since it offers the same structure as "constypes" conspartition
 Varclassifier "gamsdomain" yields a classification with 1  different variable classes 
 Varclassifier "gamssymbols" yields a classification with 1  different variable classes 
 Varpartition "gamssymbols" is not considered since it offers the same structure as "gamsdomain"
 Varclassifier "vartypes" yields a classification with 1 different variable classes
 Varpartition "vartypes" is not considered since it offers the same structure as "gamsdomain"
 Varclassifier "varobjvals" yields a classification with 1333 different variable classes
 Varclassifier "varobjvalsigns" yields a classification with 1 different variable classes
 Varpartition "varobjvalsigns" is not considered since it offers the same structure as "gamsdomain"
 Added reduced version of conspartition nonzeros with 9  different constraint classes 
 the current varclass distribution includes 1333 classes but only 18 are allowed for GCGconshdlrDecompCalcCandidatesNBlocks()
 in dec_consclass: there are 4 different constraint classes   
  the current consclass distribution includes 10 classes but only 9 are allowed for propagatePartialdec() of cons class detector
 the current constraint classifier "constypes" consists of 1 different classes   
  the current constraint classifier "constypes according to miplib" consists of 2 different classes   
  the current constraint classifier "nonzeros-red-to-9" consists of 9 different classes   
 dec_consclass found 515 new partialdecs 
dec_densemasterconss found 1 new partialdec 
dec_neighborhoodmaster found 1 new partialdec 
POSTPROCESSING of decompositions. Added 477 new decomps. 
Found 992 finished decompositions.
Measured running time per detector:
Detector postprocess               worked on      477 finished decompositions and took a total time of      0.089
Detector consclass                 worked on      988 finished decompositions and took a total time of      0.055
Detector densemasterconss          worked on        1 finished decompositions and took a total time of      0.000
Detector neighborhoodmaster        worked on        1 finished decompositions and took a total time of      0.000
Detector connectedbase             worked on      991 finished decompositions and took a total time of      0.393
Detector varclass                  worked on        1 finished decompositions and took a total time of      0.000
Detection Time: 1.64

A Dantzig-Wolfe reformulation is applied to solve the original problem.
Chosen structure has 173 blocks, 763 master-only (static) variables, and 1427 linking constraints.
This decomposition has a maxwhite score of 0.216789.
Matrix has 173 blocks, using 173 pricing problems.

  time | node  | left  |SLP iter|MLP iter|LP it/n| mem |mdpt |ovars|mvars|ocons|mcons|mcuts|  dualbound   | primalbound  |  deg   |  gap   
t  0.5s|     1 |     0 |      0 |      0 |     - |  62M|   0 |1333 |   0 |1825 |   0 |   0 | 4.780775e+05 | 1.063107e+04 |   --   |4396.98%
p  0.5s|     1 |     0 |      0 |      0 |     - |  64M|   0 |1333 |   0 |1825 |   0 |   0 | 4.780775e+05 | 6.586432e+04 |   --   | 625.85%
p  0.5s|     1 |     0 |      0 |      0 |     - |  64M|   0 |1333 |   0 |1825 |   0 |   0 | 4.780775e+05 | 7.626814e+04 |   --   | 526.84%
i  0.5s|     1 |     0 |      0 |      0 |     - |  64M|   0 |1333 |   0 |1825 |   0 |   0 | 4.780775e+05 | 7.797528e+04 |   --   | 513.11%
   1.5s|     1 |     0 |      0 |      0 |     - |  64M|   0 |1333 |   0 |1825 |   0 |   0 | 1.060817e+05 | 7.797528e+04 |   --   |  36.05%

   1.6s|     1 |     0 |    552 |    552 |     - |  69M|   0 |1333 | 936 |1826 |1601 |   0 | 1.060817e+05 | 7.797528e+04 |   0.00%|  36.05%
   1.6s|     1 |     0 |    552 |    552 |     - |  71M|   0 |1333 |1974 |1826 |1601 |   0 | 1.060817e+05 | 7.797528e+04 |   0.00%|  36.05%
*P13.8s|     1 |     0 |  11728 |  11728 |     - |  71M|   0 |1333 |1974 |1826 |1601 |   0 | 1.060817e+05 | 8.465736e+04 |   0.00%|  25.31%
  13.8s|     1 |     0 |  11728 |  11728 |     - |  71M|   0 |1333 |1974 |1826 |1601 |   0 | 1.060817e+05 | 8.465736e+04 |   0.00%|  25.31%
Starting reduced cost pricing...
  20.1s|     1 |     0 |  22795 |  22795 |     - |  80M|   0 |1333 |2402 |1826 |1601 |   0 | 1.060817e+05 | 8.465736e+04 |   0.82%|  25.31%
d 27.9s|     1 |     0 |  45269 |  45269 |     - | 112M|   0 |1333 |9149 |1826 |1601 |   0 | 1.060817e+05 | 8.510654e+04 |   0.82%|  24.65%
d 27.9s|     1 |     0 |  45269 |  45269 |     - | 113M|   0 |1333 |9322 |1826 |1601 |   0 | 1.060817e+05 | 8.653401e+04 |   0.82%|  22.59%
d 27.9s|     1 |     0 |  45269 |  45269 |     - | 113M|   0 |1333 |9495 |1826 |1601 |   0 | 1.060817e+05 | 9.067697e+04 |   0.82%|  16.99%
  38.2s|     1 |     0 |  45269 |  45269 |     - | 114M|   0 |1333 |9841 |1826 |1601 |   0 | 1.060817e+05 | 9.067697e+04 |   0.82%|  16.99%
  38.3s|     1 |     0 |  45269 |  45269 |     - | 115M|   0 |1333 |  10k|1826 |1601 |   0 | 1.060817e+05 | 9.067697e+04 |   0.82%|  16.99%
  time | node  | left  |SLP iter|MLP iter|LP it/n| mem |mdpt |ovars|mvars|ocons|mcons|mcuts|  dualbound   | primalbound  |  deg   |  gap   
  38.3s|     1 |     2 |  45269 |  45269 |     - | 116M|   0 |1333 |  10k|1826 |1601 |   0 | 1.060817e+05 | 9.067697e+04 |   0.82%|  16.99%

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 42.60
Solving Nodes      : 3
Primal Bound       : +9.06769695399432e+04 (56 solutions)
Dual Bound         : +9.06769695399432e+04
Gap                : 0.00 %

Log file of pyscipopt:

original problem has 1500 variables (1500 bin, 0 int, 0 impl, 0 cont) and 2605 constraints
feasible solution found by trivial heuristic after 0.0 seconds, objective value 0.000000e+00
presolving:
(round 1, fast)       34 del vars, 627 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 1978 clqs
(round 2, fast)       58 del vars, 627 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 1978 clqs
   (0.0s) running MILP presolver
   (0.0s) MILP presolver (2 rounds): 0 aggregations, 19 fixings, 0 bound changes
(round 3, medium)     77 del vars, 627 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 1973 clqs
(round 4, fast)       81 del vars, 635 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 1969 clqs
(round 5, exhaustive) 82 del vars, 781 del conss, 0 add conss, 0 chg bounds, 145 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 1969 clqs
(round 6, exhaustive) 82 del vars, 781 del conss, 0 add conss, 0 chg bounds, 145 chg sides, 0 chg coeffs, 1824 upgd conss, 0 impls, 1969 clqs
(round 7, medium)     162 del vars, 781 del conss, 0 add conss, 0 chg bounds, 145 chg sides, 80 chg coeffs, 1824 upgd conss, 0 impls, 1966 clqs
(round 8, exhaustive) 169 del vars, 781 del conss, 0 add conss, 0 chg bounds, 145 chg sides, 80 chg coeffs, 1824 upgd conss, 0 impls, 1959 clqs
   (0.1s) probing: 51/1331 (3.8%) - 0 fixings, 0 aggregations, 0 implications, 0 bound changes
   (0.1s) probing aborted: 50/50 successive totally useless probings
   (0.1s) symmetry computation started: requiring (bin +, int -, cont +), (fixed: bin -, int +, cont -)
   (0.1s) no symmetry present
presolving (9 rounds: 9 fast, 6 medium, 4 exhaustive):
 169 deleted vars, 781 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 145 changed sides, 80 changed coefficients
 0 implications, 1959 cliques
presolved problem has 1331 variables (1331 bin, 0 int, 0 impl, 0 cont) and 1824 constraints
   1824 constraints of type <setppc>
Presolving Time: 0.08

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl. 
t 0.1s|     1 |     0 |     0 |     - | trivial|   0 |1331 |1824 |   0 |   0 |  0 |   0 |   0 | 4.777589e+05 | 1.068445e+04 |4371.53%| unknown
p 0.1s|     1 |     0 |     0 |     - |  clique|   0 |1331 |1824 |1824 |   0 |  0 |   0 |   0 | 4.777589e+05 | 7.950136e+04 | 500.94%| unknown
  1.3s|     1 |     0 |  8500 |     - |    18M |   0 |1331 |1824 |1824 |   0 |  0 |   0 |   0 | 1.060817e+05 | 7.950136e+04 |  33.43%| unknown
  1.6s|     1 |     0 |  9017 |     - |    20M |   0 |1331 |1824 |1832 |   8 |  1 |   0 |   0 | 1.060178e+05 | 7.950136e+04 |  33.35%| unknown
  2.0s|     1 |     0 |  9335 |     - |    28M |   0 |1331 |1824 |1836 |  12 |  2 |   0 |   0 | 1.059762e+05 | 7.950136e+04 |  33.30%| unknown
  2.4s|     1 |     0 |  9640 |     - |    32M |   0 |1331 |1824 |1842 |  18 |  3 |   0 |   0 | 1.059506e+05 | 7.950136e+04 |  33.27%| unknown
  2.7s|     1 |     0 |  9909 |     - |    32M |   0 |1331 |1824 |1849 |  25 |  4 |   0 |   0 | 1.059356e+05 | 7.950136e+04 |  33.25%| unknown
  3.0s|     1 |     0 | 10006 |     - |    33M |   0 |1331 |1824 |1851 |  27 |  5 |   0 |   0 | 1.059302e+05 | 7.950136e+04 |  33.24%| unknown
  3.2s|     1 |     0 | 10113 |     - |    33M |   0 |1331 |1824 |1853 |  29 |  6 |   0 |   0 | 1.059268e+05 | 7.950136e+04 |  33.24%| unknown
  3.5s|     1 |     0 | 10400 |     - |    33M |   0 |1331 |1824 |1855 |  31 |  7 |   0 |   0 | 1.059119e+05 | 7.950136e+04 |  33.22%| unknown
  3.8s|     1 |     0 | 10428 |     - |    34M |   0 |1331 |1824 |1856 |  32 |  8 |   0 |   0 | 1.059117e+05 | 7.950136e+04 |  33.22%| unknown
  4.1s|     1 |     0 | 10614 |     - |    35M |   0 |1331 |1824 |1862 |  38 |  9 |   0 |   0 | 1.059012e+05 | 7.950136e+04 |  33.21%| unknown
  4.4s|     1 |     0 | 10711 |     - |    35M |   0 |1331 |1824 |1866 |  42 | 10 |   0 |   0 | 1.058973e+05 | 7.950136e+04 |  33.20%| unknown
  4.5s|     1 |     0 | 10725 |     - |    35M |   0 |1331 |1824 |1867 |  43 | 12 |   0 |   0 | 1.058971e+05 | 7.950136e+04 |  33.20%| unknown
  4.6s|     1 |     0 | 10790 |     - |    35M |   0 |1331 |1824 |1869 |  45 | 13 |   0 |   0 | 1.058958e+05 | 7.950136e+04 |  33.20%| unknown
 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl. 
  4.7s|     1 |     0 | 10873 |     - |    35M |   0 |1331 |1824 |1870 |  46 | 14 |   0 |   0 | 1.058940e+05 | 7.950136e+04 |  33.20%| unknown
  4.7s|     1 |     0 | 10910 |     - |    36M |   0 |1331 |1824 |1872 |  48 | 15 |   0 |   0 | 1.058938e+05 | 7.950136e+04 |  33.20%| unknown
  4.8s|     1 |     0 | 10960 |     - |    36M |   0 |1331 |1824 |1874 |  50 | 16 |   0 |   0 | 1.058929e+05 | 7.950136e+04 |  33.20%| unknown
  4.9s|     1 |     0 | 11025 |     - |    37M |   0 |1331 |1824 |1875 |  51 | 17 |   0 |   0 | 1.058908e+05 | 7.950136e+04 |  33.19%| unknown
  5.0s|     1 |     0 | 11079 |     - |    37M |   0 |1331 |1824 |1877 |  53 | 18 |   0 |   0 | 1.058897e+05 | 7.950136e+04 |  33.19%| unknown
  5.1s|     1 |     0 | 11089 |     - |    37M |   0 |1331 |1824 |1878 |  54 | 19 |   0 |   0 | 1.058897e+05 | 7.950136e+04 |  33.19%| unknown
d 7.6s|     1 |     0 | 29326 |     - |farkasdi|   0 |1331 |1824 |1878 |   0 | 19 |   0 |   0 | 1.058897e+05 | 9.010642e+04 |  17.52%| unknown
  7.6s|     1 |     0 | 29326 |     - |    39M |   0 |1331 |1824 |1878 |  54 | 19 |   0 |   0 | 1.058897e+05 | 9.010642e+04 |  17.52%| unknown
  7.7s|     1 |     0 | 29349 |     - |    39M |   0 |1331 |1824 |1879 |  55 | 20 |   0 |   0 | 1.058897e+05 | 9.010642e+04 |  17.52%| unknown
 11.0s|     1 |     2 | 29349 |     - |    39M |   0 |1331 |1824 |1879 |  55 | 21 |   0 |  22 | 1.057781e+05 | 9.010642e+04 |  17.39%| unknown
d31.0s|    14 |    15 | 43569 |2512.8 |pscostdi|  13 |1331 |1824 |1882 |   0 |  1 |   0 | 179 | 1.057781e+05 | 9.221538e+04 |  14.71%| unknown
 50.7s|   100 |   101 |144164 |1346.1 |    76M |  24 |1331 |1824 |1876 | 166 |  1 |   0 | 223 | 1.057781e+05 | 9.221538e+04 |  14.71%| unknown
*58.2s|   198 |   174 |174612 | 831.0 |    LP  |  55 |1331 |1824 |1908 | 228 |  2 |   0 | 261 | 1.057781e+05 | 9.231796e+04 |  14.58%| unknown
 58.2s|   200 |   174 |174660 | 822.9 |    96M |  55 |1331 |1824 |1908 | 228 |  2 |   0 | 261 | 1.057781e+05 | 9.231796e+04 |  14.58%| unknown
*58.3s|   218 |   170 |175298 | 757.6 |    LP  |  55 |1331 |1824 |1908 | 228 |  2 |   0 | 261 | 1.057781e+05 | 9.234057e+04 |  14.55%| unknown
 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl. 
*58.5s|   257 |   174 |176951 | 648.6 |    LP  |  59 |1331 |1824 |1908 | 228 |  2 |   0 | 261 | 1.057781e+05 | 9.243085e+04 |  14.44%| unknown
*58.7s|   293 |   167 |178455 | 573.8 |    LP  |  59 |1331 |1824 |1908 | 228 |  1 |   0 | 261 | 1.057781e+05 | 9.257921e+04 |  14.26%| unknown
*58.7s|   294 |   165 |178488 | 572.0 |    LP  |  59 |1331 |1824 |1908 | 228 |  2 |   0 | 261 | 1.057781e+05 | 9.261032e+04 |  14.22%| unknown
 58.7s|   300 |   165 |178840 | 561.7 |    96M |  59 |1331 |1824 |1908 | 228 |  0 |   0 | 261 | 1.057781e+05 | 9.261032e+04 |  14.22%| unknown
*59.0s|   328 |   160 |180501 | 518.6 |strongbr|  59 |1331 |1824 |1909 | 229 |  2 |   0 | 267 | 1.057781e+05 | 9.265688e+04 |  14.16%| unknown
 59.9s|   400 |   160 |185910 | 438.6 |    93M |  59 |1331 |1824 |1909 | 230 |  2 |   0 | 292 | 1.057781e+05 | 9.265688e+04 |  14.16%| unknown
 66.0s|   500 |   170 |213038 | 405.1 |    95M |  59 |1331 |1824 |1911 | 241 |  0 |   0 | 307 | 1.054810e+05 | 9.265688e+04 |  13.84%| unknown
L66.8s|   529 |   170 |215813 | 388.1 |    rins|  59 |1331 |1824 |1909 | 251 |  2 |   0 | 307 | 1.054810e+05 | 9.281152e+04 |  13.65%| unknown
i66.8s|   530 |   160 |215893 | 387.5 |  oneopt|  59 |1331 |1824 |1909 | 251 |  1 |   0 | 307 | 1.054810e+05 | 9.312160e+04 |  13.27%| unknown
d71.3s|   546 |   151 |235577 | 412.2 |linesear|  59 |1331 |1824 |1873 |   0 |  1 |   0 | 321 | 1.054603e+05 | 9.350931e+04 |  12.78%| unknown
 76.6s|   600 |   163 |261003 | 417.5 |    99M |  59 |1331 |1824 |1898 | 281 |  0 |   0 | 332 | 1.054402e+05 | 9.350931e+04 |  12.76%| unknown
 85.7s|   700 |   175 |306256 | 422.5 |   104M |  59 |1331 |1824 |1899 | 319 |  2 |   0 | 350 | 1.053743e+05 | 9.350931e+04 |  12.69%| unknown
 92.6s|   800 |   183 |336142 | 407.1 |   105M |  59 |1331 |1824 |1903 | 352 |  0 |   0 | 379 | 1.053545e+05 | 9.350931e+04 |  12.67%| unknown

SCIP Status        : solving was interrupted [time limit reached]
Solving Time (sec) : 100.00
Solving Nodes      : 882
Primal Bound       : +9.35093089340221e+04 (651 solutions)
Dual Bound         : +1.05352100630442e+05
Gap                : 12.66 %
jurgen-lentz commented 9 months ago

Which version of gcg are you exactly using?

haoyangliu123 commented 9 months ago

Thanks for your reply.

The version of GCG, SCIP, pygcgopt and pyscipopt are as follows: GCG 3.5.3 SCIP 8.0.3 pygcgopt 0.1.4 pyscipopt 4.2.0

Best regards