search

scipopt / papilo

Parallel Presolve for Integer and Linear Optimization
GNU Lesser General Public License v3.0
64 stars 17 forks source link

Performance regression from Papilo 2.1 to Papilo 2.3 #56

Closed rolfvdhulst closed 2 weeks ago

rolfvdhulst commented 3 months ago

I recently performed some tests for Presolving on SCIP's master branch and observed a significant performance regression for Papilo from 2.1 to 2.3. In general, the Papilo plugin seems to be anywhere between 40 to 100% slower without finding many new reductions. I checked and SCIP does indeed spend this time in Papilo, so the issue lies within Papilo.

Below is an example for the relatively large instance proteindesign121pgb11p9, where Papilo 2.1 takes 45 seconds but Papilo 2.3 takes 125 seconds.

Papilo 2.1:

SCIP version 10.0.0 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: Soplex 8.0.0] [GitHash: 80296625c3]
Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB)
External libraries: 
  Readline 8.1         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: bd56f573]
  CppAD 20180000.0     Algorithmic Differentiation of C++ algorithms developed by B. Bell (github.com/coin-or/CppAD)
  ZLIB 1.2.11          General purpose compression library by J. Gailly and M. Adler (zlib.net)
  TinyCThread 1.2      small portable implementation of the C11 threads API (tinycthread.github.io)
  GMP 6.2.1            GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)
  ZIMPL 3.5.3          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.1.1         parallel presolve for integer and linear optimization (github.com/scipopt/papilo) (built with TBB) [GitHash: 01fada2]
  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.11        Interior Point Optimizer developed by A. Waechter et.al. (github.com/coin-or/Ipopt)
original problem has 132672 variables (132594 bin, 78 int, 0 impl, 0 cont) and 254 constraints
    254 constraints of type <linear>
Reading Time: 0.21
LP Solver <Soplex 8.0.0>: barrier convergence tolerance cannot be set -- tolerance of SCIP and LP solver may differ
LP Solver <Soplex 8.0.0>: fastmip setting not available -- SCIP parameter has no effect
LP Solver <Soplex 8.0.0>: number of threads settings not available -- SCIP parameter has no effect
transformed problem has 132672 variables (132594 bin, 78 int, 0 impl, 0 cont) and 254 constraints
    254 constraints of type <linear>

original problem has 524690 active (1.557%) nonzeros and 524690 (1.557%) check nonzeros

presolving:
(round 1, fast)       1 del vars, 0 del conss, 98 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 187 impls, 2358 clqs
(round 2, fast)       1 del vars, 0 del conss, 98 add conss, 0 chg bounds, 90107 chg sides, 104416 chg coeffs, 0 upgd conss, 187 impls, 2358 clqs
   (7.8s) running MILP presolver
   (53.6s) MILP presolver (5 rounds): 2 aggregations, 50153 fixings, 64 bound changes
(round 3, medium)     50156 del vars, 254 del conss, 350 add conss, 64 chg bounds, 90107 chg sides, 104416 chg coeffs, 0 upgd conss, 187 impls, 297 clqs
(round 4, fast)       50165 del vars, 303 del conss, 445 add conss, 64 chg bounds, 90145 chg sides, 133992 chg coeffs, 0 upgd conss, 227 impls, 3085 clqs
(round 5, fast)       50165 del vars, 309 del conss, 445 add conss, 64 chg bounds, 142048 chg sides, 194622 chg coeffs, 0 upgd conss, 227 impls, 3085 clqs
(round 6, exhaustive) 50165 del vars, 387 del conss, 445 add conss, 64 chg bounds, 142116 chg sides, 194622 chg coeffs, 0 upgd conss, 227 impls, 3085 clqs
(round 7, fast)       50165 del vars, 387 del conss, 446 add conss, 64 chg bounds, 142116 chg sides, 194622 chg coeffs, 0 upgd conss, 227 impls, 3085 clqs
(round 8, fast)       50165 del vars, 387 del conss, 446 add conss, 64 chg bounds, 142117 chg sides, 194623 chg coeffs, 0 upgd conss, 227 impls, 3085 clqs
(round 9, exhaustive) 50165 del vars, 388 del conss, 446 add conss, 64 chg bounds, 142117 chg sides, 194623 chg coeffs, 0 upgd conss, 227 impls, 3085 clqs
(round 10, exhaustive) 50165 del vars, 388 del conss, 446 add conss, 64 chg bounds, 142117 chg sides, 194623 chg coeffs, 67 upgd conss, 227 impls, 3085 clqs
   (56.1s) sparsify aborted: 14974/325192 (4.6%) nonzeros canceled - in total 14974 canceled nonzeros, 15682 changed coefficients, 0 added nonzeros
