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)

  • $\begingroup$ In II) you mean $q>0$ ? Otherwise you could have $q=0$ in both cases. $\endgroup$
    – Kuifje
    Sep 9, 2021 at 14:48
  • $\begingroup$ 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. $\endgroup$
    – AnneBart
    Sep 9, 2021 at 17:43
  • $\begingroup$ In this case consider the answer below with $L:=0$. $\endgroup$
    – Kuifje
    Sep 9, 2021 at 20:40

2 Answers 2


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$.

  • 1
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Sep 9, 2021 at 16:02
  • $\begingroup$ 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? $\endgroup$
    – AnneBart
    Sep 10, 2021 at 17:16
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Sep 10, 2021 at 18:04
  • $\begingroup$ 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 ? $\endgroup$ 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 is 0 iff a+b<=1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.