Solution quality regression for set cover problems with constraints on the number of selected columns

[tobiass-sdl]

setcover.zip

For the attached problem (and a few similar instances that are harder for me to export as a lp/mps file) scip 10.0.2 does not find a solution within a few minutes while 9.2.4 does. Highs also finds a solution within a few minutes.

Not sure whether this a bug or just the result of some change that is in general improving but hurts for this kind of problem.

The problem is a set cover problem where the columns are grouped into disjoint groups and for each group there is a restriction on how many columns can be selected. Therefore trivial stuff that works for pure set cover problems like setting all variables to 1 or round up the lp relaxation is unlikely to produce a feasible solution.

Logs:
scip 10.0.2 / binary download for windows:

[...]
presolved problem has 140130 variables (140130 bin, 0 int, 0 cont) and 13283 constraints
      9 constraints of type <knapsack>
  13274 constraints of type <logicor>
Presolving Time: 2.00

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl.
 14.0s|     1 |     0 | 23388 |     - |  1131M |   0 | 140k|  13k|  13k|   0 |  0 | 270 |   0 | 6.025078e+06 |      --      |    Inf | unknown
 99.0s|     1 |     0 | 46331 |     - |  1236M |   0 | 140k|  13k|  13k|  52 |  1 | 270 |   0 | 6.042443e+06 |      --      |    Inf | unknown
  165s|     1 |     0 | 49665 |     - |  1264M |   0 | 140k|  13k|  13k| 121 |  2 | 270 |   0 | 6.057743e+06 |      --      |    Inf | unknown
  261s|     1 |     0 | 52612 |     - |  1284M |   0 | 140k|  13k|  13k| 181 |  3 | 270 |   0 | 6.066749e+06 |      --      |    Inf | unknown
  356s|     1 |     0 | 55282 |     - |  1304M |   0 | 140k|  13k|  13k| 247 |  4 | 270 |   0 | 6.075111e+06 |      --      |    Inf | unknown

scip 9.2.4 / installed using windows installer:

[...]
presolved problem has 140130 variables (140130 bin, 0 int, 0 impl, 0 cont) and 13283 constraints
      9 constraints of type <knapsack>
  13274 constraints of type <logicor>
Presolving Time: 3.00

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl.
 17.0s|     1 |     0 | 23246 |     - |  1088M |   0 | 140k|  13k|  13k|   0 |  0 | 270 |   0 | 6.025078e+06 |      --      |    Inf | unknown
o 129s|     1 |     0 | 69549 |     - |feaspump|   0 | 140k|  13k|  13k|   0 |  0 | 270 |   0 | 6.025078e+06 | 6.482536e+06 |   7.59%| unknown
  144s|     1 |     0 | 72580 |     - |  1175M |   0 | 140k|  13k|  13k|  61 |  1 | 270 |   0 | 6.044444e+06 | 6.482536e+06 |   7.25%| unknown
