Adding callback function with lazy constraints causes a worse solution than initial guess.
AnsweredHi,
I am working on a fruit harvesting problem, that is, a mobile harvesting robotic system with two rows of robot arms harvesting while moving in a whole. Once the speed of the robotic system is determined, I can find the solution of the harvesting sequence as a TOPTW similarly defined here. The difference is that my system has multiple rows. The problem is, my robot arms can move vertically freely up and down but can not cross each other. It means the higher level arm cannot be lower than the lower one. This collision can only be considered after the robot arms harvesting pattern has been found by the TOPTW. The collision check can be done in the callback function. Then I added a collision flag as a binary variable in my objective function. If the collision check failed, it will add a large negative penalty in the objective function. I hope this method could provide a collision free harvesting pattern, but it didn't.
I simplify this process by the following codes in Python 3.9.12 with gurobi 10.0.0, where x and y mimic the harvesting route (patterns, sequences, whatever) by solving TOPTW; z mimics the collision check flag and is added in the objective function with a large negative penalty. The x_val + y_val < 8 mimic the collision check function that can only be processed after the solution of x and y have been found.
from gurobipy import *
# Create a new model
m = Model("mip1")
# print(f"Thread number is :{m.getParamInfo('Threads')}")
# m.setParam('Threads', 1)
# print(f"Thread number is :{m.getParamInfo('Threads')}")
# Create variables
x = m.addVar(vtype=GRB.CONTINUOUS, name="x")
y = m.addVar(vtype=GRB.CONTINUOUS, name="y")
z = m.addVar(vtype=GRB.BINARY, name="z")
# Set objective
m.setObjective(x + y - 100*z, GRB.MAXIMIZE)
# Add constraint: x + y <= 10
m.addConstr(x + y <= 10, "c0")
# m.addConstr(z <= 0.5, "z0")
# Start with an initial feasible guess
x.start = 4
y.start = 4
z.start = 0
# Define the callback function
def mycallback(model, where):
# print(f"Calling callback!")
if where== GRB.Callback.MIPSOL:
# Get the current solution
x_val=model.cbGetSolution(x)
y_val=model.cbGetSolution(y)
# If the solution is better than the initial guess, add a constraint to exclude it
print(f"The sum is {x_val+y_val}")
if x_val+y_val>8:
# print(f"Adding a new constraint!!!")
model.cbLazy(z==1)
else:
model.cbLazy(z==0)
# Set the callback function
# m._callback = mycallback
m.Params.lazyConstraints = 1
# Optimize model
m.optimize(mycallback)
Set parameter LazyConstraints to value 1
Gurobi Optimizer version 10.0.0 build v10.0.0rc2 (mac64[x86])
CPU model: Intel(R) Core(TM) i5-5350U CPU @ 1.80GHz
Thread count: 2 physical cores, 4 logical processors, using up to 4 threads
Optimize a model with 1 rows, 3 columns and 2 nonzeros
Model fingerprint: 0xa9ce8b40
Variable types: 2 continuous, 1 integer (1 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+02]
Bounds range [1e+00, 1e+00]
RHS range [1e+01, 1e+01]
The sum is 8.0
User MIP start did not produce a new incumbent solution
The sum is 10.0
The sum is 10.0
The sum is 10.0
The sum is 10.0
The sum is 8.0
The sum is 8.0
The sum is 8.0
...
Optimal solution found (tolerance 1.00e-04)
Best objective -9.000000000000e+01, best bound -9.000000000000e+01, gap 0.0000%
User-callback calls 126, time in user-callback 0.02 sec
-
Official comment
-
Gurobi Staff
This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
Hi Yuankai,
I think it's important to remember that a lazy constraint should be globally valid, and always be valid - whether it is added or not. Consequently it does not make sense to have both z == 1, and z == 0, as lazy constraints since they cannot both be valid.
Since you are indicating that you expect (x,y) = (4,4) to be a good solution I will assume that you meant to write
if x_val+y_val>=8:
in your callback, instead of
if x_val+y_val>8:
In your particular example, once the solver arrives at a solution with x + y >= 8 - which it will very quickly - it will have z == 1 as a constraint. This constraint then remains for the rest of the solve - every solution will have z equal to 1 and incur the penalty.
It may be that imposing a lazy constraint, which removes a solution which incurs a collision, is the right approach to this problem, but just not in the way it is currently being done. In your toy example, you can penalize solutions with x + y >= 8 using your idea of the binary z variable (with a large negative objective coefficient) by adding the following constraint:
x + y <= 8 + Mz
for some constant M, which is sufficiently large. Then the only way x + y can be greater than 8 is if z is equal to 1 (and the penalty is imposed). How well this translates to your actual problem, I am not sure. I don't think a bi-level optimization is required here.
Many years ago I wrote an undergrad project on scheduling gantry cranes with collision avoidance. It looks like it may have many similarities with your fruit harvesting problem. Here is a copy if you wish to have a look.
- Riley
0 -
-
Thanks Riley,
I will try to remodel my problem and see if it can fix the issue.
Best,
Yuankai
0 -
Post is closed for comments.
Comments
3 comments