Solve time issues with solution overlap parameter
AnsweredHello,
I have a MIP that I recursively resolve with additional constraints to control the variety of solutions. I do this with a parameter k such that each following solution may only share k elements with the previous solution and so forth, thus a lower k yields a higher variety of solutions than a higher k. I did originally try using solution pools, but the problem was that in this particular problem, each item is pegged to a slot and cosmetic rearrangements of the solution wind up populating most of the pool. Thus, I wasn't able to easily get a variety of solutions like my approach with the k parameter.
The issue is that as the number of solutions grows, the solve time becomes prohibitively long for usage. I experimented with warmstarting Gurobi with the prior solution, but due to the koverlap constraint, I would get a message that the initial guess is an invalid solution and it would simply start anew and take just as long.
Here's a log of the first solve with no overlap constraints:
Optimize a model with 454 rows, 636 columns and 6989 nonzeros
Variable types: 0 continuous, 636 integer (0 binary)
Variable types: 0 continuous, 636 integer (0 binary)
Coefficient statistics:
Coefficient statistics:
Matrix range [1e+00, 1e+04]
Matrix range [1e+00, 1e+04]
Objective range [6e+00, 4e+01]
Objective range [6e+00, 4e+01]
Bounds range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 4e+04]
RHS range [1e+00, 4e+04]
Presolve removed 112 rows and 57 columns
Presolve removed 112 rows and 57 columns
Presolve time: 0.01s
Presolve time: 0.01s
Presolved: 342 rows, 579 columns, 5227 nonzeros
Presolved: 342 rows, 579 columns, 5227 nonzeros
Variable types: 0 continuous, 579 integer (573 binary)
Variable types: 0 continuous, 579 integer (573 binary)
Root relaxation: objective 1.342604e+02, 116 iterations, 0.00 seconds
Root relaxation: objective 1.342604e+02, 116 iterations, 0.00 seconds
Nodes  Current Node  Objective Bounds  Work
Nodes  Current Node  Objective Bounds  Work
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time
0 0 134.26040 0 11  134.26040   0s
0 0 134.26040 0 11  134.26040   0s
0 0 133.98727 0 24  133.98727   0s
0 0 133.98727 0 24  133.98727   0s
0 0 133.96600 0 30  133.96600   0s
0 0 133.96600 0 30  133.96600   0s
0 0 133.96294 0 29  133.96294   0s
0 0 133.96294 0 29  133.96294   0s
0 0 133.63167 0 32  133.63167   0s
0 0 133.63167 0 32  133.63167   0s
0 0 133.62657 0 29  133.62657   0s
0 0 133.62657 0 29  133.62657   0s
0 0 133.59026 0 34  133.59026   0s
0 0 133.59026 0 34  133.59026   0s
0 0 133.57669 0 33  133.57669   0s
0 0 133.57669 0 33  133.57669   0s
0 0 133.57419 0 28  133.57419   0s
0 0 133.57419 0 28  133.57419   0s
0 0 133.36479 0 38  133.36479   0s
0 0 133.36479 0 38  133.36479   0s
0 0 133.34444 0 36  133.34444   0s
0 0 133.34444 0 36  133.34444   0s
0 0 133.30888 0 41  133.30888   0s
0 0 133.30888 0 41  133.30888   0s
0 0 133.30888 0 44  133.30888   0s
0 0 133.30888 0 44  133.30888   0s
0 0 133.21187 0 48  133.21187   0s
0 0 133.21187 0 48  133.21187   0s
0 0 133.20319 0 49  133.20319   0s
0 0 133.20319 0 49  133.20319   0s
0 0 133.09729 0 47  133.09729   0s
0 0 133.09729 0 47  133.09729   0s
0 0 133.08628 0 55  133.08628   0s
0 0 133.08628 0 55  133.08628   0s
0 0 133.05674 0 50  133.05674   0s
0 0 133.05674 0 50  133.05674   0s
0 0 133.05638 0 53  133.05638   0s
0 0 133.05638 0 53  133.05638   0s
0 0 133.01550 0 38  133.01550   0s
0 0 133.01550 0 38  133.01550   0s
0 0 133.00752 0 57  133.00752   0s
0 0 133.00752 0 57  133.00752   0s
0 0 133.00044 0 51  133.00044   0s
0 0 133.00044 0 51  133.00044   0s
0 0 132.94045 0 56  132.94045   0s
0 0 132.94045 0 56  132.94045   0s
0 0 132.92884 0 53  132.92884   0s
0 0 132.92884 0 53  132.92884   0s
0 0 132.92760 0 55  132.92760   0s
0 0 132.92760 0 55  132.92760   0s
H 0 0 125.2300000 132.92760 6.15%  0s
H 0 0 125.2300000 132.92760 6.15%  0s
0 0 132.91178 0 57 125.23000 132.91178 6.13%  0s
0 0 132.91178 0 57 125.23000 132.91178 6.13%  0s
0 0 132.91178 0 57 125.23000 132.91178 6.13%  0s
0 0 132.91178 0 57 125.23000 132.91178 6.13%  0s
0 0 132.88077 0 51 125.23000 132.88077 6.11%  0s
0 0 132.88077 0 51 125.23000 132.88077 6.11%  0s
0 0 132.88009 0 51 125.23000 132.88009 6.11%  0s
0 0 132.88009 0 51 125.23000 132.88009 6.11%  0s
0 0 132.84317 0 52 125.23000 132.84317 6.08%  0s
0 0 132.84317 0 52 125.23000 132.84317 6.08%  0s
0 0 132.83714 0 50 125.23000 132.83714 6.07%  0s
0 0 132.83714 0 50 125.23000 132.83714 6.07%  0s
0 0 132.82331 0 51 125.23000 132.82331 6.06%  0s
0 0 132.82331 0 51 125.23000 132.82331 6.06%  0s
0 0 132.82295 0 59 125.23000 132.82295 6.06%  0s
0 0 132.82295 0 59 125.23000 132.82295 6.06%  0s
H 0 0 128.1000000 132.82295 3.69%  0s
H 0 0 128.1000000 132.82295 3.69%  0s
0 0 132.79760 0 52 128.10000 132.79760 3.67%  0s
0 0 132.79760 0 52 128.10000 132.79760 3.67%  0s
0 0 132.79429 0 57 128.10000 132.79429 3.66%  0s
0 0 132.79429 0 57 128.10000 132.79429 3.66%  0s
0 0 132.79351 0 61 128.10000 132.79351 3.66%  0s
0 0 132.79351 0 61 128.10000 132.79351 3.66%  0s
0 0 132.70241 0 47 128.10000 132.70241 3.59%  0s
0 0 132.70241 0 47 128.10000 132.70241 3.59%  0s
0 0 132.67471 0 55 128.10000 132.67471 3.57%  0s
0 0 132.67471 0 55 128.10000 132.67471 3.57%  0s
0 0 132.65292 0 56 128.10000 132.65292 3.55%  0s
0 0 132.65292 0 56 128.10000 132.65292 3.55%  0s
0 0 132.65140 0 50 128.10000 132.65140 3.55%  0s
0 0 132.65140 0 50 128.10000 132.65140 3.55%  0s
0 0 132.64949 0 56 128.10000 132.64949 3.55%  0s
0 0 132.64949 0 56 128.10000 132.64949 3.55%  0s
0 0 132.56110 0 52 128.10000 132.56110 3.48%  0s
0 0 132.56110 0 52 128.10000 132.56110 3.48%  0s
0 0 132.54775 0 50 128.10000 132.54775 3.47%  0s
0 0 132.54775 0 50 128.10000 132.54775 3.47%  0s
0 0 132.54775 0 51 128.10000 132.54775 3.47%  0s
0 0 132.54775 0 51 128.10000 132.54775 3.47%  0s
0 0 132.48633 0 42 128.10000 132.48633 3.42%  0s
0 0 132.48633 0 42 128.10000 132.48633 3.42%  0s
0 0 132.44941 0 46 128.10000 132.44941 3.40%  0s
0 0 132.44941 0 46 128.10000 132.44941 3.40%  0s
0 0 132.44316 0 51 128.10000 132.44316 3.39%  0s
0 0 132.44316 0 51 128.10000 132.44316 3.39%  0s
0 0 132.44316 0 51 128.10000 132.44316 3.39%  0s
0 0 132.44316 0 51 128.10000 132.44316 3.39%  0s
0 0 132.38775 0 53 128.10000 132.38775 3.35%  0s
0 0 132.38775 0 53 128.10000 132.38775 3.35%  0s
0 0 132.32449 0 51 128.10000 132.32449 3.30%  0s
0 0 132.32449 0 51 128.10000 132.32449 3.30%  0s
0 0 132.31483 0 42 128.10000 132.31483 3.29%  0s
0 0 132.31483 0 42 128.10000 132.31483 3.29%  0s
0 0 132.31483 0 41 128.10000 132.31483 3.29%  0s
0 0 132.31483 0 41 128.10000 132.31483 3.29%  0s
0 0 132.24221 0 34 128.10000 132.24221 3.23%  0s
0 0 132.24221 0 34 128.10000 132.24221 3.23%  0s
H 0 0 129.4000000 132.24221 2.20%  0s
H 0 0 129.4000000 132.24221 2.20%  0s
0 0 132.21859 0 49 129.40000 132.21859 2.18%  0s
0 0 132.21859 0 49 129.40000 132.21859 2.18%  0s
0 0 132.20545 0 48 129.40000 132.20545 2.17%  0s
0 0 132.20545 0 48 129.40000 132.20545 2.17%  0s
0 0 132.20545 0 50 129.40000 132.20545 2.17%  0s
0 0 132.20545 0 50 129.40000 132.20545 2.17%  0s
0 0 132.18375 0 47 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 47 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 10 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 10 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 24 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 24 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 22 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 22 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 33 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 33 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 36 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 36 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 46 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 46 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 45 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 45 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 44 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 44 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 35 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 35 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 53 129.40000 132.18375 2.15%  0s
0 0 132.18375 0 53 129.40000 132.18375 2.15%  0s
0 0 132.17844 0 54 129.40000 132.17844 2.15%  0s
0 0 132.17844 0 54 129.40000 132.17844 2.15%  0s
0 0 132.16137 0 53 129.40000 132.16137 2.13%  0s
0 0 132.16137 0 53 129.40000 132.16137 2.13%  0s
0 0 132.14470 0 51 129.40000 132.14470 2.12%  0s
0 0 132.14470 0 51 129.40000 132.14470 2.12%  0s
0 0 132.14039 0 51 129.40000 132.14039 2.12%  0s
0 0 132.14039 0 51 129.40000 132.14039 2.12%  0s
0 0 132.13331 0 50 129.40000 132.13331 2.11%  0s
0 0 132.13331 0 50 129.40000 132.13331 2.11%  0s
0 0 132.12804 0 58 129.40000 132.12804 2.11%  0s
0 0 132.12804 0 58 129.40000 132.12804 2.11%  0s
0 0 132.12724 0 55 129.40000 132.12724 2.11%  0s
0 0 132.12724 0 55 129.40000 132.12724 2.11%  0s
0 0 132.12724 0 55 129.40000 132.12724 2.11%  0s
0 0 132.12724 0 55 129.40000 132.12724 2.11%  0s
0 2 132.12724 0 55 129.40000 132.12724 2.11%  0s
0 2 132.12724 0 55 129.40000 132.12724 2.11%  0s
H 138 20 129.5900000 131.62082 1.57% 23.7 0s
H 138 20 129.5900000 131.62082 1.57% 23.7 0s
Cutting planes:
Cutting planes:
Gomory: 2
Gomory: 2
Cover: 21
Cover: 21
Clique: 1
Clique: 1
MIR: 21
MIR: 21
StrongCG: 1
StrongCG: 1
GUB cover: 15
GUB cover: 15
Zero half: 1
Zero half: 1
ModK: 1
ModK: 1
Explored 208 nodes (6359 simplex iterations) in 0.40 seconds
Explored 208 nodes (6359 simplex iterations) in 0.40 seconds
Thread count was 12 (of 12 available processors)
Thread count was 12 (of 12 available processors)
Solution count 4: 129.59 129.4 128.1 125.23
Solution count 4: 129.59 129.4 128.1 125.23
Optimal solution found (tolerance 1.00e04)
Optimal solution found (tolerance 1.00e04)
Best objective 1.295900000000e+02, best bound 1.295900000000e+02, gap 0.0000%
Best objective 1.295900000000e+02, best bound 1.295900000000e+02, gap 0.0000%
However, here is the log for the 145th solution:
Optimize a model with 598 rows, 636 columns and 10343 nonzeros
Variable types: 0 continuous, 636 integer (0 binary)
Variable types: 0 continuous, 636 integer (0 binary)
Coefficient statistics:
Coefficient statistics:
Matrix range [1e+00, 1e+04]
Matrix range [1e+00, 1e+04]
Objective range [6e+00, 4e+01]
Objective range [6e+00, 4e+01]
Bounds range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 4e+04]
RHS range [1e+00, 4e+04]
Presolve removed 112 rows and 57 columns
Presolve removed 112 rows and 57 columns
Presolve time: 0.02s
Presolve time: 0.02s
Presolved: 486 rows, 579 columns, 8575 nonzeros
Presolved: 486 rows, 579 columns, 8575 nonzeros
Variable types: 0 continuous, 579 integer (573 binary)
Variable types: 0 continuous, 579 integer (573 binary)
Root relaxation: objective 1.340784e+02, 134 iterations, 0.00 seconds
Root relaxation: objective 1.340784e+02, 134 iterations, 0.00 seconds
Nodes  Current Node  Objective Bounds  Work
Nodes  Current Node  Objective Bounds  Work
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time
0 0 134.07840 0 11  134.07840   0s
0 0 134.07840 0 11  134.07840   0s
0 0 133.93259 0 21  133.93259   0s
0 0 133.93259 0 21  133.93259   0s
0 0 133.85000 0 9  133.85000   0s
0 0 133.85000 0 9  133.85000   0s
0 0 133.85000 0 5  133.85000   0s
0 0 133.85000 0 5  133.85000   0s
0 0 133.68976 0 26  133.68976   0s
0 0 133.68976 0 26  133.68976   0s
0 0 133.60845 0 31  133.60845   0s
0 0 133.60845 0 31  133.60845   0s
0 0 133.60507 0 39  133.60507   0s
0 0 133.60507 0 39  133.60507   0s
0 0 133.60407 0 39  133.60407   0s
0 0 133.60407 0 39  133.60407   0s
0 0 133.57196 0 44  133.57196   0s
0 0 133.57196 0 44  133.57196   0s
0 0 133.56602 0 50  133.56602   0s
0 0 133.56602 0 50  133.56602   0s
0 0 133.56527 0 54  133.56527   0s
0 0 133.56527 0 54  133.56527   0s
0 0 133.56507 0 51  133.56507   0s
0 0 133.56507 0 51  133.56507   0s
0 0 133.45246 0 42  133.45246   0s
0 0 133.45246 0 42  133.45246   0s
0 0 133.44992 0 54  133.44992   0s
0 0 133.44992 0 54  133.44992   0s
0 0 133.43458 0 48  133.43458   0s
0 0 133.43458 0 48  133.43458   0s
0 0 133.42678 0 49  133.42678   0s
0 0 133.42678 0 49  133.42678   0s
0 0 133.42362 0 53  133.42362   0s
0 0 133.42362 0 53  133.42362   0s
0 0 133.35882 0 52  133.35882   0s
0 0 133.35882 0 52  133.35882   0s
0 0 133.31425 0 59  133.31425   0s
0 0 133.31425 0 59  133.31425   0s
0 0 133.30892 0 58  133.30892   0s
0 0 133.30892 0 58  133.30892   0s
0 0 133.30863 0 59  133.30863   0s
0 0 133.30863 0 59  133.30863   0s
0 0 133.12048 0 61  133.12048   0s
0 0 133.12048 0 61  133.12048   0s
0 0 133.09187 0 57  133.09187   0s
0 0 133.09187 0 57  133.09187   0s
0 0 133.09187 0 57  133.09187   0s
0 0 133.09187 0 57  133.09187   0s
0 0 133.03783 0 63  133.03783   0s
0 0 133.03783 0 63  133.03783   0s
0 0 133.02969 0 65  133.02969   0s
0 0 133.02969 0 65  133.02969   0s
0 0 133.02969 0 65  133.02969   0s
0 0 133.02969 0 65  133.02969   0s
0 0 132.99712 0 65  132.99712   0s
0 0 132.99712 0 65  132.99712   0s
0 0 132.96985 0 65  132.96985   0s
0 0 132.96985 0 65  132.96985   0s
0 0 132.96839 0 69  132.96839   0s
0 0 132.96839 0 69  132.96839   0s
0 0 132.96822 0 72  132.96822   0s
0 0 132.96822 0 72  132.96822   0s
0 0 132.93795 0 63  132.93795   0s
0 0 132.93795 0 63  132.93795   0s
0 0 132.93702 0 66  132.93702   0s
0 0 132.93702 0 66  132.93702   0s
0 0 132.93637 0 70  132.93637   0s
0 0 132.93637 0 70  132.93637   0s
0 0 132.93502 0 72  132.93502   0s
0 0 132.93502 0 72  132.93502   0s
0 0 132.92567 0 58  132.92567   0s
0 0 132.92567 0 58  132.92567   0s
0 0 132.92338 0 66  132.92338   0s
0 0 132.92338 0 66  132.92338   0s
0 0 132.92338 0 67  132.92338   0s
0 0 132.92338 0 67  132.92338   0s
0 0 132.92035 0 70  132.92035   0s
0 0 132.92035 0 70  132.92035   0s
0 0 132.92035 0 70  132.92035   0s
0 0 132.92035 0 70  132.92035   0s
0 0 132.92035 0 66  132.92035   0s
0 0 132.92035 0 66  132.92035   0s
0 2 132.92035 0 66  132.92035   0s
0 2 132.92035 0 66  132.92035   0s
4909 1362 124.74267 28 46  128.39550  22.5 5s
4909 1362 124.74267 28 46  128.39550  22.5 5s
30532 5260 114.16815 34 28  122.79051  28.8 10s
30532 5260 114.16815 34 28  122.79051  28.8 10s
H40003 4965 109.6700000 120.85154 10.2% 28.9 11s
H40003 4965 109.6700000 120.85154 10.2% 28.9 11s
53240 1220 cutoff 43 109.67000 115.87500 5.66% 27.6 15s
53240 1220 cutoff 43 109.67000 115.87500 5.66% 27.6 15s
Cutting planes:
Cutting planes:
Gomory: 3
Gomory: 3
Cover: 14
Cover: 14
Clique: 16
Clique: 16
MIR: 6
MIR: 6
Flow cover: 59
Flow cover: 59
GUB cover: 24
GUB cover: 24
Inf proof: 1
Inf proof: 1
Zero half: 13
Zero half: 13
Explored 55413 nodes (1522483 simplex iterations) in 15.82 seconds
Explored 55413 nodes (1522483 simplex iterations) in 15.82 seconds
Thread count was 12 (of 12 available processors)
Thread count was 12 (of 12 available processors)
Solution count 1: 109.67
Solution count 1: 109.67
Optimal solution found (tolerance 1.00e04)
Optimal solution found (tolerance 1.00e04)
Best objective 1.096700000000e+02, best bound 1.096700000000e+02, gap 0.0000%
Best objective 1.096700000000e+02, best bound 1.096700000000e+02, gap 0.0000%
Maybe this can't be improved, but any suggestions or pointers to improve this if possible would be greatly appreciated. And if anything is unclear, please let me know so I can clarify.
Thanks,
Curt

