Super slow "heuristic" solution injection
回答済み
Dear Gurobi,
I have two MIPS: MIP1 and MIP2.
MIP1 is a relaxation of MIP2 and uses only a partial subset of all decision variables. But besides that they are the same. I use MIP1 to compute an upper bound solution, that I would like to inject in MIP2 with a callback. I thought if I have a feasible solution, Gurobi would use the solution right away. But this seems not to be the case and I don't know why.
My MIPSOL callback in MIP1:
if where == gp.GRB.Callback.MIPSOL:
cur_obj = model.cbGet(gp.GRB.Callback.MIPSOL_OBJ)
global model_ub
if cur_obj < model_ub:
model_ub = cur_obj
global new_solution
new_solution = {"x":{},"y":{}, "z":{}, "bz":{}}
all_x_vars = model.cbGetSolution(model._x)
all_y_vars = model.cbGetSolution(model._y)
all_z_vars = model.cbGetSolution(model._z)
all_bz_vars = model.cbGetSolution(model._bz)
for a in model._A2:
new_solution["x"][a] = all_x_vars[a]
for a in model._Ay2:
new_solution["y"][a] = all_y_vars[a]
for i in model._V:
new_solution["z"][i] = all_z_vars[i]
new_solution["bz"][i] = all_bz_vars[i]
My MIPNODE callback in MIP2:
if where == GRB.Callback.MIPNODE:
cur_obj = model.cbGet(gp.GRB.Callback.MIPNODE_OBJBST)
if np.round(cur_obj,4) > np.round(model_ub,4)+pow(10,-4):
if np.round(model_ub,4) not in model._sols:
model._sols.add(np.round(model_ub,4))
temp_sol = new_solution
new_vars = [model._x[var] for var in temp_sol["x"]] + [model._y[var] for var in temp_sol["y"]]+[model._z[var] for var in temp_sol["z"]]+[model._bz[var] for var in temp_sol["bz"]]
new_vals = list(temp_sol["x"].values()) + list(temp_sol["y"].values())+ list(temp_sol["z"].values())+ list(temp_sol["bz"].values())
print("new solution:", model_ub, cur_obj)
model.cbSetSolution(model._vars,[0.0]*len(model._vars))
model.cbSetSolution(new_vars, new_vals)
model.cbUseSolution()
My log out output is below. As you can see MIP1 founds a solution often quicker, but the solution is not used by MIP2 apparently?
Gurobi Optimizer version 12.0.0 build v12.0.0rc1 (linux64 - "Ubuntu 24.04.1 LTS")
CPU model: Intel(R) Xeon(R) Gold 6248R CPU @ 3.00GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 48 physical cores, 96 logical processors, using up to 6 threads
Non-default parameters:
TimeLimit 3600
Threads 6
Optimize a model with 15825 rows, 8599 columns and 115739 nonzeros
Model fingerprint: 0x286d9588
Variable types: 794 continuous, 7805 integer (7805 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+03]
Objective range [4e+00, 1e+02]
Bounds range [1e+00, 2e+00]
RHS range [1e-02, 1e+03]
Presolve removed 11932 rows and 4660 columns
Presolve time: 0.53s
Presolved: 3893 rows, 3939 columns, 25032 nonzeros
Variable types: 54 continuous, 3885 integer (3885 binary)
Found heuristic solution: objective 1217.8388183
Root relaxation: objective 6.736259e+02, 4061 iterations, 0.91 seconds (0.35 work units)
Set parameter MIPFocus to value 1
Set parameter PreCrush to value 0
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 673.62592 0 256 1217.83882 673.62592 44.7% - 2s
new solution: 811.2264372937074 1217.838818258734
0 0 684.89133 0 198 1217.83882 684.89133 43.8% - 3s
H 0 0 904.7652485 684.91084 24.3% - 3s
0 0 684.91084 0 198 904.76525 684.91084 24.3% - 3s
new solution: 786.8267703521534 904.7652485232375
H 0 0 835.6016977 689.20907 17.5% - 3s
0 0 689.21558 0 281 835.60170 689.21558 17.5% - 3s
H 0 0 823.1820575 689.21558 16.3% - 3s
H 0 0 787.9073085 689.21558 12.5% - 3s
0 0 689.21558 0 281 787.90731 689.21558 12.5% - 3s
0 0 691.10867 0 312 787.90731 691.10867 12.3% - 3s
H 0 0 778.4703464 691.12702 11.2% - 3s
new solution: 765.3749017299817 778.4703463962613
0 0 691.19369 0 301 778.47035 691.19369 11.2% - 3s
0 0 691.19369 0 301 778.47035 691.19369 11.2% - 3s
H 0 0 769.7111186 691.57555 10.2% - 4s
0 0 691.57555 0 360 769.71112 691.57555 10.2% - 4s
0 0 691.61863 0 360 769.71112 691.61863 10.1% - 4s
H 0 0 718.5246391 691.61863 3.74% - 4s
0 0 691.79405 0 361 718.52464 691.79405 3.72% - 4s
0 0 691.79405 0 264 718.52464 691.79405 3.72% - 4s
0 0 691.79405 0 279 718.52464 691.79405 3.72% - 4s
0 0 691.89372 0 328 718.52464 691.89372 3.71% - 5s
0 0 692.09216 0 336 718.52464 692.09216 3.68% - 5s
0 0 692.10452 0 339 718.52464 692.10452 3.68% - 5s
0 0 692.10630 0 341 718.52464 692.10630 3.68% - 5s
0 0 692.53339 0 289 718.52464 692.53339 3.62% - 5s
0 0 692.57018 0 296 718.52464 692.57018 3.61% - 5s
0 0 692.57018 0 297 718.52464 692.57018 3.61% - 5s
0 0 693.17133 0 334 718.52464 693.17133 3.53% - 5s
0 0 693.18474 0 335 718.52464 693.18474 3.53% - 5s
0 0 693.18533 0 333 718.52464 693.18533 3.53% - 5s
0 0 693.60040 0 350 718.52464 693.60040 3.47% - 5s
0 0 693.62538 0 350 718.52464 693.62538 3.47% - 5s
0 0 693.92206 0 357 718.52464 693.92206 3.42% - 5s
0 0 693.93597 0 362 718.52464 693.93597 3.42% - 5s
0 0 695.80389 0 346 718.52464 695.80389 3.16% - 5s
0 0 695.80389 0 331 718.52464 695.80389 3.16% - 5s
0 0 695.80389 0 334 718.52464 695.80389 3.16% - 5s
0 0 695.80389 0 342 718.52464 695.80389 3.16% - 5s
0 0 695.80389 0 335 718.52464 695.80389 3.16% - 5s
0 0 695.80389 0 347 718.52464 695.80389 3.16% - 6s
0 0 695.80389 0 357 718.52464 695.80389 3.16% - 6s
0 0 697.15827 0 340 718.52464 697.15827 2.97% - 6s
0 0 697.15827 0 344 718.52464 697.15827 2.97% - 6s
0 0 697.15827 0 344 718.52464 697.15827 2.97% - 6s
0 0 697.15827 0 354 718.52464 697.15827 2.97% - 6s
0 0 697.15827 0 344 718.52464 697.15827 2.97% - 6s
0 0 697.24918 0 353 718.52464 697.24918 2.96% - 6s
0 0 697.24918 0 350 718.52464 697.24918 2.96% - 6s
0 0 697.53792 0 355 718.52464 697.53792 2.92% - 6s
0 0 697.58471 0 326 718.52464 697.58471 2.91% - 6s
0 2 697.58471 0 326 718.52464 697.58471 2.91% - 6s
Cutting planes:
Cover: 22
Implied bound: 30
Clique: 1
MIR: 23
Zero half: 34
RLT: 21
Relax-and-lift: 16
Explored 205 nodes (43952 simplex iterations) in 7.57 seconds (5.50 work units)
Thread count was 6 (of 96 available processors)
Solution count 8: 718.525 769.711 778.47 ... 1217.84
Optimal solution found (tolerance 1.00e-04)
Best objective 7.185246391077e+02, best bound 7.185246391077e+02, gap 0.0000%
User-callback calls 2997, time in user-callback 1.17 sec
-
I noticed one flaw in my approach: The models were run on two different threads, but not in a thread safe way. So I added one distinct gp.Env() to each thread.
If I only set a partial solution of x and y variables, the solution setting seems to work. Now the time is also acceptable. But I still do not understand, why gurobi does not accept the complete solution? The "z" and "bz" variables depend on the x variables.
0 -
Hi,
But I still do not understand, why gurobi does not accept the complete solution?
Have you checked the return value of cbUseSolution? If the given solution is not accepted, the value will be GRB.INFINITY (very large value). In your case, partial solutions are accepted, so which means that the solution by all variables may violate some constraint.
Thanks,
Ryuta0 -
Hi Ryuta,
thank you very much for your reply! I did not know about the return Value of cbUseSolution.
Indeed, if I provide the partial solution I will get the improved objective, if it is the "full" solution I get GRB.INFINITY. It seems that just the continous variables, which depends on the integer solution values are problematic.
Any easy way to debug it? Should I try to provide it as a MIPStart to my model?
Or is it in general better to provide partial solutions?
Best Regards
3RiverResearcher
0 -
Any easy way to debug it?
For example, you can do it by fixing ub and lb of all variables to their values and then use computeIIS to see which parts are violated. This article might be helpful.
Or is it in general better to provide partial solutions?
Sometimes this approach is recommended. The values for a continuous variables may contain numeric errors that cause it to be Infeasible. Also, if integer variables are fixed, Gurobi can compute the value of the corresponding continuous variable relatively fast.
Thanks,
Ryuta0
サインインしてコメントを残してください。
コメント
4件のコメント