Using an initial solution while also using lazy constraints
AnsweredI have a optimization problem where I have a variable x, I have a heuristic that give an initial solution that I have set using the
x[i].start = init_x[i]
To set the initial start for x. However I have also implimented some lazy constraints in the form of subtour eliminations, and I cant figure out how to give an initial solution together with using lazy constraitns.
My code is quite long, but the implimentation pars as I have tried so far is as follows:
x[i].start = init_x[i]
mdl._x = x
mdl.Params.lazyConstraints = 1
mdl.optimize(sub_elim)
I am using python as an api.
-
-
Gurobi Staff
Hi Magnus,
Your code snippet looks correct. You have to provide a MIP start before starting the optimization with lazy constraints. The only suspicious thing is that you set only one start value. I think you would like to have something like
for i in I:
x[i].start = init_x[i]
mdl._x = x
mdl.Params.lazyConstraints = 1
mdl.optimize(sub_elim)Best regards,
Jaromił1 -
-
Hi Jaromil
My mistake with setting of x[i] value, that is a typo and it is iterated as you suggested.
However I have tried to impliment it again, and it seems that the
mdl._x = x
interfeers with the start values set in the step before, no initial start is fed into the problem... I have the same problem written without the lazy constraints and there it works without any problems as:
for i in I:
x[i].start = init_x[i]
mdl.optimize()This runs with the initial solution. Can the
mdl._x = x
Somehow generate a problem for me?
0 -
-
-
Somehow generate a problem for me?
Could you please provide a minimal reproducible example to reproduce this issue?
Just from the snippets you provided, the code looks good.
1 -
-
I can try to shorten it down to give an example
A = list of tuples
x = {}
for i,j in A:
x[i,j] = mdl.addVar(vtype = GRB.BINARY, name = 'x_%d_%d' & (i,j))
#multiple contraints given
mdl.addConstrs(......)
initial = initial solution of routs given by heuristic
#initial is a list of lists with routes as example [[0,3,2,0], [0,5,4,0]]
start_x = []
for route in initial:
for i in range(len(route)-1):
start_x.append((route[i], route[i+1]))
#now the list of values for the initial solution
init_x = {}
for i in x:
if i in start_x:
init_x[i] = 1
else:
init_x[i] = 0
for i in x:
x[i].start = init_x[i]
mdl._x = x
mdl.Params.lazyConstraints = 1
mdl.optimize(sub_elim)This is in rough terms what the code is.
If i run without the lazy constraints i change the last part of the code to:
for i in x:
x[i].start = init_x[i]
mdl.optimize()Which uses the initial solution without problems.
Hope this helps
0 -
-
And if it helps, the sub_elim function is in short like the following:
def sub_elim(model, where):
if where == GRB.callback.MIPSol:
Testing and adding the lazy constraints...0 -
-
-
Could you please also share a snippet of how exactly you use the \(\texttt{mdl._x}\) variable in your callback. Could you also show a log output where you see that a MIP start is or is not provided?
1 -
-
Of course, the mdl._x is used to get the relaxed values of the LP relaxation of my MIP problem, and are used as such:
def sub_elim(model, where):
if where == GRB.callback.MIPSOL:
sol = model.cbGetSolution(model._X)
selected = tuplelist((i,j) for i,j in model._x if sol[i,j] > 0 if i != 0 if j != 0)initial objective: 259 #This is the solution from the heuristic
Set parameter Username
Academic license - for non-commercial use only - expires 2023-05-06
Set parameter TimeLimit to value 60
Set parameter LazyConstraints to value 1
Gurobi Optimizer version 9.5.2 build v9.5.2rc0 (mac64[arm])
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 2571 rows, 1034 columns and 12808 nonzeros
Model fingerprint: 0xcc1571d6
Variable types: 66 continuous, 968 integer (968 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+01]
Objective range [4e+00, 4e+01]
Bounds range [1e+00, 1e+01]
RHS range [1e+00, 1e+01]
User MIP start did not produce a new incumbent solution #No incumbent sol
Presolve removed 366 rows and 24 columns
Presolve time: 0.04s
Presolved: 2205 rows, 1010 columns, 22105 nonzeros
Variable types: 66 continuous, 944 integer (944 binary)
Root relaxation: objective 1.847778e+02, 521 iterations, 0.01 seconds (0.02 work units)
Another try with MIP start
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 184.77778 0 40 - 184.77778 - - 0s
H 0 0 347.0000000 184.77778 46.7% - 0s
0 0 191.54545 0 43 347.00000 191.54545 44.8% - 0s
H 0 0 293.0000000 191.54545 34.6% - 0s
0 0 194.46067 0 38 293.00000 194.46067 33.6% - 0s
H 0 0 282.0000000 194.46067 31.0% - 0sHope this is what you asked for.
0 -
-
-
Hi Magnus,
The line
User MIP start did not produce a new incumbent solutionmeans that Gurobi took the MIP start you provided but was not able to produce a feasible solution out of it. This is probably because some lazy constraints cut off the original MIP start and then Gurobi was not able to use the point to construct a feasible point. This means that your code works properly.
Best regards,
Jaromił1 -
-
Hi Jaromil
Ahh okay, sorry for the trouble then, my bad then… is there a way to start the program without the lazy constraint for maybe one branching for then to use the lazy constraint after?
0 -
-
-
Hi Magnus,
is there a way to start the program without the lazy constraint for maybe one branching for then to use the lazy constraint after?
No, unfortunately not. This could lead to any sort of trouble. Imagine accepting a solution which is actually cut off by a lazy constraint but telling this to the solver only a bit later. The solver could then misuse the feasible point information to perform some model reductions which are indeed not valid.
Best regards,
Jaromił1 -
-
Okay thank you a lot for the help Jaromil, it is much appreciated. Your explaination makes a lot of sense.
Best regards,
Magnus
0 -
Please sign in to leave a comment.
Comments
11 comments