(round 11, exhaustive) 50165 del vars, 388 del conss, 446 add conss, 64 chg bounds, 142117 chg sides, 210305 chg coeffs, 67 upgd conss, 229 impls, 3085 clqs
(round 12, fast)       50171 del vars, 394 del conss, 450 add conss, 78 chg bounds, 142117 chg sides, 210305 chg coeffs, 67 upgd conss, 229 impls, 3085 clqs
(round 13, fast)       50171 del vars, 400 del conss, 450 add conss, 78 chg bounds, 142308 chg sides, 210496 chg coeffs, 67 upgd conss, 229 impls, 3085 clqs
(round 14, medium)     50179 del vars, 400 del conss, 450 add conss, 78 chg bounds, 142316 chg sides, 210504 chg coeffs, 67 upgd conss, 229 impls, 3085 clqs
(round 15, fast)       50179 del vars, 400 del conss, 450 add conss, 78 chg bounds, 142316 chg sides, 212261 chg coeffs, 67 upgd conss, 229 impls, 3085 clqs
(round 16, exhaustive) 50179 del vars, 401 del conss, 450 add conss, 78 chg bounds, 142317 chg sides, 212261 chg coeffs, 67 upgd conss, 229 impls, 3085 clqs
   (58.5s) probing: 100/82433 (0.1%) - 0 fixings, 0 aggregations, 2314814 implications, 0 bound changes
   (60.7s) probing: 200/82433 (0.2%) - 0 fixings, 0 aggregations, 4661844 implications, 0 bound changes
   (62.9s) probing: 300/82433 (0.4%) - 0 fixings, 0 aggregations, 6952610 implications, 0 bound changes
   (65.2s) probing: 400/82433 (0.5%) - 0 fixings, 0 aggregations, 9318092 implications, 0 bound changes
   (67.4s) probing: 500/82433 (0.6%) - 0 fixings, 0 aggregations, 11665774 implications, 0 bound changes
   (69.7s) probing: 600/82433 (0.7%) - 0 fixings, 0 aggregations, 14080957 implications, 0 bound changes
   (72.0s) probing: 700/82433 (0.8%) - 0 fixings, 0 aggregations, 16425770 implications, 0 bound changes
   (74.0s) probing: 800/82433 (1.0%) - 0 fixings, 0 aggregations, 18390246 implications, 0 bound changes
   (76.0s) probing: 900/82433 (1.1%) - 0 fixings, 0 aggregations, 20195635 implications, 0 bound changes
   (77.8s) probing: 1000/82433 (1.2%) - 0 fixings, 0 aggregations, 21772901 implications, 0 bound changes
   (77.8s) probing: 1001/82433 (1.2%) - 0 fixings, 0 aggregations, 21783968 implications, 0 bound changes
   (77.8s) probing aborted: 1000/1000 successive useless probings
   (77.9s) symmetry computation started: requiring (bin +, int +, cont +), (fixed: bin -, int -, cont -)
   (77.9s) no symmetry present (symcode time: 0.01)
clique table cleanup detected 0 bound changes

presolved problem has 388294 active (1.55346%) nonzeros and 310198 (1.24102%) check nonzeros

presolving (17 rounds: 17 fast, 8 medium, 6 exhaustive):
 50179 deleted vars, 401 deleted constraints, 450 added constraints, 78 tightened bounds, 0 added holes, 142317 changed sides, 212261 changed coefficients
 17456 implications, 3086 cliques
presolved problem has 82493 variables (82433 bin, 12 int, 48 impl, 0 cont) and 303 constraints
     66 constraints of type <setppc>
    237 constraints of type <linear>
transformed objective value is always integral (scale: 1)
Presolving Time: 77.88
SCIP Status        : problem is presolved
Total Time         :      78.18
  solving          :      77.97
  presolving       :      77.88 (included in solving)
  reading          :       0.21
  copying          :       0.00 (0 times copied the problem)
Original Problem   :
  Problem name     : proteindesign121pgb11p9
  Variables        : 132672 (132594 binary, 78 integer, 0 implicit integer, 0 continuous)
  Constraints      : 254 initial, 254 maximal
  Objective        : minimize, 1 non-zeros (abs.min = 1, abs.max = 1)
Presolved Problem  :
  Problem name     : t_proteindesign121pgb11p9
  Variables        : 82493 (82433 binary, 12 integer, 48 implicit integer, 0 continuous)
  Constraints      : 303 initial, 303 maximal
  Objective        : minimize, 678 non-zeros (abs.min = 1, abs.max = 1104)
  Nonzeros         : 388294 constraint, 1049380 clique table
Presolvers         :   ExecTime  SetupTime  Calls  FixedVars   AggrVars   ChgTypes  ChgBounds   AddHoles    DelCons    AddCons   ChgSides   ChgCoefs
  boundshift       :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  convertinttobin  :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  domcol           :       0.07       0.00      2          0          0          0          0          0          0          0          0          0
  dualagg          :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  dualcomp         :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  dualinfer        :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  dualsparsify     :       0.05       0.00      1          0          0          0          0          0          0          0          0          0
  gateextraction   :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  implics          :       0.01       0.00      8          0          0          0          0          0          0          0          0          0
  inttobinary      :       0.00       0.00     17          0          0          0          0          0          0          0          0          0
  milp             :      45.87       0.00      1      50153          2          0         64          0        254        252          0          0
  qpkktref         :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  redvub           :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  sparsify         :       0.17       0.00      2          0          0          0          0          0          0          0          0      15682
  stuffing         :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  trivial          :       0.05       0.00     17          0          0          0          0          0          0          0          0          0
  tworowbnd        :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  dualfix          :       0.04       0.00     17          0          0          0          0          0          0          0          0          0
  genvbounds       :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  probing          :      21.56       0.00      1          0          0          0          0          0          0          0          0          0
  pseudoobj        :       0.00       0.00      1          0          0          0          0          0          0          0          0          0
  symmetry         :       0.06       0.00      1          0          0          0          0          0          0          0          0          0
  vbounds          :       0.20       0.00      2          0          0          0          0          0          0          0          0          0
  varbound         :       0.00       0.00      4          0          0          0          0          0          1          0          0          0
  setppc           :       0.06       0.00     14          0          8          0          0          0          0          0          8          8
  linear           :       9.67       0.02     23          1         15          0         14          0        146        198     142309     196571
  benders          :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  components       :       0.04       0.00      1          0          0          0          0          0          0          0          0          0
  root node        :          -          -      -          0          -          -          0          -          -          -          -          -