Hi Curt,
If I understand "cosmetic variations" correctly I'd have a look at symmetry breaking constraints. Maybe this helps you to get solutions that are really different from a functional point of view.
I also noticed that you start with integer variables but gurobi is able to convert almost all of them to binary ones. Maybe you can have a look at your model and check if you can reformulate it a bit using only binary variables.
How do you model the variety of the solution using the parameter k? I could think of some ways but it would be nice to hear your approach.
0 
Hi Curt,
One question, I guess that the constraints that you are adding are of the form:
sum(x_ix'_i : i in important set) >= k
where x_i are binary? or are you dealing with integer variables as well? The short snippet of log you share don't point to obviously large coefficients either... but it could be that you have a lot of epsilonsimilar coefficients? Now, if you are forbidding previous solutions, then warmstart has very little chance of helping (as the previous solution would be infeasible by design), now, if you do have a feasible solution for each successive iteration, that should help
Let me know if this helps
0 
Hey Daniel,
Yes, your assessment that the x_i variables are binary is correct and no I'm not dealing with integer variables at all.
I'm not quite sure what epsilon similar coefficients are  can you explain? I could actually post the MIP if that would help  should I do that? If epsilon similar means the coefficients pertaining to the x_i's are similar below some epsilon, I would say that the coefficients range from 612 with indeed some of the coefficients being very close (e.g. maybe 9.5 and 9.6).
Unfortunately, I don't have a feasible solution to aid with warm start, only the prior and now invalid solution.
What type of Gurobi parameters would you suggest tuning in this scenario, if any?
Thanks,
Curt0 
Hi Curt,
If I'm not mistaken, you could use a partial (old) solution and try to feed it to gurobi as a start solution. Maybe your knowledge can help you to decide which variables should be the same as in the old solution and which ones you set to undefined. If this is not possible maybe just randomized selection of variables might sill be possible.
A concrete example is always beneficial, so if you can post an example here, it would be great.
A difference of 0.1 should pose no problem. Note that relative numbers are more relevant for tolerances than absolute ones.
0 
Hi Curt,
What I mean is that you can have constraints like
x1 + x2 <= 1
1.00001x1 + 0.99999x2 >= 1.00001
which by themselves are fine.... but where they induce a very thin feasible region (and a large condition number for the system of equations). Now, if you are talking 9.5 and 9.6 as coefficients for same variables.... that shouldn't be too bad. As Jacob also suggested, giving some incomplete mipstarts and/or a trivially valid (but never optimal) solution to start with should also help. Finally, for tuning, there is the tuning tool grbtune still, please spend some time reading the guide about tuning.
Daniel
0
Please sign in to leave a comment.
Comments
5 comments