Extract info from Gurobi binary variables during run-time
Answered
I will ask with an example.
Consider a scheduling problem where a 2D array of binary variables Z(i,v) is defined, where i is index of time slot, and v is index of operation, each Z(i,v) is a 0-1 binary variable, Z(i,v)=1 means operation v is allocated to time slot i.
Now consider adding the following constraint/penalty based on Z(i,v):
- A certain operation v0 can be scheduled multiple times, i.e., there are multiple ii values where Z(i,v0)=1. We want to add constraint to the "last i" where Z(i,v0)=1, i.e., to the last v0 operation. For example, in the last v0 operation the product volume must satisfy vol(i,v0)≥100. The problem is we must first tell what is the last i that satisfies Z(i,v0)=1, and only after that add vol(i,v0)≥100, how to do that?
- This is an extension of the above problem. Here we consider multiple operations v0,v1,⋯,vn. In certain applications the "order" of those n+1 operations matter, meaning that certain order could incur extra cost, and that the objective should contain a penalty term that is a function of the order. To add penalty, we should know the order first, which in turns means that we should extract all those i values where Z(i,v0)=1, Z(i,v1)=1, etc.
Comment: if Z(i,v) is given, then I can just use a for loop to locate all those i values where Z(i,v)=1, the problem is Z(i,v) is part of the solution, and is unknown during the solution process. That's what gets me confused. But I expect that Gurobi has some built-in syntax/function to handle those scenarios because technically it should be possible.
-
Hi Chenguang,
These sound like modeling questions. It's common to use binary variables to ensure that certain logical conditions are satisfied.
For (1), consider a fixed time i and operation v. Assuming y is a nonnegative "volume" variable, we can model this as follows:
\( y_{iv} \geq 100 ( Z_{iv} - \sum_{j > i} Z_{jv} ) \)
If Z(i,v) = 0 or operation v is performed again at a time later than i, the constraint is redundant due to the nonnegativity of y. However, if Z(i,v) = 1 and is the last such i, this constraint becomes y(i, v) >= 100, as desired.
Perhaps you can do something similar for (2)? It's tough to say without additional information about the penalty. I imagine that this is possible to do by introducing additional "indicator" binary variables that are equal to 1 if a penalty should be incurred, and 0 otherwise. This is done by modeling a logical constraint, not unlike what we did for (1). Then, these variables are incorporated into the objective function.
I hope this helps!
Eli
0 -
Hi Eli,
Thanks for your brilliant solution! I also have another quick question to ask, or more precisely, a confirmation to make.
Like I said, we have an $Z_{iv}$ binary array. Is there a way to quickly identify those i-index where $Z_{iv}=1$, so I can use those i-index somewhere else (in constraint, penalty, for example)? Is this a model formulation issue, or it is directly support by some Gurobi syntax?
I ask this because Gurobi has syntax sugar to support certain things (for example, absolute value).
0 -
Hi Chenguang,
This is more of a model formulation question. The idea is to exploit the fact that Z_{iv} is binary in order to enforce logical conditions. For example, if we want to add a penalty of 10 to our objective if Z_{iv} = 1, we can simply add the term 10 Z_{iv} to the objective function.
If we want to enforce a constraint if Z_{iv} = 1, this is possible as well, but the exact approach depends on the particular constraint you want to add. Fortunately, Gurobi provides a shortcut method for doing this. For example, in our Python API, you can do something like this:
model.addConstr((Z[i,v] == 1) >> (x + y <= 1.5))
In this case, if Z_{iv} = 1, then the constraint x + y <= 1.5 must hold. See the documentation for the Model.addGenConstrIndicator() method for more information.
I hope this helps. Thanks!
Eli
0
Please sign in to leave a comment.
Comments
3 comments