Constraints        :     Number  MaxNumber  #Separate #Propagate    #EnfoLP    #EnfoRelax  #EnfoPS    #Check   #ResProp    Cutoffs    DomReds       Cuts    Applied      Conss   Children
  benderslp        :          0          0          0          0          0          0          0          3          0          0          0          0          0          0          0
  integral         :          0          0          0          0          0          0          0          3          0          0          0          0          0          0          0
  setppc           :         66         66          0       4999          0          0          0          0          0          0          0          0          0          0          0
  linear           :        237        237          0       4999          0          0          0          3          0          0          0          0          0          0          0
  benders          :          0          0          0          0          0          0          0          0          0          0          0          0          0          0          0
  fixedvar         :          0          0          0          0          0          0          0          0          0          0          0          0          0          0          0
  countsols        :          0          0          0          0          0          0          0          0          0          0          0          0          0          0          0
  components       :          0          0          0          0          0          0          0          0          0          0          0          0          0          0          0
Constraint Timings :  TotalTime  SetupTime   Separate  Propagate     EnfoLP     EnfoPS     EnfoRelax   Check    ResProp    SB-Prop
  benderslp        :       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00
  integral         :       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00
  setppc           :       0.44       0.00       0.00       0.44       0.00       0.00       0.00       0.00       0.00       0.00
  linear           :       8.39       0.02       0.00       8.37       0.00       0.00       0.00       0.00       0.00       0.00
  benders          :       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00
  fixedvar         :       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00
  countsols        :       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00
  components       :       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00
Propagators        : #Propagate   #ResProp    Cutoffs    DomReds
  dualfix          :          0          0          0          0
  genvbounds       :          0          0          0          0
  nlobbt           :          0          0          0          0
  obbt             :          0          0          0          0
  probing          :          0          0          0          0
  pseudoobj        :          0          0          0          0
  redcost          :          0          0          0          0
  rootredcost      :          0          0          0          0
  symmetry         :          0          0          0          0
  vbounds          :          0          0          0          0
Propagator Timings :  TotalTime  SetupTime   Presolve  Propagate    ResProp    SB-Prop
  dualfix          :       0.04       0.00       0.04       0.00       0.00       0.00
  genvbounds       :       0.00       0.00       0.00       0.00       0.00       0.00
  nlobbt           :       0.00       0.00       0.00       0.00       0.00       0.00
  obbt             :       0.00       0.00       0.00       0.00       0.00       0.00
  probing          :      21.56       0.00      21.56       0.00       0.00       0.00
  pseudoobj        :       0.00       0.00       0.00       0.00       0.00       0.00
  redcost          :       0.00       0.00       0.00       0.00       0.00       0.00
  rootredcost      :       0.00       0.00       0.00       0.00       0.00       0.00
  symmetry         :       0.06       0.00       0.06       0.00       0.00       0.00
  vbounds          :       0.20       0.00       0.20       0.00       0.00       0.00
Conflict Analysis  :       Time      Calls    Success    DomReds  Conflicts   Literals    Reconvs ReconvLits   Dualrays   Nonzeros   LP Iters   (pool size: [--,--])
  propagation      :       0.00          0          0          -          0        0.0          0        0.0          -          -          -
  infeasible LP    :       0.00          0          0          -          0        0.0          0        0.0          0        0.0          0
  bound exceed. LP :       0.00          0          0          -          0        0.0          0        0.0          0        0.0          0
  strong branching :       0.00          0          0          -          0        0.0          0        0.0          -          -          0
  pseudo solution  :       0.00          0          0          -          0        0.0          0        0.0          -          -          -
  applied globally :       0.00          -          -          0          0        0.0          -          -          0          -          -
  applied locally  :          -          -          -          0          0        0.0          -          -          0          -          -
Primal Heuristics  :   ExecTime  SetupTime      Calls      Found       Best
  LP solutions     :       0.00          -          -          0          0
  relax solutions  :       0.00          -          -          0          0
  pseudo solutions :       0.00          -          -          0          0
  strong branching :       0.00          -          -          0          0
  actconsdiving    :       0.00       0.00          0          0          0
  adaptivediving   :       0.00       0.00          0          0          0
  alns             :       0.00       0.00          0          0          0
  bound            :       0.00       0.00          0          0          0
  clique           :       0.00       0.00          0          0          0
  coefdiving       :       0.00       0.00          0          0          0
  completesol      :       0.00       0.00          0          0          0
  conflictdiving   :       0.00       0.00          0          0          0
  crossover        :       0.00       0.00          0          0          0
  dins             :       0.00       0.00          0          0          0
  distributiondivin:       0.00       0.00          0          0          0
  dps              :       0.00       0.00          0          0          0
  dualval          :       0.00       0.00          0          0          0
  farkasdiving     :       0.00       0.00          0          0          0
  feaspump         :       0.00       0.00          0          0          0
  fixandinfer      :       0.00       0.00          0          0          0
  fracdiving       :       0.00       0.00          0          0          0
  gins             :       0.00       0.00          0          0          0
  guideddiving     :       0.00       0.00          0          0          0
  indicator        :       0.00       0.00          0          0          0
  indicatordiving  :       0.00       0.00          0          0          0
  intdiving        :       0.00       0.00          0          0          0
  intshifting      :       0.00       0.00          0          0          0
  linesearchdiving :       0.00       0.00          0          0          0
  localbranching   :       0.00       0.00          0          0          0
  locks            :       0.00       0.00          0          0          0
  lpface           :       0.00       0.00          0          0          0
  mpec             :       0.00       0.00          0          0          0
  multistart       :       0.00       0.00          0          0          0
  mutation         :       0.00       0.00          0          0          0
  nlpdiving        :       0.00       0.00          0          0          0
  objpscostdiving  :       0.00       0.00          0          0          0
  octane           :       0.00       0.00          0          0          0
  ofins            :       0.00       0.00          0          0          0
  oneopt           :       0.00       0.00          0          0          0
  padm             :       0.00       0.00          0          0          0
  proximity        :       0.00       0.00          0          0          0
  pscostdiving     :       0.00       0.00          0          0          0
  randrounding     :       0.00       0.00          0          0          0
  rens             :       0.00       0.00          0          0          0
  reoptsols        :       0.00       0.00          0          0          0
  repair           :       0.00       0.00          0          0          0
  rins             :       0.00       0.00          0          0          0
  rootsoldiving    :       0.00       0.00          0          0          0
  rounding         :       0.00       0.00          0          0          0
  scheduler        :       0.00       0.00          0          0          0
  shiftandpropagate:       0.00       0.00          0          0          0
  shifting         :       0.00       0.00          0          0          0
  simplerounding   :       0.00       0.00          0          0          0
  subnlp           :       0.00       0.00          0          0          0
  trivial          :       0.01       0.00          1          0          0
  trivialnegation  :       0.00       0.00          0          0          0
  trustregion      :       0.00       0.00          0          0          0
  trysol           :       0.00       0.00          0          0          0
  twoopt           :       0.00       0.00          0          0          0
  undercover       :       0.00       0.00          0          0          0
  vbounds          :       0.00       0.00          0          0          0
  veclendiving     :       0.00       0.00          0          0          0
  zeroobj          :       0.00       0.00          0          0          0
  zirounding       :       0.00       0.00          0          0          0
  other solutions  :          -          -          -          0          -
