Writing a max function for MTZ constraints for the CVRP
AnsweredHi I am trying to solve some instances of the CVRP where I am trying to incorporate some Miller-Tucker-Zemlin constraints for the capacity.
I have the variable \[ u_i \] denoting the load at each costumer \[N = \{1, \dots , n\} \].
I want to introduce the constraint:
\[u_{i} \leqslant Q-\left(Q-\max _{j \neq i}\left\{q_{j}\right\}-q_{i}\right) x_{1 i}-\sum_{\substack{j=2 \\ j \neq i}}^{n} q_{j} x_{i j} \]
My problem is when trying to use the max function. I have tried the following:
mdl.addConstrs(u[i] <= Q - (Q - max_([q[j] for j in N] - q[i])*x[0,i] - quicksum(q[j]*x[i,j] for j in N) for i in N)
Is this the right use of the max_ function or am I completely lost?
-
-
Gurobi Staff
Hi Magnus,
When working with general constraints such as \(\max\), one has to introduce auxiliary variables for each general constraint term. You constraint will then look like
\[\begin{align*}
u_i &\leq Q - (Q - z_i - q_i)x_{1i} - \sum_{j=2,j\neq i}^{n} q_j x_{ij}\\
z_i &= \max\{q_j, j\neq i \}
\end{align*}\]In Python code this would look similar to
for i in N:
z = mdl.addVar(lb=-GRB.INFINITY,name="z[%d]"%(i))
mdl.addGenConstrMax(z, [q[j] for j in N if j != i], name="max_constr[%d]"%(i))
mdl.addConstr(u[i] <= Q - (Q - z - q[i])*x[0,i] - quicksum(q[j]*x[i,j] for j in N))Best regards,
Jaromił0 -
-
-
Please also see our Knowledge Base article How do I model logical and general expressions? for additional information.
1 -
-
Thank you both for the quick and precise responses, that helped a lot.
0 -
Please sign in to leave a comment.
Comments
3 comments