SCIP - stuck in clique table clean up

Question

I'm running a multi year optimization with continuous and binary variables. For the 1st year, SCIP is able to pre-solve in 5 seconds and fully solve in under a minute, however, for the second year, SCIP gets stuck on the clique table clean up, not finishing in over 1h.

Details about the problems: 1st year:

original problem has 249472 variables (4189 bin, 0 int, 0 impl, 245283 cont) and 324123 constraints
presolved problem has 77757 variables (4189 bin, 0 int, 0 impl, 73568 cont) and 63603 constraints

2nd year:

original problem has 247394 variables (2112 bin, 0 int, 0 impl, 245282 cont) and 299978 constraints

As you can see, the 2nd year should be even quicker to solve (less contraints and binary variables).

I tried changing the clique table parameters to speed up the clean up, but I was not successful.

this is the message from year 2:

presolving:
(round 1, fast)       111770 del vars, 199370 del conss, 0 add conss, 175207 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 2112 impls, 0 clqs
(round 2, fast)       111774 del vars, 199371 del conss, 0 add conss, 228820 chg bounds, 1 chg sides, 0 chg coeffs, 0 upgd conss, 2112 impls, 0 clqs
(round 3, fast)       111774 del vars, 199371 del conss, 0 add conss, 262799 chg bounds, 1 chg sides, 0 chg coeffs, 0 upgd conss, 2112 impls, 0 clqs
(round 4, fast)       111774 del vars, 199371 del conss, 0 add conss, 267181 chg bounds, 1 chg sides, 0 chg coeffs, 0 upgd conss, 2112 impls, 0 clqs
(round 5, fast)       111774 del vars, 199371 del conss, 0 add conss, 269297 chg bounds, 1 chg sides, 0 chg coeffs, 0 upgd conss, 2112 impls, 0 clqs
(round 6, fast)       111774 del vars, 199371 del conss, 0 add conss, 269297 chg bounds, 2114 chg sides, 4224 chg coeffs, 0 upgd conss, 2112 impls, 0 clqs
   (3.0s) running MILP presolver
   (4.0s) MILP presolver (8 rounds): 21903 aggregations, 2 fixings, 6504 bound changes
(round 7, medium)     133680 del vars, 199372 del conss, 0 add conss, 275801 chg bounds, 2114 chg sides, 4224 chg coeffs, 0 upgd conss, 2112 impls, 0 clqs
(round 8, fast)       138055 del vars, 230038 del conss, 0 add conss, 275801 chg bounds, 4228 chg sides, 8448 chg coeffs, 0 upgd conss, 2112 impls, 0 clqs
(round 9, exhaustive) 138057 del vars, 234415 del conss, 0 add conss, 275811 chg bounds, 4228 chg sides, 8448 chg coeffs, 0 upgd conss, 2112 impls, 0 clqs
(round 10, exhaustive) 138057 del vars, 234415 del conss, 0 add conss, 275823 chg bounds, 4230 chg sides, 8448 chg coeffs, 2112 upgd conss, 2112 impls, 0 clqs
   (5.0s) probing: 52/2112 (2.5%) - 2 fixings, 0 aggregations, 0 implications, 0 bound changes
   (5.0s) probing aborted: 50/50 successive totally useless probings
   (5.0s) symmetry computation started: requiring (bin +, int -, cont +), (fixed: bin -, int +, cont -)
   (7.0s) symmetry computation finished: 585 generators found (max: 585, log10 of symmetry group size: inf) (symcode time: 2.00)
   (7.0s) no symmetry on binary variables present.
pressed CTRL-C 1 times (5 times for forcing termination)
(round 11, exhaustive) 138061 del vars, 234417 del conss, 171405 add conss, 275835 chg bounds, 4232 chg sides, 8448 chg coeffs, 2112 upgd conss, 2112 impls, 0 clqs
presolving (11 rounds: 11 fast, 4 medium, 3 exhaustive):
 138061 deleted vars, 234417 deleted constraints, 171405 added constraints, 275835 tightened bounds, 0 added holes, 4232 changed sides, 8448 changed coefficients
 2112 implications, 0 cliques
presolving was interrupted.
Presolving Time: 560.00

SCIP Status        : solving was interrupted [user interrupt]
Solving Time (sec) : 562.00
Solving Nodes      : 0
clique table cleanup detected 0 bound changes

Answer 1

After trying many different combinations of parameters in SCIP, I was able to identify that it was the symmetry pre-solving that was causing SCIP to get stuck. I disabled it with:

solver.options['misc/usesymmetry'] = 0

SCIP isn't able to finish some years even after running for a few hours, the optimality gap is under 0.1%. I will increase the acceptable optimality gap and use the near optimal solution.

Answer 2

As you can see, the 2nd year should be even quicker to solve (less constraints and binary variables).

The size of an optimization problem alone may not accurately predict the time required for its solution. If you look at the miplib benchmark (https://miplib.zib.de/tag_benchmark.html) there are instances with 5k variables (bnatt500) that are labeled as "hard instances" while instances with 20+k variables (academictimetablesmall) are "easy". Therefore, factors beyond problem size, such as problem structure and complexity, significantly influence solving time.

560 seconds is not a huge time limit by any means. I would recommend setting a time limit (2h) so that the logs are displayed. Then, one can have a look at the statistics to see which presolver/heuristics, etc consume much time. By identifying and potentially disabling time-consuming ones, solver efficiency can be improved.

Nevertheless, if you encounter unexpected behavior or bugs in SCIP please feel free to submit a bug ticket in SCIP. https://www.scipopt.org/bugs.php

Answer 3

Great that it worked for you.

SCIP isn't able to finish some years even after running for a few hours, the optimality gap is under 0.1%. I will increase the acceptable optimality gap and use the near-optimal solution.

Heuristics in MIP Solvers are quite sophisticated so in many times the optimal solution is found very fast. Providing the proof that the solution is indeed optimal takes significantly more time. Hence setting a gap to skip the optimality proof should be fine and is recommended in practice.

Nevertheless, it would be great if you could submit a bug ticket to help improve the quality of the solver. Getting stuck in symmetry detection should not be the case