i 144s|     1 |     0 | 72580 |     - |  oneopt|   0 | 140k|  13k|  13k|  61 |  1 | 270 |   0 | 6.044444e+06 | 6.381714e+06 |   5.58%| unknown
  151s|     1 |     0 | 75461 |     - |  1202M |   0 | 140k|  13k|  13k| 119 |  2 | 270 |   0 | 6.056773e+06 | 6.381714e+06 |   5.36%| unknown
  159s|     1 |     0 | 78635 |     - |  1224M |   0 | 140k|  13k|  13k| 184 |  3 | 270 |   0 | 6.065958e+06 | 6.381714e+06 |   5.21%| unknown
  167s|     1 |     0 | 81255 |     - |  1247M |   0 | 140k|  13k|  13k| 247 |  4 | 270 |   0 | 6.072024e+06 | 6.381714e+06 |   5.10%| unknown
  174s|     1 |     0 | 84051 |     - |  1265M |   0 | 140k|  13k|  13k| 325 |  5 | 270 |   0 | 6.079024e+06 | 6.381714e+06 |   4.98%| unknown
  182s|     1 |     0 | 87016 |     - |  1285M |   0 | 140k|  13k|  13k| 394 |  6 | 270 |   0 | 6.087126e+06 | 6.381714e+06 |   4.84%| unknown
  190s|     1 |     0 | 89637 |     - |  1308M |   0 | 140k|  13k|  13k| 457 |  7 | 270 |   0 | 6.091356e+06 | 6.381714e+06 |   4.77%| unknown
  196s|     1 |     0 | 92176 |     - |  1329M |   0 | 140k|  13k|  13k| 519 |  8 | 270 |   0 | 6.094990e+06 | 6.381714e+06 |   4.70%| unknown
  203s|     1 |     0 | 94735 |     - |  1351M |   0 | 140k|  13k|  13k| 588 |  9 | 270 |   0 | 6.098400e+06 | 6.381714e+06 |   4.65%| unknown
  209s|     1 |     0 | 97227 |     - |  1370M |   0 | 140k|  13k|  13k| 656 | 10 | 270 |   0 | 6.101595e+06 | 6.381714e+06 |   4.59%| unknown
  214s|     1 |     0 | 98583 |     - |  1381M |   0 | 140k|  13k|  13k| 712 | 11 | 270 |   0 | 6.102505e+06 | 6.381714e+06 |   4.58%| unknown
  221s|     1 |     0 | 99788 |     - |  1388M |   0 | 140k|  13k|  14k| 763 | 12 | 270 |   0 | 6.103727e+06 | 6.381714e+06 |   4.55%| unknown
 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl.
  227s|     1 |     0 |100886 |     - |  1392M |   0 | 140k|  13k|  14k| 807 | 13 | 270 |   0 | 6.104634e+06 | 6.381714e+06 |   4.54%| unknown
  233s|     1 |     0 |102694 |     - |  1397M |   0 | 140k|  13k|  14k| 866 | 14 | 270 |   0 | 6.106316e+06 | 6.381714e+06 |   4.51%| unknown
  238s|     1 |     0 |103316 |     - |  1405M |   0 | 140k|  13k|  14k| 895 | 15 | 270 |   0 | 6.106670e+06 | 6.381714e+06 |   4.50%| unknown
  244s|     1 |     0 |104187 |     - |  1409M |   0 | 140k|  13k|  14k| 924 | 16 | 270 |   0 | 6.107428e+06 | 6.381714e+06 |   4.49%| unknown
  250s|     1 |     0 |104571 |     - |  1412M |   0 | 140k|  13k|  14k| 944 | 17 | 270 |   0 | 6.107595e+06 | 6.381714e+06 |   4.49%| unknown
  257s|     1 |     0 |105813 |     - |  1418M |   0 | 140k|  13k|  14k| 984 | 18 | 270 |   0 | 6.108685e+06 | 6.381714e+06 |   4.47%| unknown
  262s|     1 |     0 |106212 |     - |  1424M |   0 | 140k|  13k|  14k|1005 | 19 | 270 |   0 | 6.108909e+06 | 6.381714e+06 |   4.47%| unknown
  268s|     1 |     0 |106384 |     - |  1427M |   0 | 140k|  13k|  14k|1014 | 20 | 270 |   0 | 6.109126e+06 | 6.381714e+06 |   4.46%| unknown
  273s|     1 |     0 |106399 |     - |  1427M |   0 | 140k|  13k|  14k|1016 | 21 | 270 |   0 | 6.109128e+06 | 6.381714e+06 |   4.46%| unknown
L 460s|     1 |     0 |189647 |     - |    rens|   0 | 140k|  13k|  14k|1016 | 22 | 274 |   0 | 6.109128e+06 | 6.320570e+06 |   3.46%| unknown

highs 1.10 debian package:

[...]
Solving MIP model with:
   13285 rows
   140049 cols (139385 binary, 664 integer, 0 implied int., 0 continuous)
   1164961 nonzeros

Src: B => Branching; C => Central rounding; F => Feasibility pump; H => Heuristic; L => Sub-MIP;
     P => Empty MIP; R => Randomized rounding; S => Solve LP; T => Evaluate node; U => Unbounded;
     z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point; X => User solution

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work
Src  Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   5157.970941     inf                  inf        0      0      0         0   116.6s
         0       0         0   0.00%   6025078.000718  inf                  inf        0      0     23     23108   118.4s
 R       0       0         0   0.00%   6058082.44634   12343499.68079    50.92%     2029     82     30     25344   119.8s
         0       0         0   0.00%   6078960.27118   12343499.68079    50.75%     4921    174    870     28471   135.5s
         0       0         0   0.00%   6099578.262953  12343499.68079    50.58%     7587    494    870     37829   141.4s
         0       0         0   0.00%   6104627.16426   12343499.68079    50.54%     9050    689    870     43331   147.0s
         0       0         0   0.00%   6107299.308617  12343499.68079    50.52%     9875    768    870     46071   152.5s
         0       0         0   0.00%   6109941.800171  12343499.68079    50.50%    10680    898    870     50650   158.3s
         0       0         0   0.00%   6111687.893518  12343499.68079    50.49%    10738   1032    870     55084   164.5s
         0       0         0   0.00%   6112708.47782   12343499.68079    50.48%     9138   1122    870     58668   170.1s
         0       0         0   0.00%   6113447.01501   12343499.68079    50.47%     8607   1145    870     62305   175.9s
         0       0         0   0.00%   6113927.899989  12343499.68079    50.47%     8372   1222    870     65983   181.3s
         0       0         0   0.00%   6114343.424458  12343499.68079    50.47%     8118   1301    870     69908   187.0s
 L       0       0         0   0.00%   6114498.727515  6307330.466438     3.06%     8157   1366    870     71384   251.6s
 L       0       0         0   0.00%   6114498.727515  6301273.461486     2.96%     8157   1366    870     81429   268.1s
 L       0       0         0   0.00%   6114498.727515  6298841.698287     2.93%     7343    851    870     85346   285.5s
       135     134         1   0.00%   6114498.727515  6298841.698287     2.93%     7346    851   1000    241542   397.3s

