3
$\begingroup$

It's almost this question: Formulating the conditional constraint

But there they have non-strict inequality. I have $x_i$ a boolean decision var and $Q_i$ as a nonnegative integer decision variable such that

  1. if $x_i = 0$, then $Q_i = 0$
  2. if $x_i = 1$, then $Q_i \gt 0$ (note the strict inequality!).

Lets say I dont have upper bound on $Q_i$; is there a mathematical relation between $x_i$ and $Q_i$ you can write directly or is the following way to go?

dvar boolean x[I];
dvar int+ Q[I];

subject to
{
  forall(i in I) {
     (x[i]==0) => (Q[i] == 0);
     (x[i]==1) => (Q[i] > 0);
}

I can formulate the constraint other way but does it help I'm not sure:

  1. if $Q_i = 0$, then $x_i = 0$
  2. if $Q_i \gt 0$, then $x_i = 1$.
$\endgroup$
12
  • 4
    $\begingroup$ If $Q_i$ is an integer variable, then $Q_i > 0$ is equivalent to $Q_i \geq 1$. $\endgroup$
    – joni
    Nov 17 '21 at 11:01
  • 2
    $\begingroup$ @athing If there was an upper bound $b_i$ you could impose constraints $Q_i\leq b_i x_i$, $Q_i\geq x_i$. If $Q_i=0$, the second constraint forces $x_i=0$ since $x_i$ is a binary variable. If $Q_i=1$ the first constraint would force $x_i=1$ while $Q_i$ is smaller than or equal to its upper bound $b_i$. $\endgroup$
    – YukiJ
    Nov 17 '21 at 13:27
  • 1
    $\begingroup$ yes, it should have been $Q_i \geq 1$, sorry! Concerning your code: I have not used Cplex in a while so I am not too sure about the syntax. However, I would definitely advise following @joni's comment to change $Q_i>0$ to $Q_i \geq 1$ in the code. $\endgroup$
    – YukiJ
    Nov 17 '21 at 13:40
  • 3
    $\begingroup$ By the way, you can (usually) calculate an upper bound for $Q_i$ by relaxing the integrality constraints and maximizing $Q_i$ subject to the constraints. The only two issues here are (1) the LP might be unbounded and (2) if the problem is big enough, solving all those LPs (one for each $i$) might take too much time. $\endgroup$
    – prubin
    Nov 17 '21 at 15:59
  • 1
    $\begingroup$ The second implication with >= should be fine. I'm not sure with > whether CPLEX will recognize that $Q > 0$ equates to $Q\ge 1$ or whether it will just reflexively complain. $\endgroup$
    – prubin
    Nov 17 '21 at 23:01
2
$\begingroup$

As already mentioned in the comments: If $𝑄_i$ is an integer variable, then $𝑄_i > 0$ is equivalent to $𝑄_i \geq 1$. Hence, you can use the indicator constraints offered by the most commercial solvers in case you don't know upper bounds, i.e. (x[i]==1) => (Q[i] >= 1). Note also prubin's comment on how one can calculate an upper bound:

By the way, you can (usually) calculate an upper bound for $Q_i$ by relaxing the integrality constraints and maximizing Qi subject to the constraints. The only two issues here are (1) the LP might be unbounded and (2) if the problem is big enough, solving all those LPs (one for each i) might take too much time.

$\endgroup$
0

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.