LNS (Scheduler)    :      Calls  SetupTime  SolveTime SolveNodes       Sols       Best       Exp3    Exp3-IX  EpsGreedy        UCB TgtFixRate  Opt  Inf Node Stal  Sol  Usr Othr Actv
  rens             :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
  rins             :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
  mutation         :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
  localbranching   :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
  crossover        :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
  proximity        :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
  zeroobjective    :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
  dins             :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
  trustregion      :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
Solution           :
  Solutions found  :          0 (0 improvements)
  Primal Bound     :          -
  Dual Bound       : +0.00000000000000e+00
  Gap              :   infinite
Integrals          :      Total       Avg%
  primal-dual      :    7797.00     100.00
  primal-ref       :          -          - (not evaluated)
  dual-ref         :          -          - (not evaluated) SCIP, and observed a significant performance regression from Papilo 2.1 to Papilo 2.3.

Papilo 2.3:

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

External libraries: 
  Readline 8.1         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: bd56f573]
  CppAD 20180000.0     Algorithmic Differentiation of C++ algorithms developed by B. Bell (github.com/coin-or/CppAD)
  ZLIB 1.2.11          General purpose compression library by J. Gailly and M. Adler (zlib.net)
  TinyCThread 1.2      small portable implementation of the C11 threads API (tinycthread.github.io)
  GMP 6.2.1            GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)
  ZIMPL 3.5.3          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.3.1         parallel presolve for integer and linear optimization (github.com/scipopt/papilo) (built with TBB) [GitHash: a0b3f4e1]
  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.11        Interior Point Optimizer developed by A. Waechter et.al. (github.com/coin-or/Ipopt)

user parameter file <scip.set> not found - using default parameters

SCIP> read /home/rolf/phd/data/collection/proteindesign121pgb11p9.mps.gz 

read problem </home/rolf/phd/data/collection/proteindesign121pgb11p9.mps.gz>
============

original problem has 132672 variables (132594 bin, 78 int, 0 impl, 0 cont) and 254 constraints
SCIP> presolve

presolving:
(round 1, fast)       1 del vars, 0 del conss, 98 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 187 impls, 2358 clqs
(round 2, fast)       1 del vars, 0 del conss, 98 add conss, 0 chg bounds, 90107 chg sides, 104416 chg coeffs, 0 upgd conss, 187 impls, 2358 clqs
   (7.8s) running MILP presolver
   (133.2s) MILP presolver (5 rounds): 2 aggregations, 50153 fixings, 64 bound changes
(round 3, medium)     50156 del vars, 254 del conss, 350 add conss, 64 chg bounds, 90107 chg sides, 104416 chg coeffs, 0 upgd conss, 187 impls, 297 clqs
(round 4, fast)       50165 del vars, 303 del conss, 445 add conss, 64 chg bounds, 90145 chg sides, 133992 chg coeffs, 0 upgd conss, 227 impls, 3085 clqs
(round 5, fast)       50165 del vars, 309 del conss, 445 add conss, 64 chg bounds, 142048 chg sides, 194622 chg coeffs, 0 upgd conss, 227 impls, 3085 clqs
(round 6, exhaustive) 50165 del vars, 387 del conss, 445 add conss, 64 chg bounds, 142116 chg sides, 194622 chg coeffs, 0 upgd conss, 227 impls, 3085 clqs
(round 7, fast)       50165 del vars, 387 del conss, 446 add conss, 64 chg bounds, 142116 chg sides, 194622 chg coeffs, 0 upgd conss, 227 impls, 3085 clqs
(round 8, fast)       50165 del vars, 387 del conss, 446 add conss, 64 chg bounds, 142117 chg sides, 194623 chg coeffs, 0 upgd conss, 227 impls, 3085 clqs
(round 9, exhaustive) 50165 del vars, 388 del conss, 446 add conss, 64 chg bounds, 142117 chg sides, 194623 chg coeffs, 0 upgd conss, 227 impls, 3085 clqs
(round 10, exhaustive) 50165 del vars, 388 del conss, 446 add conss, 64 chg bounds, 142117 chg sides, 194623 chg coeffs, 67 upgd conss, 227 impls, 3085 clqs
   (136.0s) sparsify aborted: 14974/325192 (4.6%) nonzeros canceled - in total 14974 canceled nonzeros, 15682 changed coefficients, 0 added nonzeros