[tobiass-sdl]

I let it run for longer and after ~2200s (at the end of the root node) scip 10.0.* finds good solutions - first farkas diving, then rens. Has something changed in the priority / timing of the heuristics between 9.2.* and 10.0.*?
Providing a rather stupid initial solution (>35% gap) did not help within a time limit of 300s.
Next step would be to try to add a custom heuristic in case the problem is mostly logicor with a few knapsack constraints and no (negative) impact otherwise.

[DominikKamp]

Yes, there was 6a1c9dd to reduce the diving overhead for major instance sets. When reverted this brings back the feaspump solution. Maybe this can be retuned.

[DominikKamp]

For example setting heuristics/feaspump/maxlpiterofs = 100000 gives feaspump enough resources to find a solution for this instance, but I doubt that this is a reasonable default value.

[tobiass-sdl]

Quick status update: I have a prototype of a fast heuristic (using objscip) that produces good solutions during the root node:

time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl. 
L 9.0s|     1 |     0 |     0 |     - |feasjump|   0 | 140k|  13k|  13k|   0 |  0 | 270 |   0 | 5.157971e+03 | 1.086350e+07 |  Large | unknown
i 9.0s|     1 |     0 |     0 |     - |  oneopt|   0 | 140k|  13k|  13k|   0 |  0 | 270 |   0 | 5.157971e+03 | 1.017285e+07 |  Large | unknown
 10.0s|     1 |     0 | 26009 |     - |  1206M |   0 | 140k|  13k|  13k|   0 |  0 | 270 |   0 | 6.025078e+06 | 1.017285e+07 |  68.84%| unknown
S12.0s|     1 |     0 | 26009 |     - |setcover|   0 | 140k|  13k|  13k|   0 |  0 | 270 |   0 | 6.025078e+06 | 6.601694e+06 |   9.57%| unknown
 15.0s|     1 |     0 | 28307 |     - |  1304M |   0 | 140k|  13k|  13k|  64 |  1 | 270 |   0 | 6.044942e+06 | 6.601694e+06 |   9.21%| unknown
 21.0s|     1 |     0 | 30508 |     - |  1330M |   0 | 140k|  13k|  13k| 129 |  2 | 270 |   0 | 6.057262e+06 | 6.601694e+06 |   8.99%| unknown
 27.0s|     1 |     0 | 32679 |     - |  1356M |   0 | 140k|  13k|  13k| 202 |  3 | 270 |   0 | 6.068350e+06 | 6.601694e+06 |   8.79%| unknown
S29.0s|     1 |     0 | 32679 |     - |setcover|   0 | 140k|  13k|  13k| 202 |  3 | 270 |   0 | 6.068350e+06 | 6.532869e+06 |   7.65%| unknown

What remains is to benchmark this on a broader set of instances include instances that are not 99% logicor.
As I have tasks with higher priority and given the workaround "use HiGHS" I do not know when this will happen...

[DominikKamp]

@tobiass-sdl Have you tested whether heuristics/feaspump/maxlpiterofs = 100000 gives acceptable performance, or does the feaspump solution come too late for this application?

[tobiass-sdl]

That approach is not promising due to the structure of the software - there is a vrp heuristic that internally solves set cover style MIPs but calls scip/highs/... throw a general abstraction layer. If I change the setting, I change ist for all calls to scip and that might not be the best idea - not all MIPs generated by the application are set cover problems.

User has a dropdown to switch between scip, highs, cbc and gurobi (if licensed) at runtime so switching to highs is the easiest workaround.

Therefore I didn't experiment with heuristics/feaspump/maxlpiterofs

[DominikKamp]

Yes, without testing we do not know. But since the regression is only due to reducing the effort in feaspump, it might still be worth to investigate whether it makes sense to increase it again in general. We can do this internally, though more test instances with this issues might help.