How to correctly write a constraint with a gurobi variable as both variable and index of another decision variable (in Python)
AnsweredHello everyone,
I'm having trouble correctly coding a constraint, in which a time variable is used both as an index of a binary decision variable $x_{ijt}$ and a continuous time variable. The constraint looks as follows:
\begin{align}
\sum_{t \in T} \sum_{i \in V} x_{ijt} \cdot (t+c_{j0}) \quad &\leq \quad t^* & & \forall \; j \in V & \label{eq:MIP34}
\end{align}
The whole model which minimizes the "makespan" or "completion time" of an AGV-Routing essentially combines a VRP and a TSP over the orders $\omega \in \Omega$ containing multiple Positions $(i,j) \in V^{\omega}$.
For reference the whole model looks like this (thus far):
\begin{align}
\textbf{M_{3}:} \quad & Minimize ~ t^* \\
subject~to:
\sum_{t \in T} \sum_{i \in V} x_{ijt} \cdot (t+c_{j0}) \quad &\leq \quad t^* & & \forall \; j \in V & \label{eq:MIP7}\\
\sum_{t \in T} \sum_{j \in V_{0}} x_{jit} \quad &= \quad 1 & & \forall \; i \in V^{\omega}, \; \omega \in \Omega & \label{eq:MIP35}\\
\sum_{t \in T} \sum_{j \in V_{0}} p_{jit} \quad &= \quad 1 & & \forall \; i \in V & \label{eq:MIP36}\\
\sum_{\tau = 1}^{t} \sum_{j \in V_{0}} x_{ij\tau} \quad & \geq \quad \sum_{j \in V} x_{ij(t+c_{ij})} & & \forall \; i \in V_{0}^{\omega}, \; \omega \in \Omega, \; i \neq j, & \label{eq:MIP37}\\&&& t = c_{ij},...,T \nonumber\\
\sum_{\tau = 1}^{t} \sum_{j \in V_{0}} p_{ij\tau} \quad & \geq \quad \sum_{j \in V} p_{ij(t+c_{ij})} & & \forall \; i \in V_{0}, \; t = c_{ij},...,T, \; i \neq j & \label{eq:MIP38}\\
\sum_{\tau = 1}^{t} \sum_{j \in V_{0}} x_{ij\tau} \quad & \geq \quad \sum_{j \in V} p_{ij(t+c_{ij})} & & \forall \; i \in V_{0}^{\omega}, \; \omega \in \Omega, \; i \neq j, & \label{eq:MIP39}\\&&& t = c_{ij},...,T \nonumber\\
\sum_{\tau = 1}^{t} \sum_{j \in V_{0}} p_{ij\tau} \quad & \geq \quad \sum_{j \in V} x_{ij(t+c_{ij})} & & \forall \; i \in V_{0}^{\omega}, \; \omega \in \Omega, \; i \neq j, & \label{eq:MIP40}\\&&& t = c_{ij},...,T \nonumber\\
\sum_{t = 1}^{T} \sum_{j \in V} p_{0jt} \quad & \leq \quad \vert P \vert &&& \label{eq:MIP41}\\
x_{ijt} \quad &\in \quad \{ 0, 1 \} & & \forall \; \, i \in V^{\omega}_{0}, \; j \in V^{\omega}, \; \omega \in \Omega, & \label{eq:MIP42}\\&&& t = c_{ij},...,T-c_{ij} \nonumber\\
p_{ijt} \quad &\in \quad \{ 0, 1 \} & & \forall \; \, i \in V_{0}, \; j \in V, \; t = c_{ij},...,T - c_{ij} & \label{eq:MIP43}
\end{align}
In my code I first create instances of Data containing the distances between the nodes in the matrix (inst.distance(i, j)), the number of pickers working with AGVs (inst.num_pickers()), a total number of nodes (inst.nodes), a number of clusters (inst.clusters()) being the orders containing lists of lists of nodes within the matrix and a number of customer nodes which exclude the depot $i=0$ (inst.customers()).
Both the decision variables for the assignment of AGVs $x_{ijt}$ and pickers $p_{ijt}$ are binary.
The problematic constraint commented raises a KeyError exception and looks like this:
-
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 Erik,
You create the \( \texttt{x[i, j, t]} \) variables under the condition that \( \texttt{i != j} \):
if i != j:
# AGV arcs between cluster nodes
x[i, j, t] = m.addVar(vtype=GRB.BINARY, name="x_%s_%s_%s" % (i, j, t))Thus, the variable \( \texttt{x[1,1,0]} \) does not exist. The constraint in question must try to access this variable, which produces the \( \texttt{KeyError} \).In your code, you fix a \( \texttt{j} \) in \( \texttt{inst.customers()} \), then add a constraint by summing over \( \texttt{i} \) in \( \texttt{inst.customers()} \) without checking if \( \texttt{i != j} \). You should be able to fix this particular error by adding an additional conditional check within the constraint. E.g.:m.addConstr(quicksum(x[i, j, t] * (t + inst.distance(j, inst.depot())) for t in T for i in inst.customers() if i != j) <= makespan)
I see that you define some "clusters." So perhaps \( \texttt{x[i, j, t]} \) is not even defined for every \( \texttt{i != j} \). In this case, you would have to be even more careful with how you sum over the \( \texttt{x} \) variables.Thanks,Eli0 -
-
Hi Eli,
thank you very much. I completely forgot to include the conditional check. The x variables are defined for i != j only, so the code works now.
Cheers,Erik
0 -
-
Hello Eli,
the code needed to be modified and doesn't work again. I tweaked the constraint mentioned above so it looks like this now:
\begin{align}
\sum_{t \in T} \sum_{i \in V^{\omega}} \sum_{\omega \in \Omega} x_{ijt} \cdot (t+c_{j0}) \quad &\leq \quad t^* & & \forall \; j \in V^{\omega}, \; \omega \in \Omega, \; i \neq j
\end{align}The corresponding code looks like this (so far):
for k in inst.clusters():
for j in inst.customers(k):
m.addConstr(quicksum(x[i, j, t] * (t + inst.distance(j, inst.depot())) for t in T for k in inst.clusters() for i in inst.customers(k) if i != j) <= makespan)The object instance (inst) has the following properties which are fed into the model:
{"_nodes": [0,1,2,3,4,5],"_customers": [1,2,3,4,5],"_clusters": [0,1],"_depot": 0,"_cluster_nodes": [[1,2,3],[1,2]],"_x": {"0": -5,"1": 17,"2": 97,"3": 32,"4": 63,"5": 57},"_y": {"0": -5,"1": 72,"2": 8,"3": 15,"4": 97,"5": 60},"_num_pickers": 1}Here the call to inst.customers(k) returns cluster_nodes instead of customers, so a list of lists separating the customer nodes into clusters is returned and fed into the model.
The Code above throws the following TypeError:
Exception has occurred: TypeErrorunsupported operand type(s) for *: 'int' and 'dict'Alternatively, I summarized over inst.customers without specifying clusters, leaving out the problematic (I assume?) inst.customers(k)-expression within the addConstr() function:
for k in inst.clusters():
for j in inst.customers(k):
m.addConstr(quicksum(x[i, j, t] * (t + inst.distance(j, inst.depot())) for t in T for i in inst.customers() if i != j) <= makespan)This then throws a KeyError indicating that i = 4 cannot compute, which must have to do with the definition of x[i, j, t] (see full Code in initial post) and the clusters_nodes forming the first cluster as [1, 2, 3]:
Exception has occurred: KeyError(4, 1, 0)Questions:
How can I properly code a constraint which sums over clusters of customers?
Alternatively, how do I define my x variables so that a summation over inst.customers without clusters can be interpreted by Gurobi?
Thank you again in advance.
Cheers,
Erik0 -
-
-
Hi Erik,
This constraint doesn't quite make sense:
$$\begin{align*} \sum_{t \in T} \sum_{i \in V^{\omega}} \sum_{\omega \in \Omega} x_{ijt} \cdot (t+c_{j0}) &\leq t^* \qquad \forall \; j \in V^{\omega}, \; \omega \in \Omega, \; i \neq j\end{align*}$$
In particular, you likely don't want the summation \( \sum_{\omega \in \Omega} \) on the left-hand side. \( \omega \) is defined in the forall statement, so it doesn't make sense to also use \( \omega \) to index a summation in the same constraint family. Your first code snippet does something similar by using \( \texttt{for k in inst.clusters()} \) in an outer loop, then again inside of this loop. As a smaller note, the \( i \neq j \) should be a condition on the \( i \in V^\omega \) summation on the left-hand side, not in the forall statement (where \( i \) is not even defined).
- The \( \texttt{TypeError} \) in your first code snippet suggests that you are multiplying an \( \texttt{int} \) and a \( \texttt{dict} \) together somewhere. It's hard to see what's going on here without a completely self-contained code example that includes all of the necessary definitions.
- The \( \texttt{KeyError} \) in your second code snippet can probably be resolved by only summing over customers within the \( k \)th cluster. I.e., change \( \texttt{for i in inst.customers()} \) to \( \texttt{for i in inst.customers(k)} \). This matches how you defined the \( \texttt{x} \) variables in your original post.
Thanks,
Eli
0 -
-
Hi Eli,
thank you again for your comments. The summation over \omega accidentally made it into my code and I just blindly implemented it TeX for...reasons (lazyness).
Code works now. This can be closed.
Cheers,
Erik
0 -
Post is closed for comments.
Comments
6 comments