2
$\begingroup$

Given a boolean variable $x$ and nonnegative integer variable $s$, I want to select $y = \begin{cases} 0 & \text{if} \ x = 0 \\ s & \text{if} \ x = 1 \end{cases}$. Currently in the problem, $s$ is the sum of $n$ boolean variables $x_1 + x_2 + \cdots + x_n$ so I want to compute $x \land x_1 + x \land x_2 + \cdots + x \land x_n$. However, computing each individual $x \land x_i$ requires its own variable and constraints and I'm wondering if its possible to use a constant number of variables and constraints.

$\endgroup$
2
  • $\begingroup$ If $s$ is an integer variable then it can't be the sum of boolean variables. If the sum is known you can just compute $xs$. $\endgroup$ Apr 28, 2022 at 6:32
  • $\begingroup$ @BjörnLindqvist It's possible that "s is an integer variable and s is the sum of n boolean variables x1 + ... + xn" was an informal way to say "s is an integer variable, and there is a linear equality constraint s = x1 + ... + xn". $\endgroup$
    – Stef
    Apr 28, 2022 at 9:25

1 Answer 1

3
$\begingroup$

Use the three inequalities

$$0 \le y \le s$$

$$y \le Mx$$

$$y \ge s - M(1-x)$$

where $M$ is a large constant, chosen to be larger than the largest possible value of $s$ (e.g., $M=n+1$ in your example).

$\endgroup$

Your Answer

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

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