# In a MIP, how to force a decision variable to be zero unless the sum of specific other decision variables is equal to a certain number?

In an MIP, how can I formulate a constraint such that a decision variable is only greater (or equal to) zero if (and only if) the sum of different decision variables is equal to something.

I'm working with a path flow formulation model and I want to have a constraint that forces flow q on path p to be zero if not all routes in path p are flown.

Example: flow q on path p, which contains flight A to B ($$f_{AB}$$) and flight B to C ($$f_{BC}$$), can be greater than zero if and only if one aircraft flies from A to B and (the same or another aircraft) flies from B to C.

I) q = 0 if $$\sum$$($$f_{AB}$$ + $$f_{BC}$$) $$\le$$ 1

II) q $$\ge$$ 0 if $$\sum$$($$f_{AB}$$ + $$f_{BC}$$) = 2

In case there are three flights in one path, constraint I becomes $$\le$$ 2, and constraint II becomes = 3, etc.

(I know exactly which flow can go over which paths, and I know how many flights are contained in all of the available paths. Moreover, all $$f_{ij}$$ are binary)

Help with this would be highly appreciated! (I'm writing my problem in python, in case that matters for anything)

• In II) you mean $q>0$ ? Otherwise you could have $q=0$ in both cases. Sep 9, 2021 at 14:48
• No q may still be zero. In general, there are multiple paths available for each q, so the fact that $f_{AB}$ and $f_{BC}$ are both 1, does not mean that this path will be used to transport q. I'm using a timespace network, so AB and BC do not only represent airports, but also points in time. Therefore, if a path earlier/later in time is better, then that other path can also be used. Sep 9, 2021 at 17:43
• In this case consider the answer below with $L:=0$. Sep 9, 2021 at 20:40

Introduce a binary variable $$\delta \in \{0,1\}$$ to indicate whether $$q$$ is positive or not. You want: $$\sum_{(i,j) \in A}f_{ij} \le |A| - 1 \quad \Longrightarrow \quad \delta=0$$ or the contrapositive: $$\delta=1 \quad \Longrightarrow \quad \sum_{(i,j) \in A}f_{ij} \ge |A|$$ which you can achieve with: $$\sum_{(i,j) \in A}f_{ij} \ge |A| \delta$$

Then, assuming you want $$q\ge L$$ when $$\sum_{(i,j) \in A}f_{ij} = |A|$$, add the constraints: $$L\delta \le q \le M \delta$$ $$M$$ is an upper bound on $$q$$. The right hand side of this last constraint enforces $$q$$ to take value $$0$$ when $$\delta=0$$.

• Looks good (+1). You can optionally strengthen the formulation by disaggregating the first constraint to $f_{ij} \ge \delta$ for all $(i,j)\in A$, which arises from rewriting $\delta \implies \wedge_{(i,j)} f_{ij}$ in conjunctive normal form. Likely, cut generation will do this dynamically as needed. Sep 9, 2021 at 16:02
• Thank you so much @Kuifje! The constraint with the $\sum f_{ij} \ge |A| \delta$ works perfectly! (The constraint with $q \le M \delta$ I already had, with the upperbound being the maximum q can take on). @RobPratt I've added your cut as well, however, for some reasons it does not yet seem to improve the speed of convergence to an optimal solution (within a given timelimit of 15 minutes, the optimality gap is larger with this added cut, then without it) Do you think that a larger timelimit could make a change for the better? Sep 10, 2021 at 17:16
• No, I think that behavior is evidence that the useful cuts are generated as needed from the weaker aggregated constraint and that the other cuts just artificially make the LP larger. Sep 10, 2021 at 18:04
• if $\sum f_{ij} \geq |A|$ for example if $\sum f_{ij} =|A|$ then $|A| \geq |A|\delta \implies \delta \leq 1$ how does that force $\delta$ to be 1 ? Dec 12, 2022 at 8:10

With CPLEX you can use logical constraints.

For instance with the OPL API you can write:

dvar boolean q;
dvar int a;
dvar int b;

subject to
{
q==(a+b>=2);
}


q is 0 iff a+b<=1

• Thanks for the suggestion! Interesting, I was not aware that this was possible. Will see if this can come of use in the future. Sep 10, 2021 at 17:21