5

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)

Kuifje
  • 13,324
  • 1
  • 23
  • 56
AnneBart
  • 51
  • 3
  • In II) you mean $q>0$ ? Otherwise you could have $q=0$ in both cases. – Kuifje Sep 09 '21 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. – AnneBart Sep 09 '21 at 17:43
  • In this case consider the answer below with $L:=0$. – Kuifje Sep 09 '21 at 20:40

2 Answers2

5

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

Kuifje
  • 13,324
  • 1
  • 23
  • 56
  • 1
    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. – RobPratt Sep 09 '21 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? – AnneBart Sep 10 '21 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. – RobPratt Sep 10 '21 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 ? – tonythestark Dec 12 '22 at 08:10
2

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

Alex Fleischer
  • 4,000
  • 5
  • 11
  • Thanks for the suggestion! Interesting, I was not aware that this was possible. Will see if this can come of use in the future. – AnneBart Sep 10 '21 at 17:21