Приведение к логическому, для целочисленного линейного программирования

Я хочу выразить следующее ограничение в целочисленной линейной программе:

y = {\begin{cases} 0 & if x = 0 \\ 1 & if x \neq 0. \end{cases}

$y = \begin{cases} 0 &\text{if } x=0\\ 1 &\text{if } x\ne 0. \end{cases}$

У меня уже есть целочисленные переменные и мне обещают, что . Как я могу выразить вышеупомянутое ограничение в форме, подходящей для использования с решателем целочисленного линейного программирования? $x,y$ $-100 \le x \le 100$

Это, вероятно, потребует введения некоторых дополнительных переменных. Какие новые переменные и ограничения мне нужно добавить? Можно ли сделать это чисто с помощью одной новой переменной? Два?

Эквивалентно, это спрашивает, как применить ограничение

y \neq 0 if and only if x \neq 0.

$y \ne 0 \text{ if and only if } x \ne 0.$

в контексте, где у меня уже есть ограничения, которые подразумевают и . $|x| \le 100$ $0 \le y \le 1$

(Моя цель - исправить ошибку в https://cs.stackexchange.com/a/12118/755 .)

linear-programming integer-programming DW
источник

Что вы пробовали? Вы пробовали проработать несколько примеров, чтобы увидеть, видите ли вы образец? Если да, пытались ли вы сделать предположение, а затем попытались доказать это?

Брика

Хех! Я вижу, что ты там сделал , @Brika. Если вам интересно посмотреть, что я попробовал, посмотрите здесь, а также объяснение, почему это было на самом деле неправильно . Если вы хотите увидеть мою следующую попытку, посмотрите мой ответ . Спасибо за чтение моих старых вопросов, и, если они могут быть улучшены в будущем, я хотел бы услышать любые ваши предложения!

Это очень хорошо. ;)

Брика

Ответы:

Я думаю, что могу сделать это с одной дополнительной двоичной переменной $\delta \in \{0,1\}$ :

- 100 y \leq x \leq 100 y

$-100y \le x \le 100 y$

0.001 y - 100.001 δ \leq x \leq - 0.001 y + 100.001 (1 - δ)

$0.001y-100.001\delta \le x \le -0.001y+100.001 (1-\delta)$

Обновить

$x$ $x$

y - 101 δ \leq x \leq - y + 101 (1 - δ)

$y-101\delta \le x \le -y+101 (1-\delta)$

Эрвин Кальвелаген
источник

Я подтвердил это, тщательно протестировав его с помощью небольшой программы. Спасибо за решение!

@ErwinKalvelagen, не могли бы вы объяснить вашу логику с помощью бинарной переменной delta, например, для более общего случая, если y = {a: x> 0, b: x <0}.

Ник

@Nick Бинарная переменная используется для моделирования конструкции «ИЛИ». Смотрите здесь для ответа на ваш вопрос.

Эрвин Кальвелаген

@ErwinKalvelagen, отличный ответ, я попытался применить ваш подход к моему вопросу здесь. Cs.stackexchange.com/questions/64794/… .

Ник

x

$x$

x

$x$

$0 \leq x \leq N$ $N=100$

$0 \leq z_1, z_2, z \leq 1$
$x - N(1-z_1) \leq 0$
$-x -Nz_1 \leq -1$
$-x -N(1-z_2) \leq 0$
$x -Nz_2 \leq -1$
$z_1 + z_2 - 1 \leq z$
$z \leq z_1$
$z \leq z_2$

$z_1 = 1 \iff x \leq 0$ $z_2 = 1 \iff x \geq 0$ $z = z_1 \land z_2$

Pramod
источник

z = 1 - y

$z=1-y$

x = 100

$x=100$

y = 1

$y=1$

z = 0

$z=0$

z_{1}, z_{2}

$z_1,z_2$

x - N z_{2} \leq - 1

$x-Nz_2 \le -1$

x < N

$x<N$

x \leq 99

$x \le 99$

x = 99

$x=99$

y = 1

$y=1$

y = 0

$y=0$

x

$x$

- N \leq x \leq N

$-N \le x \le N$

0 \leq x \leq N

$0 \le x \le N$

$t,u$ $t=1$ $x \ge 0$ $u=1$ $x \le 0$ $y=\neg(t \land u)$

\begin{aligned} 0 & \leq t, u, y \leq 1 \\ 1 + x & \leq 101 t \leq 101 + x \\ 1 - x & \leq 101 u \leq 101 - x \\ t + u - 1 & \leq 1 - y \\ 1 - y & \leq t \\ 1 - y & \leq u \end{aligned}

$\begin{align*} 0 &\le t,u,y \le 1\\ 1+x &\le 101t \le 101 + x\\ 1-x &\le 101u \le 101-x\\ t+u-1 &\le 1-y\\ 1-y &\le t\\ 1-y &\le u \end{align*}$

DW
источник

x \leq 99

$x \leq 99$

x \leq 100

$x \leq 100$

x \geq - 99

$x \geq -99$

@ TLW, спасибо, что поймали это! Я отредактировал свой ответ, чтобы исправить ошибку. Я исчерпывающе проверил это с помощью небольшой программы и думаю, что сейчас это должно быть правильно.