(round 11, exhaustive) 50165 del vars, 388 del conss, 446 add conss, 64 chg bounds, 142117 chg sides, 210305 chg coeffs, 67 upgd conss, 229 impls, 3085 clqs
(round 12, fast)       50171 del vars, 394 del conss, 450 add conss, 78 chg bounds, 142117 chg sides, 210305 chg coeffs, 67 upgd conss, 229 impls, 3085 clqs
(round 13, fast)       50171 del vars, 400 del conss, 450 add conss, 78 chg bounds, 142308 chg sides, 210496 chg coeffs, 67 upgd conss, 229 impls, 3085 clqs
(round 14, medium)     50179 del vars, 400 del conss, 450 add conss, 78 chg bounds, 142316 chg sides, 210504 chg coeffs, 67 upgd conss, 229 impls, 3085 clqs
(round 15, fast)       50179 del vars, 400 del conss, 450 add conss, 78 chg bounds, 142316 chg sides, 212261 chg coeffs, 67 upgd conss, 229 impls, 3085 clqs
(round 16, exhaustive) 50179 del vars, 401 del conss, 450 add conss, 78 chg bounds, 142317 chg sides, 212261 chg coeffs, 67 upgd conss, 229 impls, 3085 clqs
   (166.9s) probing: 1000/82433 (1.2%) - 0 fixings, 0 aggregations, 21786924 implications, 0 bound changes
   (166.9s) probing: 1001/82433 (1.2%) - 0 fixings, 0 aggregations, 21800269 implications, 0 bound changes
   (166.9s) probing aborted: 1000/1000 successive useless probings
   (167.0s) symmetry computation started: requiring (bin +, int +, cont +), (fixed: bin -, int -, cont -)
   (167.1s) no symmetry present (symcode time: 0.01)
presolving (17 rounds: 17 fast, 8 medium, 6 exhaustive):
 50179 deleted vars, 401 deleted constraints, 450 added constraints, 78 tightened bounds, 0 added holes, 142317 changed sides, 212261 changed coefficients
 17473 implications, 3086 cliques
presolved problem has 82493 variables (82433 bin, 12 int, 48 impl, 0 cont) and 303 constraints
     66 constraints of type <setppc>
    237 constraints of type <linear>
transformed objective value is always integral (scale: 1)
Presolving Time: 166.97

SCIP> display statistics

SCIP Status        : problem is presolved
Total Time         :     167.40
  solving          :     167.14
  presolving       :     166.97 (included in solving)
  reading          :       0.26
  copying          :       0.00 (0 times copied the problem)
Original Problem   :
  Problem name     : proteindesign121pgb11p9
  Variables        : 132672 (132594 binary, 78 integer, 0 implicit integer, 0 continuous)
  Constraints      : 254 initial, 254 maximal
  Objective        : minimize, 1 non-zeros (abs.min = 1, abs.max = 1)
Presolved Problem  :
  Problem name     : t_proteindesign121pgb11p9
  Variables        : 82493 (82433 binary, 12 integer, 48 implicit integer, 0 continuous)
  Constraints      : 303 initial, 303 maximal
  Objective        : minimize, 678 non-zeros (abs.min = 1, abs.max = 1104)
  Nonzeros         : 388294 constraint, 1049380 clique table
Presolvers         :   ExecTime  SetupTime  Calls  FixedVars   AggrVars   ChgTypes  ChgBounds   AddHoles    DelCons    AddCons   ChgSides   ChgCoefs
  boundshift       :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  convertinttobin  :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  domcol           :       0.10       0.00      2          0          0          0          0          0          0          0          0          0
  dualagg          :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  dualcomp         :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  dualinfer        :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  dualsparsify     :       0.08       0.00      1          0          0          0          0          0          0          0          0          0
  gateextraction   :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  implics          :       0.02       0.00      8          0          0          0          0          0          0          0          0          0
  inttobinary      :       0.00       0.00     17          0          0          0          0          0          0          0          0          0
  milp             :     125.55       0.00      1      50153          2          0         64          0        254        252          0          0
  qpkktref         :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  redvub           :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  sparsify         :       0.22       0.00      2          0          0          0          0          0          0          0          0      15682
  stuffing         :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  trivial          :       0.09       0.00     17          0          0          0          0          0          0          0          0          0
  tworowbnd        :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  dualfix          :       0.06       0.00     17          0          0          0          0          0          0          0          0          0
  genvbounds       :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  probing          :      30.61       0.00      1          0          0          0          0          0          0          0          0          0
  pseudoobj        :       0.00       0.00      1          0          0          0          0          0          0          0          0          0
  symmetry         :       0.09       0.00      1          0          0          0          0          0          0          0          0          0
  vbounds          :       0.22       0.00      2          0          0          0          0          0          0          0          0          0
  varbound         :       0.00       0.00      4          0          0          0          0          0          1          0          0          0
  setppc           :       0.09       0.00     14          0          8          0          0          0          0          0          8          8
  linear           :       9.74       0.03     23          1         15          0         14          0        146        198     142309     196571
  benders          :       0.00       0.00      0          0          0          0          0          0          0          0          0          0
  components       :       0.05       0.00      1          0          0          0          0          0          0          0          0          0
  root node        :          -          -      -          0          -          -          0          -          -          -          -          -
Constraints        :     Number  MaxNumber  #Separate #Propagate    #EnfoLP    #EnfoRelax  #EnfoPS    #Check   #ResProp    Cutoffs    DomReds       Cuts    Applied      Conss   Children
  benderslp        :          0          0          0          0          0          0          0          3          0          0          0          0          0          0          0
  integral         :          0          0          0          0          0          0          0          3          0          0          0          0          0          0          0
  setppc           :         66         66          0       4998          0          0          0          0          0          0          0          0          0          0          0
  linear           :        237        237          0       4998          0          0          0          3          0          0          0          0          0          0          0
  benders          :          0          0          0          0          0          0          0          0          0          0          0          0          0          0          0
  fixedvar         :          0          0          0          0          0          0          0          0          0          0          0          0          0          0          0
  countsols        :          0          0          0          0          0          0          0          0          0          0          0          0          0          0          0
  components       :          0          0          0          0          0          0          0          0          0          0          0          0          0          0          0
