MIQCP cannot improve incumbent and even cannot find any best bound
Awaiting user input
I’ve experimented with many parameter combinations, but I’m still encountering issues: the incumbent solution remains unchanged, the best bound isn't found, and the gap is large and difficult to close across different settings. I’ve attached my log file below and am uncertain about the next steps for improvement.
Set parameter Username
Academic license - for non-commercial use only - expires 2025-01-31
Set parameter NonConvex to value 2
Set parameter MinRelNodes to value 100
Set parameter MIPFocus to value 1
Set parameter Presolve to value 2
Set parameter PreQLinearize to value 2
Gurobi Optimizer version 11.0.3 build v11.0.3rc0 (mac64[rosetta2] - Darwin 24.0.0 24A348)
CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 12148 rows, 161 columns and 48738 nonzeros
Model fingerprint: 0x653dabce
Model has 1 quadratic objective term
Model has 3 quadratic constraints
Model has 11 general constraints
Variable types: 30 continuous, 131 integer (131 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+07]
QMatrix range [1e+00, 1e+00]
QLMatrix range [1e+00, 1e+00]
Objective range [0e+00, 0e+00]
QObjective range [2e+00, 2e+00]
Bounds range [1e-04, 1e+04]
RHS range [1e+00, 1e+07]
QRHS range [1e+00, 1e+00]
Presolve added 17 rows and 28 columns
Presolve time: 0.22s
Presolved: 12217 rows, 257 columns, 50040 nonzeros
Presolved model has 66 SOS constraint(s)
Presolved model has 2 bilinear constraint(s)
Warning: Model contains variables with very large bounds participating
in product terms.
Presolve was not able to compute smaller bounds for these variables.
Consider bounding these variables or reformulating the model.
Solving non-convex MIQCP
Variable types: 87 continuous, 170 integer (170 binary)
Root relaxation presolve removed 59 rows and 101 columns
Root relaxation: numerical trouble, 0 iterations, 0.01 seconds (0.00 work units)
Exploring 100 nodes in MinRel heuristic
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
H 0 0 -0.0000000 - - - 0s
Feasible solution found by MinRel heuristic at node 63
0 2 postponed 0 -0.00000 - - - 0s
* 177 149 13 500000.00000 - - 18.3 4s
214 144 1000000.00 15 18 500000.000 - - 22.1 6s
382 177 4000000.00 17 33 500000.000 - - 41.1 10s
820 275 5.1200e+08 21 33 500000.000 - - 29.9 15s
953 333 postponed 12 500000.000 - - 29.9 20s
1065 370 postponed 14 500000.000 - - 39.8 146s
1171 419 postponed 16 500000.000 - - 40.5 158s
1502 521 postponed 23 500000.000 - - 33.3 160s
1991 812 5.3687e+14 32 138 500000.000 - - 34.2 172s
2056 821 infeasible 34 500000.000 - - 34.5 276s
2119 850 infeasible 36 500000.000 - - 39.0 299s
2167 851 6.5536e+10 44 0 500000.000 - - 40.6 300s
2172 855 cutoff 15 500000.000 - - 41.0 313s
2174 857 postponed 16 500000.000 - - 41.5 316s
2180 865 2000000.00 18 40 500000.000 - - 42.2 339s
2188 868 2000000.00 19 26 500000.000 - - 42.8 342s
2286 903 2000000.00 27 11 500000.000 - - 41.5 345s
2524 978 1.6000e+07 26 34 500000.000 - - 39.2 350s
2729 1065 1.6000e+07 35 34 500000.000 - - 36.7 355s
2964 1148 3.2000e+07 21 29 500000.000 - - 35.0 360s
2989 1169 3.2000e+07 23 22 500000.000 - - 34.8 378s
3047 1206 3.2000e+07 28 33 500000.000 - - 34.6 380s
0
-
Hi,
The warning is shown in your log:
Warning: Model contains variables with very large bounds participating in product terms. Presolve was not able to compute smaller bounds for these variables. Consider bounding these variables or reformulating the model.
Are there any variables included in the quadratic constraints that have large upper and lower bounds or unset upper and lower bounds? It is recommended to make these Bounds as tight as possible. Also, the model numerics are not great mainly because the coefficient matrix has a wide range of 7 orders of magnitude. It might be a good idea to try to improve this value as well by scaling. This material may also be helpful: Tolerances and User-Scaling
Thanks,
Ryuta0 -
Thank you for your response. I made some adjustments and generated a new log. However, I’m now facing an issue where the best objective bound doesn’t improve, even after letting it run all day. I’ve done my best to tighten the bounds of the variables in the quadratic constraints and experimented with various parameter combinations but with no success. Could you offer some guidance on how to proceed?
Set parameter Username Academic license - for non-commercial use only - expires 2025-01-31 Set parameter NonConvex to value 2 Set parameter MIPFocus to value 1 Set parameter Cuts to value 0 Set parameter NoRelHeurTime to value 100 Set parameter NumericFocus to value 1 Gurobi Optimizer version 11.0.3 build v11.0.3rc0 (mac64[rosetta2] - Darwin 24.0.0 24A348) CPU model: Apple M1 Thread count: 8 physical cores, 8 logical processors, using up to 8 threads Optimize a model with 58 rows, 172 columns and 358 nonzeros Model fingerprint: 0x4b9afcb1 Model has 1 quadratic objective term Model has 13 quadratic constraints Model has 11 general constraints Variable types: 41 continuous, 131 integer (131 binary) Coefficient statistics: Matrix range [2e-01, 1e+06] QMatrix range [1e+00, 1e+00] QLMatrix range [1e+00, 1e+00] Objective range [0e+00, 0e+00] QObjective range [2e+00, 2e+00] Bounds range [1e-05, 1e+06] RHS range [1e+00, 1e+06] QRHS range [1e+00, 1e+02] Warning: Completing partial solution with 126 unfixed non-continuous variables out of 131 User MIP start produced solution with objective 10.2639 (0.08s) Loaded user MIP start with objective 10.2639 Presolve added 17 rows and 26 columns Presolve time: 0.02s Presolved: 336 rows, 562 columns, 1169 nonzeros Presolved model has 264 SOS constraint(s) Presolved model has 3 bilinear constraint(s) Solving non-convex MIQCP Variable types: 293 continuous, 269 integer (269 binary) Starting NoRel heuristic Found heuristic solution: objective 10.2826129 Found heuristic solution: objective 10.3708574 Found heuristic solution: objective 10.8006030 Found heuristic solution: objective 11.0077821 Found heuristic solution: objective 11.0922223 Found heuristic solution: objective 11.7555540 Found heuristic solution: objective 11.7591050 Found heuristic solution: objective 11.7617544 Elapsed time for NoRel heuristic: 5s (best bound 5e+07) Found heuristic solution: objective 11.7820470 Found heuristic solution: objective 11.7820514 Found heuristic solution: objective 11.7820566 Elapsed time for NoRel heuristic: 11s (best bound 5e+07) Elapsed time for NoRel heuristic: 16s (best bound 5e+07) Elapsed time for NoRel heuristic: 22s (best bound 5e+07) Found heuristic solution: objective 11.7820805 Elapsed time for NoRel heuristic: 28s (best bound 5e+07) Found heuristic solution: objective 11.7820936 Elapsed time for NoRel heuristic: 35s (best bound 5e+07) Elapsed time for NoRel heuristic: 42s (best bound 5e+07) Elapsed time for NoRel heuristic: 49s (best bound 5e+07) Elapsed time for NoRel heuristic: 54s (best bound 5e+07) Elapsed time for NoRel heuristic: 59s (best bound 5e+07) Elapsed time for NoRel heuristic: 66s (best bound 5e+07) Elapsed time for NoRel heuristic: 71s (best bound 5e+07) Elapsed time for NoRel heuristic: 76s (best bound 5e+07) Elapsed time for NoRel heuristic: 83s (best bound 5e+07) Elapsed time for NoRel heuristic: 89s (best bound 5e+07) Elapsed time for NoRel heuristic: 96s (best bound 5e+07) Found heuristic solution: objective 11.8523982 Found heuristic solution: objective 12.2484065 Root simplex log... Iteration Objective Primal Inf. Dual Inf. Time 0 1.2800000e+32 1.500000e+30 1.280000e+02 100s 206 5.0000050e+07 0.000000e+00 0.000000e+00 100s Root relaxation: objective 5.000005e+07, 206 iterations, 0.00 seconds (0.00 work units) Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time 0 0 5.0000e+07 0 28 12.24841 5.0000e+07 - - 100s 0 0 5.0000e+07 0 18 12.24841 5.0000e+07 - - 100s 0 0 5.0000e+07 0 18 12.24841 5.0000e+07 - - 100s 0 0 5.0000e+07 0 18 12.24841 5.0000e+07 - - 100s 0 0 5.0000e+07 0 18 12.24841 5.0000e+07 - - 100s 0 0 5.0000e+07 0 18 12.24841 5.0000e+07 - - 100s 0 0 5.0000e+07 0 18 12.24841 5.0000e+07 - - 100s 0 0 5.0000e+07 0 18 12.24841 5.0000e+07 - - 100s 0 0 5.0000e+07 0 18 12.24841 5.0000e+07 - - 100s 0 0 5.0000e+07 0 18 12.24841 5.0000e+07 - - 100s 0 0 5.0000e+07 0 18 12.24841 5.0000e+07 - - 100s 0 0 5.0000e+07 0 18 12.24841 5.0000e+07 - - 100s 0 2 5.0000e+07 0 18 12.24841 5.0000e+07 - - 100s H 1 4 12.2484127 5.0000e+07 - 0.0 100s H 9274 3796 12.2484142 5.0000e+07 - 6.3 102s H10912 4433 12.2484143 5.0000e+07 - 6.2 102s 27985 11580 infeasible 47 12.24841 5.0000e+07 - 5.6 105s H34185 13316 12.2484149 5.0000e+07 - 5.6 105s H38131 14899 12.2484151 5.0000e+07 - 5.5 106s H63979 24760 12.2484152 5.0000e+07 - 5.3 109s H65034 25063 12.3776444 5.0000e+07 - 5.3 109s 67059 25849 2180478.96 48 9 12.37764 5.0000e+07 - 5.3 110s H69484 26814 12.3776444 5.0000e+07 - 5.3 110s H89096 33610 12.4890769 5.0000e+07 - 5.2 112s H90244 34466 12.4890822 5.0000e+07 - 5.1 112s H91448 34817 12.4891104 5.0000e+07 - 5.1 112s 114153 43036 1.1756e+07 46 10 12.48911 5.0000e+07 - 5.0 115s H119961 44339 12.4891104 5.0000e+07 - 5.0 115s H133137 48726 12.4891104 5.0000e+07 - 5.0 117s H133306 48726 12.4891104 5.0000e+07 - 5.0 117s H133949 48726 12.4891104 5.0000e+07 - 5.0 117s H136212 49337 12.4891104 5.0000e+07 - 5.0 117s H138151 50043 12.4891105 5.0000e+07 - 5.0 117s H140616 50803 12.4891105 5.0000e+07 - 5.0 118s H141067 50803 12.4891105 5.0000e+07 - 5.0 118s H150396 53697 12.4891106 5.0000e+07 - 4.9 119s 152399 54174 1.4521e+07 37 8 12.48911 5.0000e+07 - 4.9 120s H161279 57424 12.4891106 5.0000e+07 - 4.9 120s 198249 71594 3.5077e+07 43 20 12.48911 5.0000e+07 - 5.0 125s H211018 75210 12.4891106 5.0000e+07 - 5.0 126s H225470 79581 12.4891532 5.0000e+07 - 5.1 127s H234939 82061 12.4891614 5.0000e+07 - 5.1 128s 244232 84861 2.0442e+07 49 15 12.48916 5.0000e+07 - 5.1 130s H271659 92975 12.4891614 5.0000e+07 - 5.1 132s 294143 100343 infeasible 45 12.48916 5.0000e+07 - 5.1 135s H295590 100844 12.4891616 5.0000e+07 - 5.1 135s H296633 100844 12.4891617 5.0000e+07 - 5.1 135s H300098 102117 12.4891619 5.0000e+07 - 5.1 135s H301180 102507 12.4892872 5.0000e+07 - 5.1 135s H304716 103736 12.4892872 5.0000e+07 - 5.1 136s H305865 103954 12.4892872 5.0000e+07 - 5.1 136s H306261 103954 12.4892872 5.0000e+07 - 5.1 136s H320404 108397 12.4892872 5.0000e+07 - 5.1 137s H321101 108778 12.4892874 5.0000e+07 - 5.1 137s H321436 108778 12.4892875 5.0000e+07 - 5.1 137s H329269 110829 12.4892876 5.0000e+07 - 5.1 138s H333166 111898 12.4892889 5.0000e+07 - 5.1 139s 340681 114438 7873841.14 48 15 12.48929 5.0000e+07 - 5.1 140s H344396 115480 12.4892924 5.0000e+07 - 5.1 140s H368317 122150 12.4893133 5.0000e+07 - 5.1 143s H369768 122548 12.4893657 5.0000e+07 - 5.1 143s 385461 127487 infeasible 33 12.48937 5.0000e+07 - 5.1 145s H407208 133251 12.4893657 5.0000e+07 - 5.1 147s H411981 134694 12.4893659 5.0000e+07 - 5.1 147s H413748 135432 12.4893661 5.0000e+07 - 5.1 148s 431378 141445 3774.07222 57 3 12.48937 5.0000e+07 - 5.1 150s H436063 142789 12.4893694 5.0000e+07 - 5.1 150s H443830 145586 12.4893695 5.0000e+07 - 5.1 151s H449049 147254 12.4893695 5.0000e+07 - 5.0 151s H452851 148985 12.4894859 5.0000e+07 - 5.0 152s H453699 148985 12.4894864 5.0000e+07 - 5.0 152s H460619 151086 12.4894864 5.0000e+07 - 5.0 153s H465470 153301 12.4898146 5.0000e+07 - 5.0 153s H467965 153903 12.4898150 5.0000e+07 - 5.0 154s 475465 156316 1.6407e+07 56 8 12.48981 5.0000e+07 - 5.0 155s 513897 167033 1977.69956 61 3 12.48981 5.0000e+07 - 5.0 160s 560168 179659 2.4405e+07 40 15 12.48981 5.0000e+07 - 4.9 165s 612117 196990 5.0000e+07 42 18 12.48981 5.0000e+07 - 5.0 170s H618092 198701 12.4898153 5.0000e+07 - 5.0 170s 656141 212734 1.3916e+07 35 17 12.48982 5.0000e+07 - 4.9 175s 703552 230044 infeasible 42 12.48982 5.0000e+07 - 4.9 180s 750658 245714 454584.206 57 8 12.48982 5.0000e+07 - 4.9 185s0 -
Hi,
Bounds are now computed. It's the first step!
Then, the value of the Incumbent solution(=12.48982) and the value of Bounds are far apart. Which value is assumed to be closer to objective function for your desired solution?- If the actual objective value of the solution is assumed to be close to the Bounds, it may be difficult to improve the acceptable solution significantly with this model. If you assign an actual expected solution to each variable (e.g., using Start), will that solution be accepted and is its objective function value calculated correctly?
- If the actual objective value of solution is assumed to be close to the Incumbent solution, then this model appears to be a very weak formulation. In this case, reformulation of the model may be useful. See the article: General modeling tips to improve a formulation
Thanks,
Ryuta0 -
Hi Xin Yu,
In addition to the recommendations made by Ryuta, could you maybe please share the model such that we could have a closer look? Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.
Best regards,
Jaromił0 -
Thank you so much for your recommendations!
Yes, I assume that the actual objective value of the solution is close to the incumbent solution. After reading the article you suggested, I realize my formulation is weak. So far, I haven't come up with an effective way to reformulate it, but I’ll keep working on it. Below, I've attached my model and the log file.
Additionally, I used the warm-up solution, and I've noticed two different behaviors. In constraint C0, which involves matrix multiplication, when I use
x[j] / 10000, the model accepts my initial warm-up solution and quickly finds better solutions. However, if I leave it asx[j], the model doesn’t accept the initial warm-up solution. I'm still unsure why this is happening.warm = [-2.572, -1.610, -1.319, -0.064, -0.144]
m = gp.Model()
#m.setParam('OutputFlag', 0)
n = 11
k = 5
m.setParam('TimeLimit', 180)
x = {}
for s in range(k):
x[s] = m.addVar(vtype='C', name="x[%s]"%(s), lb = -1000000,ub = 1000000)
c = {}
for i in range(n):
c[i] = m.addVar(vtype='C', name="c[%s]"%(i), lb = -1000000,ub = 1000000)
z = {}
for i in range(n):
z[i] = m.addVar(vtype='C', name="z[%s]"%(i), lb = 0.001,ub = 100000)
b = {}
for i in range(n):
for j in range(n):
b[i,j] = m.addVar(vtype='B', name="b[%s,%s]"%(i,j))
positive, negative = {}, {}
for j in range(k):
positive[j] = m.addVar(vtype='B', name="positive[%s]"%j)
negative[j] = m.addVar(vtype='B', name="negative[%s]"%j)
r = {}
t = m.addVar(vtype='C', name="t", lb = 0.00001, ub = 1000)
for i in range(n):
r[i] = m.addVar(vtype='C', name="r[%s]"%(i), lb = 0.001,ub = 100000)
m.update()
M = 1000
m.setObjective(r[0] * t, gp.GRB.MAXIMIZE)
for i in range(k):
x[i].Start = warm[i]
m.addConstr(t * r[3] == 1)
m.update()
for i in range(n):
m.addConstr(gp.quicksum(x[j]*g[j,i] for j in range(k)) == c[i], name = 'C0')
for j in range(k):
m.addConstr(x[j] >= 1e-3 - M * (1 - positive[j]), name = 'C1')
m.addConstr(x[j] <= -1e-3 + M * (1 - negative[j]), name = 'C2')
m.addConstr(positive[j] + negative[j] == 1, name = 'C3')
for i in range(n):
m.addConstr(z[i] == gp.abs_(c[i]), name='abs_c[%s]'%i)
for i in range(n):
m.addConstr(gp.quicksum(b[i,j] for j in range(n)) == 1, name = 'C8')
for j in range(n):
m.addConstr(gp.quicksum(b[i,j] for i in range(n)) == 1, name = 'C9')
for j in range(n):
m.addConstr(r[j] == gp.quicksum(z[i] * b[i,j] for i in range(n)), name = 'C10')
for j in range(n-1):
m.addConstr(r[j+1] <= r[j])
m.update()
m.update()
m.params.NonConvex = 2
m.params.MIPFocus = 2
#m.params.Cuts = 0
m.params.NoRelHeurTime = 50
#m.params.PreSparsify = -1
#m.params.NumericFocus = 1
m.optimize()
print(m.SolCount)Set parameter TimeLimit to value 180 Set parameter NonConvex to value 2 Set parameter MIPFocus to value 2 Set parameter NoRelHeurTime to value 50 Gurobi Optimizer version 11.0.3 build v11.0.3rc0 (mac64[rosetta2] - Darwin 24.0.0 24A348) CPU model: Apple M1 Thread count: 8 physical cores, 8 logical processors, using up to 8 threads Optimize a model with 58 rows, 170 columns and 358 nonzeros Model fingerprint: 0x2347c3bb Model has 1 quadratic objective term Model has 12 quadratic constraints Model has 11 general constraints Variable types: 39 continuous, 131 integer (131 binary) Coefficient statistics: Matrix range [1e+00, 1e+05] QMatrix range [1e+00, 1e+00] QLMatrix range [1e+00, 1e+00] Objective range [0e+00, 0e+00] QObjective range [2e+00, 2e+00] Bounds range [1e-05, 1e+06] RHS range [1e+00, 1e+03] QRHS range [1e+00, 1e+00] Warning: Completing partial solution with 131 unfixed non-continuous variables out of 131 User MIP start did not produce a new incumbent solution Presolve added 28 rows and 17 columns Presolve time: 0.01s Presolved: 345 rows, 551 columns, 1187 nonzeros Presolved model has 242 SOS constraint(s) Presolved model has 2 bilinear constraint(s) Solving non-convex MIQCP Variable types: 293 continuous, 258 integer (258 binary) Starting NoRel heuristic Found phase-1 solution: relaxation 1.04673e+07 Found phase-1 solution: relaxation 390.831 Found phase-1 solution: relaxation 220.212 Found phase-1 solution: relaxation 187.375 Found phase-1 solution: relaxation 173.082 Found phase-1 solution: relaxation 142.163 Found phase-1 solution: relaxation 134.557 Found phase-1 solution: relaxation 50.151 Found phase-1 solution: relaxation 14.4443 Found phase-1 solution: relaxation 0 Found heuristic solution: objective 0.0000000 Transition to phase 2 Found heuristic solution: objective 2.7751957 Found heuristic solution: objective 2.7980737 Found heuristic solution: objective 2.8481540 Found heuristic solution: objective 3.4671465 Found heuristic solution: objective 7.1965900 Found heuristic solution: objective 7.1965918 Found heuristic solution: objective 7.1965933 Found heuristic solution: objective 7.2386159 Elapsed time for NoRel heuristic: 5s (best bound 1e+08) Found heuristic solution: objective 7.7472518 Found heuristic solution: objective 8.9426985 Found heuristic solution: objective 9.5630493 Found heuristic solution: objective 9.6729848 Found heuristic solution: objective 9.6847377 Found heuristic solution: objective 9.7013254 Found heuristic solution: objective 10.1746778 Elapsed time for NoRel heuristic: 10s (best bound 1e+08) Found heuristic solution: objective 11.4044405 Found heuristic solution: objective 11.4044475 Found heuristic solution: objective 11.4797411 Found heuristic solution: objective 11.5762016 Found heuristic solution: objective 11.7487334 Found heuristic solution: objective 11.7487414 Elapsed time for NoRel heuristic: 15s (best bound 1e+08) Elapsed time for NoRel heuristic: 21s (best bound 1e+08) Elapsed time for NoRel heuristic: 27s (best bound 1e+08) Elapsed time for NoRel heuristic: 32s (best bound 1e+08) Elapsed time for NoRel heuristic: 37s (best bound 1e+08) Elapsed time for NoRel heuristic: 42s (best bound 1e+08) Found heuristic solution: objective 11.7487419 Found heuristic solution: objective 12.2760342 Elapsed time for NoRel heuristic: 48s (best bound 1e+08) Root relaxation presolve removed 292 rows and 409 columns Root relaxation presolved: 53 rows, 142 columns, 339 nonzeros Root simplex log... Iteration Objective Primal Inf. Dual Inf. Time 0 1.0000000e+08 3.737264e+06 0.000000e+00 51s 32 1.0000000e+08 0.000000e+00 0.000000e+00 51s 32 1.0000000e+08 0.000000e+00 0.000000e+00 51s Root relaxation: objective 1.000000e+08, 32 iterations, 0.02 seconds (0.00 work units) Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time 0 0 1.0000e+08 0 25 12.27603 1.0000e+08 - - 51s 0 0 1.0000e+08 0 28 12.27603 1.0000e+08 - - 51s 0 0 1.0000e+08 0 30 12.27603 1.0000e+08 - - 51s 0 0 1.0000e+08 0 32 12.27603 1.0000e+08 - - 51s 0 0 1.0000e+08 0 35 12.27603 1.0000e+08 - - 51s 0 0 1.0000e+08 0 38 12.27603 1.0000e+08 - - 51s 0 0 1.0000e+08 0 41 12.27603 1.0000e+08 - - 51s 0 0 1.0000e+08 0 44 12.27603 1.0000e+08 - - 51s 0 0 1.0000e+08 0 47 12.27603 1.0000e+08 - - 51s 0 0 1.0000e+08 0 50 12.27603 1.0000e+08 - - 51s Another try with MIP start 0 0 1.0000e+08 0 50 12.27603 1.0000e+08 - - 51s 0 0 1.0000e+08 0 61 12.27603 1.0000e+08 - - 51s 0 0 1.0000e+08 0 42 12.27603 1.0000e+08 - - 51s 0 0 1.0000e+08 0 26 12.27603 1.0000e+08 - - 51s 0 0 1.0000e+08 0 56 12.27603 1.0000e+08 - - 51s 0 0 1.0000e+08 0 23 12.27603 1.0000e+08 - - 51s 0 0 1.0000e+08 0 50 12.27603 1.0000e+08 - - 51s 0 0 1.0000e+08 0 25 12.27603 1.0000e+08 - - 51s 0 0 1.0000e+08 0 25 12.27603 1.0000e+08 - - 51s 0 2 1.0000e+08 0 25 12.27603 1.0000e+08 - - 51s H 4023 2049 12.2760349 1.0000e+08 - 9.6 52s H14491 6837 12.2760411 1.0000e+08 - 7.1 54s 21980 10821 3.4721e+07 48 14 12.27604 1.0000e+08 - 6.8 55s H36759 15714 12.2760412 1.0000e+08 - 6.5 57s 54544 22417 4.0314e+07 60 12 12.27604 1.0000e+08 - 6.8 60s 84360 32784 1.5540e+07 53 16 12.27604 1.0000e+08 - 7.0 65s H91706 35634 12.2760414 1.0000e+08 - 7.0 66s 110017 43308 2.7351e+07 47 17 12.27604 1.0000e+08 - 6.9 70s 130940 52020 7.2954e+07 61 15 12.27604 1.0000e+08 - 7.0 75s H136807 53429 12.2760414 1.0000e+08 - 7.1 76s 158084 61474 cutoff 62 12.27604 1.0000e+08 - 7.2 80s 187544 73747 infeasible 89 12.27604 1.0000e+08 - 7.2 85s 213088 83920 infeasible 66 12.27604 1.0000e+08 - 7.1 90s 236941 93816 1.0000e+08 42 14 12.27604 1.0000e+08 - 7.0 95s 259128 103968 1.0000e+08 55 16 12.27604 1.0000e+08 - 6.9 100s 283726 114925 infeasible 60 12.27604 1.0000e+08 - 6.9 105s H300238 121256 12.2760415 1.0000e+08 - 6.8 107s 310856 126134 2.2821e+07 61 13 12.27604 1.0000e+08 - 6.8 110s 334220 134400 infeasible 46 12.27604 1.0000e+08 - 6.9 115s 357891 142405 2.7155e+07 48 20 12.27604 1.0000e+08 - 7.0 120s 382207 152318 infeasible 50 12.27604 1.0000e+08 - 7.1 125s 407315 161446 1.0000e+08 47 7 12.27604 1.0000e+08 - 7.2 130s 432228 170268 infeasible 48 12.27604 1.0000e+08 - 7.3 135s 458743 179292 1.0000e+08 42 16 12.27604 1.0000e+08 - 7.4 140s 481497 187300 1.0000e+08 46 7 12.27604 1.0000e+08 - 7.4 145s 507659 195573 infeasible 65 12.27604 1.0000e+08 - 7.5 150s 532978 204235 5.0458e+07 64 22 12.27604 1.0000e+08 - 7.6 155s 556637 211834 963098.385 41 22 12.27604 1.0000e+08 - 7.7 160s 580165 219629 3.2758e+07 53 6 12.27604 1.0000e+08 - 7.8 165s 602324 227567 3.7447e+07 56 9 12.27604 1.0000e+08 - 7.8 170s 625684 233717 infeasible 55 12.27604 1.0000e+08 - 7.8 175s 647599 239956 infeasible 55 12.27604 1.0000e+08 - 7.8 180s Cutting planes: Gomory: 2 Cover: 7 Implied bound: 129 MIR: 12 Flow cover: 37 Inf proof: 1 Relax-and-lift: 1 Explored 647655 nodes (5059830 simplex iterations) in 180.01 seconds (117.56 work units) Thread count was 8 (of 8 available processors) Solution count 10: 12.276 12.276 12.276 ... 11.7487 Time limit reached Best objective 1.227604126225e+01, best bound 1.000000000000e+08, gap 814594750.7643% 100 -
Thank you for sharing the model. Unfortunately, you code runs into an error, because the dictionary \(\texttt{g}\) is not defined.
0 -
I apologize for the oversight! Thank you for pointing that out. I’ve attached the
garray in my updated model.g = np.array([ [-52132, -2437, -89683, 23721, 17470, 56906, -87388, -6704, -3640, -21389, -5672], [-18848, 81214, -81832, 27573, -29659, 76282, 49208, -13784, 4139, 37693, -48055], [-57201, -70755, -24017, -99533, 35845, -15988, 84777, 40056, -26800, -21139, 71576], [ -3242, -20108, 31311, -90271, -57992, 3842, 8302, -40082, 39925, 81538, -9366], [-91481, 19279, -78836, 9771, -41431, 31797, -10345, -88336, -26491, 83814, -91193] ])
warm = [-2.572, -1.610, -1.319, -0.064, -0.144]
m = gp.Model()
#m.setParam('OutputFlag', 0)
n = 11
k = 5
m.setParam('TimeLimit', 180)
x = {}
for s in range(k):
x[s] = m.addVar(vtype='C', name="x[%s]"%(s), lb = -1000000,ub = 1000000)
c = {}
for i in range(n):
c[i] = m.addVar(vtype='C', name="c[%s]"%(i), lb = -1000000,ub = 1000000)
z = {}
for i in range(n):
z[i] = m.addVar(vtype='C', name="z[%s]"%(i), lb = 0.001,ub = 100000)
b = {}
for i in range(n):
for j in range(n):
b[i,j] = m.addVar(vtype='B', name="b[%s,%s]"%(i,j))
positive, negative = {}, {}
for j in range(k):
positive[j] = m.addVar(vtype='B', name="positive[%s]"%j)
negative[j] = m.addVar(vtype='B', name="negative[%s]"%j)
r = {}
t = m.addVar(vtype='C', name="t", lb = 0.00001, ub = 1000)
for i in range(n):
r[i] = m.addVar(vtype='C', name="r[%s]"%(i), lb = 0.001,ub = 100000)
m.update()
M = 1000
m.setObjective(r[0] * t, gp.GRB.MAXIMIZE)
for i in range(k):
x[i].Start = warm[i]
m.addConstr(t * r[3] == 1)
m.update()
for i in range(n):
m.addConstr(gp.quicksum(x[j]*g[j,i] for j in range(k)) == c[i], name = 'C0')
for j in range(k):
m.addConstr(x[j] >= 1e-3 - M * (1 - positive[j]), name = 'C1')
m.addConstr(x[j] <= -1e-3 + M * (1 - negative[j]), name = 'C2')
m.addConstr(positive[j] + negative[j] == 1, name = 'C3')
for i in range(n):
m.addConstr(z[i] == gp.abs_(c[i]), name='abs_c[%s]'%i)
for i in range(n):
m.addConstr(gp.quicksum(b[i,j] for j in range(n)) == 1, name = 'C8')
for j in range(n):
m.addConstr(gp.quicksum(b[i,j] for i in range(n)) == 1, name = 'C9')
for j in range(n):
m.addConstr(r[j] == gp.quicksum(z[i] * b[i,j] for i in range(n)), name = 'C10')
for j in range(n-1):
m.addConstr(r[j+1] <= r[j])
m.update()
m.update()
m.params.NonConvex = 2
m.params.MIPFocus = 2
#m.params.Cuts = 0
m.params.NoRelHeurTime = 50
#m.params.PreSparsify = -1
#m.params.NumericFocus = 1
m.optimize()
print(m.SolCount)0 -
Hi Xin Yu,
Thank you for sharing the model! This looks a hard model. From the following code snippet:
m.setObjective(r[0] * t, gp.GRB.MAXIMIZE) m.addConstr(t * r[3] == 1)
the objective function can be rewritten as \( \frac{r[0]}{r[3]} \). The maximum of this value could diverge. Hence, it may be natural for the formulation to be weak.
Currently, Gurobi solves this problem as NonConvex MIQCP. However, it is known that these kinds of fractional functions optimization can be linearized by using the Charnes-Cooper transformation. By applying this, Gurobi may be able to solve it as a MILP.Thanks,
Ryuta0
Please sign in to leave a comment.
Comments
8 comments