multiple conditions in indicator constraint
Answered
Hi there, I'm working on a vehicle routing problem, in which a vehicle need to pick up amounts of things in some nodes. Except for meeting the time windows of each nodes, it is also required that the capacity of the vehicle is limited, which causes a big problem for me. Every time when the vehicle leaves a node, it checks whether the remaining capacity can load the amount in the next node. If not, the vehicle need to unload first and then go to the next node (the unloading time can be neglected). my model for the capacity constraints are like:
As you can see, there are 4 indicator constraints, each of them has two conditions in "if" line. I saw a similar question here in this community but that doesn't work on my problem. Does anyone know how to deal with such format of constraints in Gurobi? Or do we have more smarter modeling method to list some constraints that is easier to input in Gurobi optimizer?
Besides, since Gurobi doesn't support strict comparation signs like < and >, how do we deal with such a problem if we find a way to input the above constraint? I mean, if strict comparation sign is not supported then we have constraints like if x <= 0, y =1; if x >= 0, y = 0, in which the value of x has some overlap and it may cause problems.
-
Official comment
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 Kaiyu,
It is possible to model the above with additional binary variables \(\delta_i\) and the constraints
\[\begin{align}
T_i + q_i &\geq Q - M \cdot \delta_i + 0.00001 \\
T_i + q_i &\leq Q + M \cdot (1 - \delta_i) \\
\end{align}\]The above sets \(\delta_i=1\) if \(T_i + q_i \leq Q\) and \(\delta_i = 0 \) if \(T_i + q_i \geq Q + 0.00001\). Here I used \(T_i\) for \(TotalLoad_i\). The small offset \(0.00001\) is necessary to model the strict inequality constraint. \(M\) is a constant big-M value, which can very likely be set equal to \(2Q\) (depending on the bounds of \(T_i\) and \(q_i\).
We can now model the two \(\texttt{if}\)-clauses with 2 indicator constraints
\[\begin{align}
x_{ij} = 1 &\rightarrow T_j = T_i \cdot \delta_i + q_j\\
x_{ij} = 1 &\rightarrow U_i = 1 - \delta_i
\end{align}\]Please note that \(T_i \cdot \delta_i\) is a bilinear term and the indicator constraint feature allows linear expressions only. Thus, you will have to introduce an additional variable and reformulate the bilinear term as described in How to linearize the product of a binary and a non-negative continuous variable?
Please note that the above formulation is not guaranteed to be the best one and there may be a better one possible.
Best regards,
Jaromił0
Post is closed for comments.
Comments
2 comments