Constraint Timings :  TotalTime  SetupTime   Separate  Propagate     EnfoLP     EnfoPS     EnfoRelax   Check    ResProp    SB-Prop
  benderslp        :       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00
  integral         :       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00
  setppc           :       0.57       0.00       0.00       0.57       0.00       0.00       0.00       0.00       0.00       0.00
  linear           :      11.44       0.03       0.00      11.41       0.00       0.00       0.00       0.00       0.00       0.00
  benders          :       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00
  fixedvar         :       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00
  countsols        :       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00
  components       :       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00       0.00
Propagators        : #Propagate   #ResProp    Cutoffs    DomReds
  dualfix          :          0          0          0          0
  genvbounds       :          0          0          0          0
  nlobbt           :          0          0          0          0
  obbt             :          0          0          0          0
  probing          :          0          0          0          0
  pseudoobj        :          0          0          0          0
  redcost          :          0          0          0          0
  rootredcost      :          0          0          0          0
  symmetry         :          0          0          0          0
  vbounds          :          0          0          0          0
Propagator Timings :  TotalTime  SetupTime   Presolve  Propagate    ResProp    SB-Prop
  dualfix          :       0.06       0.00       0.06       0.00       0.00       0.00
  genvbounds       :       0.00       0.00       0.00       0.00       0.00       0.00
  nlobbt           :       0.00       0.00       0.00       0.00       0.00       0.00
  obbt             :       0.00       0.00       0.00       0.00       0.00       0.00
  probing          :      30.61       0.00      30.61       0.00       0.00       0.00
  pseudoobj        :       0.00       0.00       0.00       0.00       0.00       0.00
  redcost          :       0.00       0.00       0.00       0.00       0.00       0.00
  rootredcost      :       0.00       0.00       0.00       0.00       0.00       0.00
  symmetry         :       0.09       0.00       0.09       0.00       0.00       0.00
  vbounds          :       0.22       0.00       0.22       0.00       0.00       0.00
Conflict Analysis  :       Time      Calls    Success    DomReds  Conflicts   Literals    Reconvs ReconvLits   Dualrays   Nonzeros   LP Iters   (pool size: [--,--])
  propagation      :       0.00          0          0          -          0        0.0          0        0.0          -          -          -
  infeasible LP    :       0.00          0          0          -          0        0.0          0        0.0          0        0.0          0
  bound exceed. LP :       0.00          0          0          -          0        0.0          0        0.0          0        0.0          0
  strong branching :       0.00          0          0          -          0        0.0          0        0.0          -          -          0
  pseudo solution  :       0.00          0          0          -          0        0.0          0        0.0          -          -          -
  applied globally :       0.00          -          -          0          0        0.0          -          -          0          -          -
  applied locally  :          -          -          -          0          0        0.0          -          -          0          -          -
Primal Heuristics  :   ExecTime  SetupTime      Calls      Found       Best
  LP solutions     :       0.00          -          -          0          0
  relax solutions  :       0.00          -          -          0          0
  pseudo solutions :       0.00          -          -          0          0
  strong branching :       0.00          -          -          0          0
  actconsdiving    :       0.00       0.00          0          0          0
  adaptivediving   :       0.00       0.00          0          0          0
  alns             :       0.00       0.00          0          0          0
  bound            :       0.00       0.00          0          0          0
  clique           :       0.00       0.00          0          0          0
  coefdiving       :       0.00       0.00          0          0          0
  completesol      :       0.00       0.00          0          0          0
  conflictdiving   :       0.00       0.00          0          0          0
  crossover        :       0.00       0.00          0          0          0
  dins             :       0.00       0.00          0          0          0
  distributiondivin:       0.00       0.00          0          0          0
  dps              :       0.00       0.00          0          0          0
  dualval          :       0.00       0.00          0          0          0
  farkasdiving     :       0.00       0.00          0          0          0
  feaspump         :       0.00       0.00          0          0          0
  fixandinfer      :       0.00       0.00          0          0          0
  fracdiving       :       0.00       0.00          0          0          0
  gins             :       0.00       0.00          0          0          0
  guideddiving     :       0.00       0.00          0          0          0
  indicator        :       0.00       0.00          0          0          0
  indicatordiving  :       0.00       0.00          0          0          0
  intdiving        :       0.00       0.00          0          0          0
  intshifting      :       0.00       0.00          0          0          0
  linesearchdiving :       0.00       0.00          0          0          0
  localbranching   :       0.00       0.00          0          0          0
  locks            :       0.00       0.00          0          0          0
  lpface           :       0.00       0.00          0          0          0
  mpec             :       0.00       0.00          0          0          0
  multistart       :       0.00       0.00          0          0          0
  mutation         :       0.00       0.00          0          0          0
  nlpdiving        :       0.00       0.00          0          0          0
  objpscostdiving  :       0.00       0.00          0          0          0
  octane           :       0.00       0.00          0          0          0
  ofins            :       0.00       0.00          0          0          0
  oneopt           :       0.00       0.00          0          0          0
  padm             :       0.00       0.00          0          0          0
  proximity        :       0.00       0.00          0          0          0
  pscostdiving     :       0.00       0.00          0          0          0
  randrounding     :       0.00       0.00          0          0          0
  rens             :       0.00       0.00          0          0          0
  reoptsols        :       0.00       0.00          0          0          0
  repair           :       0.00       0.00          0          0          0
  rins             :       0.00       0.00          0          0          0
  rootsoldiving    :       0.00       0.00          0          0          0
  rounding         :       0.00       0.00          0          0          0
  scheduler        :       0.00       0.00          0          0          0
  shiftandpropagate:       0.00       0.00          0          0          0
  shifting         :       0.00       0.00          0          0          0
  simplerounding   :       0.00       0.00          0          0          0
  subnlp           :       0.00       0.00          0          0          0
  trivial          :       0.02       0.00          1          0          0
  trivialnegation  :       0.00       0.00          0          0          0
  trustregion      :       0.00       0.00          0          0          0
  trysol           :       0.00       0.00          0          0          0
  twoopt           :       0.00       0.00          0          0          0
  undercover       :       0.00       0.00          0          0          0
  vbounds          :       0.00       0.00          0          0          0
  veclendiving     :       0.00       0.00          0          0          0
  zeroobj          :       0.00       0.00          0          0          0
  zirounding       :       0.00       0.00          0          0          0
  other solutions  :          -          -          -          0          -
