5
$\begingroup$

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)

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

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

$\endgroup$
3
  • 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 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 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 at 18:04
2
$\begingroup$

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

$\endgroup$
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 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.