Stuck in very specific bound while solving MIP
AnsweredHello, when i try to solve a MIP in Gurobi,
it always stuck in 15% gap( I tried set PreSOS1Encoding, Cuts and MIPFocus as below).
Is there any parameter I can have a try?
# n_cars = 100, budget = 10, G = 100 * 100 mat, lambda_1, lambda_2 = list with 100 ele
def MI_solver_with_incentive(budget, G, lambda_1, lambda_2, n_cars, time_limit,theta_lower_bound=0, theta_upper_bound=1):
m = Model("MI_incentive")
theta = m.addVars(n_cars, lb=theta_lower_bound, ub=theta_upper_bound, name="theta")
gamma = m.addVars(n_cars, lb=0,name="gamma")
sigma = m.addVars(n_cars, lb=0, name="sigma") mu = m.addVars(n_cars, lb=0, name="mu")
omega_1 = m.addVars(n_cars, vtype=GRB.BINARY, name="omega_1") # if sigma == 0
omega_2 = m.addVars(n_cars, vtype=GRB.BINARY, name="omega_2") # if mu == 0 theta_i_plus_1 = m.addVars(n_cars, name="theta_i_plus_1")
inverse_theta_i_plus_1_squared = m.addVars(n_cars, name="inverse_theta_i_plus_1_squared")
inverse_theta_i_plus_1 = m.addVars(n_cars, name="inverse_theta_i_plus_1") obj = quicksum(cal_emission(theta[i], sum(theta[j] * G[i,j] for j in range(n_cars))) for i in range(n_cars))
obj = quicksum(cal_emission(theta[i], sum(theta[j] * G[i,j] for j in range(n_cars))) for i in range(n_cars))
m.setObjective(obj, GRB.MINIMIZE)
for i in range(n_cars):
theta[i].setAttr(GRB.Attr.BranchPriority, 2)
gamma[i].setAttr(GRB.Attr.BranchPriority, 1)
m.addConstr(theta[i] +1 == theta_i_plus_1[i])
m.addGenConstrPow(theta_i_plus_1[i], inverse_theta_i_plus_1_squared[i], -2, f"inv_theta_i_plus_1_squared_{i}")
m.addConstr(theta_i_plus_1[i] * inverse_theta_i_plus_1[i] == 1)m.addConstr(
lambda_1[i] * theta[i] + sigma[i] - mu[i] - inverse_theta_i_plus_1_squared[i] * (lambda_2[i]- gamma[i]) == 0,
f"KKT_{i}"
)
m.addGenConstrIndicator(omega_1[i], True, sigma[i], GRB.EQUAL, 0)
m.addGenConstrIndicator(omega_1[i], False, theta[i], GRB.EQUAL, 1)
m.addGenConstrIndicator(omega_2[i], True, mu[i], GRB.EQUAL, 0)
m.addGenConstrIndicator(omega_2[i], False, theta[i], GRB.EQUAL, 0)m.addConstr(quicksum(gamma[i] * inverse_theta_i_plus_1[i] for i in range(n_cars)) <= budget, "BudgetConstraint")
m.setParam('MIPGap', 0.05) # optimality gap
m.setParam('Cuts', 3)
m.setParam('Threads', 8)
m.setParam('Heuristics', 0.1)
m.setParam('MIPFocus', 2)
m.setParam('NodefileStart', 0.5)
m.setParam('PreSOS1Encoding', 2) m.setParam('TimeLimit', time_limit)
m.setParam('NonConvex', 2)
m.update()
m.optimize()
0
-
corresponding formulate:
x(cal_emission in code)=0.5*\theta_i^2+0.2*z_i^2+0.5; z_i = sum(\theta_j * G[i,j] for j in range(n_cars)
y(cal_travel_time in code)=1/(1+\theta_i)
Running example:
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 50.00000 0 71 - 50.00000 - - 0s
0 0 50.00524 0 289 - 50.00524 - - 0s
0 0 50.31463 0 350 - 50.31463 - - 2s
0 0 50.93325 0 350 - 50.93325 - - 2s
0 0 50.97470 0 350 - 50.97470 - - 3s
0 0 50.98445 0 350 - 50.98445 - - 3s
0 2 50.98445 0 350 - 50.98445 - - 8s
217 226 54.03896 17 321 - 51.67592 - 165 10s
907 522 55.31769 58 241 - 51.67827 - 193 15s
1241 903 56.61928 80 241 - 51.67827 - 253 20s
1903 1536 59.04904 110 191 - 51.67827 - 271 25s
1970 1610 59.04904 114 191 - 51.67827 - 286 33s
2071 1761 60.99363 120 191 - 51.67827 - 301 35s
2896 2776 60.65707 198 241 - 51.67827 - 266 40s
3885 3836 60.99547 229 241 - 51.67827 - 222 53s
4786 4982 61.55385 293 191 - 51.67827 - 193 55s
6254 7046 61.86721 421 191 - 51.67827 - 156 60s
7454 7052 60.58870 255 390 - 53.95615 - 134 65s
7464 7059 61.15599 289 384 - 54.53915 - 134 70s
7474 7067 59.92141 188 232 - 54.58287 - 142 75s
7478 7070 61.88553 462 290 - 54.98540 - 141 80s
7485 7075 59.79551 193 247 - 55.01443 - 141 90s
7508 7099 55.61478 27 452 - 55.18910 - 147 98s
7611 7175 55.62291 33 425 - 55.19845 - 146 100s
8204 7568 55.20603 43 369 - 55.20603 - 139 105s
8673 7942 55.21309 73 331 - 55.21081 - 136 110s
9390 8214 55.21093 156 250 - 55.21081 - 131 118s
9504 8243 55.33395 180 294 - 55.21081 - 131 121s
9984 8679 55.67114 300 203 - 55.21081 - 136 125s
10558 8994 56.76871 401 207 - 55.21081 - 136 131s
11120 9153 55.33403 182 293 - 55.21081 - 138 143s
11444 9592 55.44443 228 280 - 55.21081 - 137 147s
12109 9921 55.55691 257 245 - 55.21081 - 134 153s
12760 10176 55.44449 256 250 - 55.21081 - 131 158s
13356 10279 55.55690 303 204 - 55.21081 - 130 163s
13819 10470 55.68382 310 217 - 55.21081 - 131 170s
14341 10486 55.55710 309 204 - 55.21081 - 131 177s
14689 10652 55.67857 317 202 - 55.21081 - 133 185s
15135 10781 infeasible 321 - 55.21081 - 134 194s
15592 10831 56.09787 334 203 - 55.21081 - 136 201s
16073 11022 56.42906 338 203 - 55.21093 - 139 214s
16572 11218 55.21124 155 250 - 55.21093 - 139 221s
17156 11408 55.33540 246 251 - 55.21093 - 140 231s
17767 11597 55.46051 281 250 - 55.21093 - 141 239s
18458 11831 55.57736 312 244 - 55.21093 - 142 245s
19242 11954 55.69574 339 245 - 55.21093 - 143 253s
20020 11963 infeasible 341 - 55.21093 - 145 269s
H20255 11530 64.9793494 55.21093 15.0% 146 269s
20461 12804 55.95167 359 269 64.97935 55.21093 15.0% 146 285s
22524 12884 55.46567 263 265 64.97935 55.21093 15.0% 138 298s
23365 14335 55.21409 99 306 64.97935 55.21093 15.0% 134 312s
25537 14962 57.42826 359 227 64.97935 55.21093 15.0% 129 320s
27046 15536 55.33844 223 253 64.97935 55.21093 15.0% 129 330s
28505 16737 55.46555 274 250 64.97935 55.21093 15.0% 129 343s
30394 17849 55.59470 306 206 64.97935 55.21093 15.0% 126 351s
31954 18681 55.98890 348 222 64.97935 55.21093 15.0% 125 360s
33023 19321 56.15115 363 215 64.97935 55.21093 15.0% 124 372s
H33923 19592 64.9209993 55.21093 15.0% 124 385s
34310 19987 56.35599 380 208 64.92100 55.21093 15.0% 125 397s
34945 20797 56.65917 397 205 64.92100 55.21093 15.0% 126 411s
36145 21448 55.34136 207 275 64.92100 55.21093 15.0% 126 425s
37154 21922 59.41827 426 198 64.92100 55.21093 15.0% 127 439s
37896 23029 56.18777 350 218 64.92100 55.21093 15.0% 128 455s
39415 24461 infeasible 767 64.92100 55.21093 15.0% 128 469s
41291 24487 55.46792 233 226 64.92100 55.21093 15.0% 126 482s
41331 26106 55.46792 238 221 64.92100 55.21093 15.0% 126 491s
43514 28832 56.68818 292 204 64.92100 55.21093 15.0% 123 504s
46580 30805 59.08230 482 221 64.92100 55.21093 15.0% 118 514s
48953 33043 62.54048 773 226 64.92100 55.21093 15.0% 115 524s
51612 33861 infeasible 160 64.92100 55.21093 15.0% 111 530s
52513 34562 57.80875 162 271 64.92100 55.21093 15.0% 111 538s
53482 35169 55.34211 189 293 64.92100 55.21094 15.0% 110 544s
54361 35865 infeasible 156 64.92100 55.21094 15.0% 111 551s
55258 36429 55.33775 229 249 64.92100 55.21094 15.0% 111 558s
55966 36931 55.59349 257 217 64.92100 55.21094 15.0% 111 567s
56688 37539 55.46291 254 251 64.92100 55.21094 15.0% 111 574s
57480 38152 55.59337 275 199 64.92100 55.21094 15.0% 111 583s0 -
-
-
Gurobi Staff
Could you please also share the first ~30 lines of the log?
There can be multiple reasons for the behavior you observe.
- It is very hard to find and improve feasible points. In this case, I would recommend to experiment with the parameter NoRelHeurTime. This enables a special heuristic which tries to find and improve feasible points before going into the B&B algorithm. A value of 600s to start off should be acceptable. Alternatively, you could try providing a MIP Start.
- The formulation is weak. In this case, please refer to our Tech Talk on Converting Weak to Strong MIP Formulations.
- The branching priorities you provided might be causing more harm than good. You should try running the model with default settings and without any branching priorities.
Best regards,
Jaromił0 -
Please sign in to leave a comment.
Comments
2 comments