LNS (Scheduler)    :      Calls  SetupTime  SolveTime SolveNodes       Sols       Best       Exp3    Exp3-IX  EpsGreedy        UCB TgtFixRate  Opt  Inf Node Stal  Sol  Usr Othr Actv
  rens             :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
  rins             :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
  mutation         :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
  localbranching   :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
  crossover        :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
  proximity        :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
  zeroobjective    :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
  dins             :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
  trustregion      :          0       0.00       0.00          0          0          0    0.00000    0.00000   -1.00000    1.00000      0.900    0    0    0    0    0    0    0    1
Solution           :
  Solutions found  :          0 (0 improvements)
  Primal Bound     :          -
  Dual Bound       : +0.00000000000000e+00
  Gap              :   infinite
Integrals          :      Total       Avg%
  primal-dual      :   16713.53     100.00
  primal-ref       :          -          - (not evaluated)
  dual-ref         :          -          - (not evaluated)

SCIP> quit
DominikKamp commented 3 months ago

In your comparison the SCIP versions differ. I have compared PaPILO 2.1.4 with latest develop PaPILO 2.4.0 in latest master SCIP 10.0.0 where presolving with the new version indeed takes 19.3 % longer while some more implications are found. Due to the instance size it is hard to tell whether they help afterwards at some point.

old.log

new.log

The time difference is significant enough to look into it but do you have encountered an instance where the difference reaches your claim when comparing to the latest develop PaPILO?

DominikKamp commented 3 months ago

It seems like we perform one more useless round of all presolvers now:

Old

          presolver     nb calls   success calls(%)    nb transactions     tsx applied(%)  execution time(s) 
       colsingleton            5                0.0                  0                0.0              0.000
    coefftightening            5                0.0                  0                0.0              0.000
        propagation            5               60.0                352              100.0              0.004
      simpleprobing            2                0.0                  0                0.0              0.000
       parallelrows            2                0.0                  0                0.0              0.004
           stuffing            2                0.0                  0                0.0              0.000
            dualfix            2                0.0                  0                0.0              0.002
      fixcontinuous            2                0.0                  0                0.0              0.000
       simplifyineq            2                0.0                  0                0.0              0.000
        doubletoneq            2                0.0                  0                0.0              0.000
            implint            2                0.0                  0                0.0              0.000
          dualinfer            2                0.0                  0                0.0              0.002
            probing            3               33.3              50091              100.0             43.382
             domcol            2                0.0                  0                0.0              0.574
       substitution            4              100.0                103                1.9              0.036

New

          presolver     nb calls   success calls(%)    nb transactions     tsx applied(%)  execution time(s) 
       colsingleton            6                0.0                  0                0.0              0.000
    coefftightening            6                0.0                  0                0.0              0.000
        propagation            6               50.0                352              100.0              0.015
      simpleprobing            3                0.0                  0                0.0              0.000
       parallelrows            3                0.0                  0                0.0              0.004
           stuffing            3                0.0                  0                0.0              0.000
            dualfix            3                0.0                  0                0.0              0.002
      fixcontinuous            3                0.0                  0                0.0              0.000
       simplifyineq            3                0.0                  0                0.0              0.000
        doubletoneq            3                0.0                  0                0.0              0.000
            implint            3                0.0                  0                0.0              0.000
          dualinfer            3                0.0                  0                0.0              0.002
            probing            4               25.0              50091              100.0             59.318
             domcol            3                0.0                  0                0.0              0.566
       substitution            5               80.0                103                1.9              0.035
DominikKamp commented 3 months ago

The additional round is already introduced in PaPILO 2.2.0 but without overhead.

The overhead is actually introduced afterwards in PaPILO 2.2.1.

DominikKamp commented 3 months ago

A fix in single row propagation causes this slowdown and it seems like the computational effort can be reduced without losing the fix. I consider this as a bugfix since it should have been part of the original fix and therefore target it to main. But it is not clear when this will be merged since I have no permissions and @alexhoen is not there.

rolfvdhulst commented 2 months ago

It's still strange that Papilo needs probing at all for this particular instance; Highs can fix the columns without any probing. I'll highlight how below;

For example, for fixing 'X_INTRODUCED_108', the reasoning needed is as follows.

I shorten the variable names to 'x_100' here, all variables are integer/binary.

First, objective constraint 'p_lin_0' is of the form x_obj = x11 + x_12 + ...

with lb(x_obj) = 0, ub(x_obj) = 39062 and lb(x_11) = 0, ub(x_11)= 39063. Then, ub(x_obj) = 39062 implies that ub(x_11) can be strengthened to ub(x_11) = 39062 (using the objective cutoff, essentially) Second, constraint 'p_lin_2' is of the form x_11 = 39063 x_108 + ... where all ... terms are binaries with positive integral coefficients. Because ub(x_11) = 39062, we can fix x_108 = 0 using bound implications, since this implies that x_108 <= 39602/39603 < 1.

