Solving a very Large QIP
Answered
Dear Gurobi Team,
Hope you are well. I am trying to solve a large QIP and have been running it for quite some time without much improvement in the optimality gap. Would you be able to take a look at the model please? Here is an incumbent solution. Thanks.
Set parameter WLSAccessID
Set parameter WLSSecret
Set parameter LicenseID to value 2500418
Academic license 2500418 - for non-commercial use only - registered to dl___@columbia.edu
Building model..
Set parameter BarHomogeneous to value 1
Set parameter Method to value 2
Set parameter NumericFocus to value 3
Set parameter Presolve to value 2
Set parameter Crossover to value 0
Set parameter DualReductions to value 0
Set parameter Heuristics to value 0.25
Set parameter MIPGap to value 0.05
Solving model..
Reading incumbent solution..
Read solution from file incumbent_23_24.sol
Gurobi Optimizer version 11.0.2 build v11.0.2rc0 (linux64 - "Ubuntu 22.04.2 LTS")
CPU model: AMD EPYC-Milan Processor, instruction set [SSE2|AVX|AVX2]
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Academic license 2500418 - for non-commercial use only - registered to dl___@columbia.edu
Optimize a model with 795003 rows, 463140 columns and 4205700 nonzeros
Model fingerprint: 0x70578d92
Model has 4296600 quadratic objective terms
Variable types: 0 continuous, 463140 integer (313740 binary)
Coefficient statistics:
Matrix range [3e-01, 2e+00]
Objective range [0e+00, 0e+00]
QObjective range [1e-02, 5e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+03]
Loaded user MIP start with objective 1247.18
Presolve removed 591085 rows and 239684 columns (presolve time = 5s) ...
Presolve removed 591085 rows and 240422 columns (presolve time = 10s) ...
Presolve removed 694612 rows and 311386 columns (presolve time = 44s) ...
Presolve removed 694552 rows and 311326 columns
Presolve time: 43.73s
Presolved: 149910 rows, 201273 columns, 2724581 nonzeros
Variable types: 49368 continuous, 151905 integer (139648 binary)
Root relaxation presolved: 132148 rows, 196288 columns, 2689005 nonzeros
Root barrier log...
Ordering time: 5.23s
Barrier statistics:
AA' NZ : 4.005e+06
Factor NZ : 2.678e+07 (roughly 350 MB of memory)
Factor Ops : 1.755e+10 (less than 1 second per iteration)
Threads : 8
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 4.61769951e+08 -3.45806555e+08 2.09e+07 4.83e+00 6.19e+05 92s
1 2.63441405e+08 -3.98289936e+08 1.14e+07 1.79e+02 3.27e+05 92s
2 7.39822930e+07 -4.41523620e+08 3.10e+06 2.73e-12 9.21e+04 93s
3 9.81774291e+06 -4.23938714e+08 3.59e+05 3.58e-12 1.12e+04 94s
4 2.34902662e+06 -4.07600914e+07 4.16e+04 6.46e-13 2.93e+02 95s
5 1.31602332e+06 -4.66365860e+06 6.79e+03 3.33e-13 2.55e+01 96s
6 5.67952491e+05 -1.09284694e+06 2.58e+03 1.68e-13 6.36e+00 97s
7 1.16043450e+05 -4.61587348e+05 8.47e+02 1.17e-13 1.81e+00 98s
8 3.65705449e+04 -1.80150677e+05 3.52e+02 5.50e-14 5.72e-01 99s
9 1.58346047e+04 -6.72650258e+04 1.80e+02 4.19e-14 2.01e-01 100s
10 6.78335578e+03 -3.47062409e+04 6.91e+01 2.23e-14 8.99e-02 100s
11 2.63141743e+03 -1.19158148e+04 1.44e+01 2.02e-14 2.92e-02 101s
12 1.46969908e+03 -4.03784694e+03 4.00e+00 5.05e-14 1.08e-02 102s
13 9.93993390e+02 -2.17261784e+03 2.08e+00 4.23e-14 6.20e-03 103s
14 8.03315308e+02 -1.53743387e+03 1.60e+00 3.36e-14 4.59e-03 104s
15 6.22643944e+02 -1.06919263e+03 1.18e+00 5.70e-14 3.31e-03 105s
16 4.66979584e+02 -6.54167762e+02 8.43e-01 1.30e-13 2.20e-03 106s
17 3.06228073e+02 -3.43365439e+02 5.11e-01 1.86e-13 1.27e-03 107s
18 2.27020637e+02 -1.74020216e+02 3.55e-01 3.02e-13 7.89e-04 108s
19 1.68659082e+02 -1.04317575e+02 2.46e-01 4.65e-13 5.37e-04 109s
20 1.35393288e+02 -7.35780513e+01 1.86e-01 5.71e-13 4.11e-04 110s
21 1.07413942e+02 -4.50660695e+01 1.35e-01 4.16e-13 3.00e-04 111s
22 8.04549769e+01 -2.54651971e+01 8.66e-02 6.35e-13 2.08e-04 113s
23 6.08086108e+01 -5.33572752e-01 5.14e-02 1.23e-12 1.20e-04 114s
24 5.03953797e+01 1.00273972e+01 3.34e-02 5.08e-12 7.92e-05 116s
25 4.47154641e+01 1.65618828e+01 2.35e-02 3.99e-12 5.53e-05 117s
26 4.19100921e+01 1.93214541e+01 1.88e-02 2.94e-12 4.43e-05 118s
27 3.95829511e+01 2.20292097e+01 1.49e-02 4.48e-12 3.45e-05 119s
28 3.75772021e+01 2.44424556e+01 1.16e-02 8.85e-12 2.58e-05 120s
29 3.52375726e+01 2.64148444e+01 7.71e-03 1.16e-11 1.73e-05 122s
30 3.37181364e+01 2.80020255e+01 5.23e-03 1.95e-11 1.12e-05 124s
31 3.24462543e+01 2.91135490e+01 3.13e-03 2.97e-11 6.56e-06 126s
32 3.17899531e+01 2.94145913e+01 2.07e-03 3.16e-11 4.67e-06 128s
33 3.14691525e+01 2.97368581e+01 1.54e-03 5.40e-11 3.41e-06 129s
34 3.12205402e+01 2.99389439e+01 1.14e-03 1.20e-10 2.52e-06 131s
35 3.10448202e+01 3.00991208e+01 8.53e-04 1.07e-10 1.86e-06 133s
36 3.09846543e+01 3.01395040e+01 7.54e-04 1.12e-10 1.66e-06 136s
37 3.07612539e+01 3.02838640e+01 3.90e-04 4.46e-10 9.36e-07 139s
38 3.06798047e+01 3.03590239e+01 2.59e-04 3.34e-10 6.29e-07 145s
39 3.06206406e+01 3.04025444e+01 1.63e-04 4.58e-10 4.27e-07 148s
40 3.05925574e+01 3.04429049e+01 1.17e-04 1.05e-09 2.93e-07 149s
41 3.05750094e+01 3.04701873e+01 8.77e-05 1.58e-09 2.06e-07 151s
42 3.05520266e+01 3.04833522e+01 4.98e-05 1.49e-09 1.34e-07 153s
43 3.05373304e+01 3.04969425e+01 2.55e-05 3.03e-09 7.88e-08 154s
44 3.05294770e+01 3.05037388e+01 1.26e-05 4.89e-09 5.01e-08 156s
45 3.05253102e+01 3.05113687e+01 5.76e-06 1.80e-08 2.71e-08 157s
46 3.05235411e+01 3.05191131e+01 2.92e-06 5.98e-08 8.65e-09 159s
47 3.05219989e+01 3.05211577e+01 5.03e-07 2.72e-08 1.64e-09 160s
48 3.05217335e+01 3.05215959e+01 8.95e-08 7.79e-08 2.68e-10 163s
49 3.05216836e+01 3.05216678e+01 1.19e-08 6.25e-08 3.10e-11 164s
50 3.05216771e+01 3.05216751e+01 1.09e-08 2.31e-08 3.88e-12 167s
51 3.05216763e+01 3.05216758e+01 6.99e-08 4.69e-09 9.74e-13 169s
52 3.05216759e+01 3.05216759e+01 6.28e-09 6.55e-10 1.02e-13 171s
Barrier solved model in 52 iterations and 170.65 seconds (147.78 work units)
Optimal objective 3.05216759e+01
Root crossover log...
31267 DPushes remaining with DInf 0.0000000e+00 172s
8897 DPushes remaining with DInf 0.0000000e+00 176s
0 DPushes remaining with DInf 0.0000000e+00 177s
41485 PPushes remaining with PInf 1.7814625e-05 177s
7834 PPushes remaining with PInf 0.0000000e+00 180s
5481 PPushes remaining with PInf 0.0000000e+00 185s
3536 PPushes remaining with PInf 0.0000000e+00 190s
1802 PPushes remaining with PInf 0.0000000e+00 195s
139 PPushes remaining with PInf 0.0000000e+00 200s
0 PPushes remaining with PInf 0.0000000e+00 201s
Push phase complete: Pinf 0.0000000e+00, Dinf 4.9105466e-15 201s
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
56459 3.0521676e+01 0.000000e+00 0.000000e+00 201s
56459 3.0521676e+01 0.000000e+00 0.000000e+00 201s
Root relaxation: objective 3.052168e+01, 56459 iterations, 120.35 seconds (108.14 work units)
Total elapsed time = 201.66s (DegenMoves)
Total elapsed time = 1139.25s (DegenMoves)
Total elapsed time = 1780.58s (DegenMoves)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 30.52168 0 10601 1247.17530 30.52168 97.6% - 1782s
0 2 30.52168 0 9476 1247.17530 30.52168 97.6% - 5810s
1 5 30.52168 1 8883 1247.17530 30.52168 97.6% 464469 6067s
3 8 30.52311 2 9077 1247.17530 30.52168 97.6% 169462 6502s
7 16 31.16604 3 9052 1247.17530 30.52311 97.6% 88849 6781s
15 24 31.16604 4 9269 1247.17530 31.16604 97.5% 57926 7208s
...
131824 91628 120.81637 2738 11091 1245.08085 31.79918 97.4% 8322 5203088s
132533 92078 121.02682 2782 11029 1245.08085 31.79918 97.4% 8321 5229084s
133235 92343 121.16793 2831 11083 1245.08085 31.79918 97.4% 8319 5254292s
133742 92830 122.31757 2859 11042 1245.08085 31.79918 97.4% 8317 5277270s
134408 93207 122.33962 2884 11085 1245.08085 31.79918 97.4% 8315 5299701s
135012 93781 123.35424 2922 11006 1245.08085 31.79918 97.4% 8313 5321635s
135787 94218 123.59869 2971 11009 1245.08085 31.79918 97.4% 8303 5344634s
136443 93999 74.80345 519 11991 1245.08085 31.79918 97.4% 8290 5344635s
136486 94691 124.99935 3009 10888 1245.08085 31.79918 97.4% 8294 5366197s
137200 95174 125.65940 3050 11001 1245.08085 31.79918 97.4% 8285 5388103s
137927 95582 128.07618 3099 10834 1245.08085 31.79918 97.4% 8269 5409237s
-
Hi Derek,
Your objective has many terms of the form
sum constant_i * Locations[IND,PHI,127] * variable_i
Could you try reformulating the obejctive by introducing an additional auxiliary variable and equality constraint to get
aux_var = sum constant_i * variable_i
and then replace the above sum by
Locations[IND,PHI,127] * aux_var
Note that auxvar needs to be a free continuous variable. You can apply this to all such terms that you have. From what I see, you have this for constellation for every variable. After you apply the reformulation, could you please share the MPS/LP file?
In addition to the above reformulation, you might want to set DegenMoves=0. If you think that a the primal bound is not good enough, you might want to experiment with the NoRelHeurTime parameter.
Since you have many products with binary variable, you might also want to test the PreQLinearize parameter.
Best regards,
Jaromił0 -
Hi Jaromił,
Thanks for your response. Currently, the objective looks like the following (where `self.distances`, `self.teams`, and `self.timesteps` are arrays of constants, and `self.l` are the Locations[] variables):
obj = gp.quicksum(self.distances[k][j] * self.l[i, k, t - 1] * self.l[i, j, t] for t in self.timesteps[1:]
for j in self.teams for k in self.teams for i in self.teams if self.distances[k][j] > 1e-6)Would you have an idea of how to reformulate this per your description?
Kind regards,
Derek0 -
Hi Derek,
Would you have an idea of how to reformulate this per your description?
You could use the QuadExpr object and successively build up your objective function in a for-loop while adding auxiliary variables and equalities. Something like the following pseudo-code should give you an idea
obj = gp.QuadExpr(0)
outer for-loop:
aux_linexpr = gp.LinExpr(0)
inner for-loop to construct auxiliary linear expression
aux_linexpr.add(constant * variable)
aux_var = gp.addVar(lb=-GRB.INFINITY, name="auxvar")
model.addConstr(aux_linexpr == aux_var, "name="auxconstr")
obj.add(loopvariable * aux_var)
# possibly add some linear part to obj
model.setObjective(obj)Best regards,
Jaromił0 -
Thanks Jaromił. Please find the updated .mps file here (I've checked that the incumbent solution has the same objective as before).
Kind regards,
Derek0 -
Hi Derek,
The best settings I can see so far for the updated model are
- Method 2
- Crossover 0
- NodeMethod 2
- DegenMoves 0
- Presolve 2
- PreQLinearize 2
The first three parameters make sure that only the Barrier method is used to solve node relaxations. It looks like Simplex really struggles on this model. I don't have any good reason for why it is the case.
DegenMoves avoids a quite expensive feasible point heuristic which is performed right before the B&B tree. In your case, it is extraordinary expensive as it uses Simplex moves internally.
Presolve 2 activates more presolve reduction. This intuitively makes sense as your model is really big for a MIQCP.
PreQLinearize controls the way how products with binary variables are handled.
Please note that even with the above parameters, the model is far from convergence.
I think that only some reformulation or maybe additional constraints can help. Maybe our webinar on strong MIP formulations is helpful here.
Maybe you could try to perform some presolve yourself. If any such information is available, you could fix sets of decision variables to simplify the model.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
5 comments