Extract info from Gurobi binary variables during run-time
AnsweredI 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.
-
Official comment
-
Gurobi Staff
This post is more than three 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 why not try our AI Gurobot?. -
-
-
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 -
Post is closed for comments.
Comments
4 comments