Für die ganzzahlige lineare Programmierung in Boolesche Werte umwandeln

Ich möchte die folgende Einschränkung in einem ganzzahligen linearen Programm ausdrücken:

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

Ich habe bereits die ganzzahligen Variablen und mir wird versprochen, dass . Wie kann ich die obige Einschränkung in einer Form ausdrücken, die für die Verwendung mit einem ganzzahligen linearen Programmierlöser geeignet ist? $x,y$ $-100 \le x \le 100$

Dies erfordert vermutlich die Einführung einiger zusätzlicher Variablen. Welche neuen Variablen und Einschränkungen muss ich hinzufügen? Kann es mit einer neuen Variablen sauber gemacht werden? Zwei?

Entsprechend wird gefragt, wie die Einschränkung durchgesetzt werden soll

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

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

in dem Kontext, in dem ich bereits Einschränkungen habe, die implizieren und . $|x| \le 100$ $0 \le y \le 1$

(Mein Ziel ist es, einen Fehler in /cs//a/12118/755 zu beheben .)

linear-programming integer-programming DW
quelle

Was hast du versucht? Haben Sie versucht, einige Beispiele durchzuarbeiten, um festzustellen, ob Sie ein Muster sehen? Wenn ja, haben Sie versucht, eine Vermutung anzustellen und sie dann zu beweisen?

Brika

Heh! Ich sehe, was du dort getan hast , @Brika. Wenn Sie neugierig sind, was ich versucht habe, lesen Sie hier sowie diese Erklärung, warum das eigentlich falsch war . Wenn Sie meinen nächsten Versuch sehen möchten, lesen Sie meine Antwort . Vielen Dank, dass Sie meine alten Fragen gelesen haben. Wenn sie für die Zukunft verbessert werden können, würde ich gerne Ihre Vorschläge hören!

Das ist sehr gut. ;)

Brika

Antworten:

Ich denke, ich kann es mit einer zusätzlichen binären Variablen tun : $\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)$

Aktualisieren

Dies setzt voraus, dass eine stetige Variable ist . Wenn wir auf einen ganzzahligen Wert beschränken, kann die zweite Einschränkung vereinfacht werden zu: $x$ $x$

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

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

Erwin Kalvelagen
quelle

Ich habe dies korrekt überprüft, indem ich es mit einem kleinen Programm ausführlich getestet habe. Danke für die Lösung!

@ErwinKalvelagen, könnten Sie bitte Ihre Logik mit der binären Variablen Delta erklären, für einen allgemeineren Fall, zum Beispiel wenn y = {a: x> 0, b: x <0}.

Nick

@Nick Die binäre Variable wird verwendet, um ein 'OR'-Konstrukt zu modellieren. Sehen Sie hier eine Antwort auf Ihre Frage.

Erwin Kalvelagen

@ErwinKalvelagen, die großartige Antwort, ich habe versucht, Ihren Ansatz auf meine Frage hier cs.stackexchange.com/questions/64794/… anzuwenden .

Nick

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
quelle

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
quelle

x \leq 99

$x \leq 99$

x \leq 100

$x \leq 100$

x \geq - 99

$x \geq -99$

@ TLW, danke, dass du das verstanden hast! Ich habe meine Antwort bearbeitet, um den Fehler zu beheben. Ich habe es ausführlich mit einem kleinen Programm getestet und ich denke, es sollte jetzt korrekt sein.