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?
-
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 try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
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 -
Post is closed for comments.
Comments
4 comments