Adding callback function with lazy constraints causes a worse solution than initial guess.

Hi,

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)

My intuitive thought is that the best objective should be 8 with x=4, y=4 and z=0. However, the best it can find is -90 which is worse than the initial guess. Here is the output:

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

My question is, is there any way I can add this collision check into my objective function? Or find the truly best objective. I tried to limit the thread to take the callback constraint into consideration, but it didn't work. I also tried to add a hard constraint for z, but it gave me infeasible solution.

Edited:

Is it a bi-level optimization problem?

Riley Clement

Gurobi Staff

2023年05月11日 18:29

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

Yuankai Zhu

2023年05月12日 00:37

Thanks Riley,

I will try to remodel my problem and see if it can fix the issue.

Best,

Yuankai

Adding callback function with lazy constraints causes a worse solution than initial guess.

コメント

お探しのものを見つけられませんでしたか？