These are definitely reductions that I would expect papilo to find, without probing. The only thing I can think off here is that numerical tolerances prevent one of the reductions. However, in an ideal world we should detect that this is not an issue here, as integrality of both the coefficients and the variables ensures validity.

DominikKamp commented 2 months ago

The fix is actually on this type of reduction (single row propagation), which seems to be used in probing as well. Numerics do not look too bad here. Do you mean that this is done in probing instead of propagation or that it does no longer happen at all?

rolfvdhulst commented 2 months ago

Highs finds the fixings using propagation, and does not perform any probing at all, whereas Papilo does not find the reductions in propagation and needs to use probing. So likely, Papilo is leaving some (obvious) performance on the table during propagation or is not doing it fully.

DominikKamp commented 2 months ago

When switching off PaPILOs probing, I get

          presolver     nb calls   success calls(%)    nb transactions     tsx applied(%)  execution time(s) 
       colsingleton            6                0.0                  0                0.0              0.000
    coefftightening            6                0.0                  0                0.0              0.000
        propagation            6               50.0             100534              100.0              0.007
      simpleprobing            3                0.0                  0                0.0              0.000
       parallelrows            3                0.0                  0                0.0              0.004
           stuffing            3                0.0                  0                0.0              0.000
            dualfix            3                0.0                  0                0.0              0.002
      fixcontinuous            3                0.0                  0                0.0              0.000
       simplifyineq            3                0.0                  0                0.0              0.000
        doubletoneq            3                0.0                  0                0.0              0.000
            implint            3                0.0                  0                0.0              0.000
          dualinfer            3                0.0                  0                0.0              0.002
             domcol            3                0.0                  0                0.0              0.957
       substitution            5               80.0                259                0.8              0.043

and t_X_INTRODUCED108 is still fixed to zero. So you are definitely right that there is something to win here but it rather seems like probing kicks in too early by default since propagation is able to find the exposed reduction. Was this default probing behavior different in a previous version of PaPILO?

rolfvdhulst commented 2 months ago

There is also a difference between single-threaded and multithreaded runs.

Single-threaded calling Papilo's executable:

          presolver     nb calls   success calls(%)    nb transactions     tsx applied(%)  execution time(s) 
       colsingleton           11               18.2                115               50.4              0.000
    coefftightening           11                0.0                  0                0.0              0.000
        propagation           11               45.5                652              100.0              0.033
      fixcontinuous            1                0.0                  0                0.0              0.000
      simpleprobing            4                0.0                  0                0.0              0.000
       parallelrows            3                0.0                  0                0.0              0.006
       parallelcols            3                0.0                  0                0.0              0.022
           stuffing            4                0.0                  0                0.0              0.000
            dualfix            4                0.0                  0                0.0              0.006
       simplifyineq            4                0.0                  0                0.0              0.000
        doubletoneq            4                0.0                  0                0.0              0.000
            implint            1                0.0                  0                0.0              0.000
             domcol            3                0.0                  0                0.0              1.317
          dualinfer            1                0.0                  0                0.0              0.000
            probing            5               20.0              50091              100.0            547.793
       substitution            8               87.5                162                4.3              0.044
           sparsify            3               33.3                 66              100.0              0.031

Papilo executable, Threads = 2:

          presolver     nb calls   success calls(%)    nb transactions     tsx applied(%)  execution time(s) 
       colsingleton            9               22.2                 58              100.0              0.000
    coefftightening            9                0.0                  0                0.0              0.000
        propagation            9               55.6             100708              100.0              0.010
      fixcontinuous            1                0.0                  0                0.0              0.000
      simpleprobing            3                0.0                  0                0.0              0.000
       parallelrows            3                0.0                  0                0.0              0.004
       parallelcols            3                0.0                  0                0.0              0.015
           stuffing            3                0.0                  0                0.0              0.000
            dualfix            3                0.0                  0                0.0              0.003
       simplifyineq            3                0.0                  0                0.0              0.000
        doubletoneq            3                0.0                  0                0.0              0.000
            implint            1                0.0                  0                0.0              0.000
             domcol            3                0.0                  0                0.0              0.445
          dualinfer            1                0.0                  0                0.0              0.000
            probing            3                0.0                  0                0.0              0.174
       substitution            6               83.3                235                3.0              0.035
           sparsify            3               33.3                 66              100.0              0.032

SCIP uses the single-threaded version (with some tweaks). Debugging the code, the issue seems to be that somehow the rows whose activity is modified by the first reduction are not properly tracked. Papilo even calls the constraint propagation presolver again but then with an empty 'changed_activities' vector. The issue seems to only affect the implementation of the non-multithreaded code, because this uses a different logic (for some reason...).

This is quite a big issue that could potentially also affect the performance of other plugins in Papilo that are not triggering from reductions, as it seems like Papilo is not correctly telling the plugins what rows have been modified.

DominikKamp commented 2 months ago

Sounds like a good catch. Indeed, at the top of Presolve::evaluate_and_apply() there is a weird reset of the changed_activities, which seems to cause this undesired skip of propagation. No idea what this is for, so I am just trying to remove this.

DominikKamp commented 2 months ago

The computational overhead in propagation during probing shown in https://github.com/scipopt/papilo/issues/56#issuecomment-2266725673 should be reduced again by 944ddf3, whereas the fundamentally inefficient evaluation sequence described in https://github.com/scipopt/papilo/issues/56#issuecomment-2268989256 persists.

DominikKamp commented 2 weeks ago

This is resolved with b4051e3002abdc6a9a3042c985c1e6978437b0e3 when applying PaPILO directly, however, through SCIP the setting presolve.removeslackvars = 0 still avoids a significant performance improvement here.