Ist 0-1-Programmierung mit konstanter Anzahl von Einschränkungen polynomiell lösbar?

11

In der Arbeit "Integer-Programmierung mit einer festen Anzahl von Variablen" wurde gezeigt, dass Integer-Programmierungen mit einer konstanten Anzahl von Einschränkungen (oder Variablen) polynomiell lösbar sind.

Gilt dies für die 0-1-Programmierung?

cc.complexity-theory integer-programming Regelmäßigkeit
quelle

Ist 0-1-Programmierung nicht ein Sonderfall der Ganzzahlprogrammierung?

Nathann Cohen

3

Ich denke, der nicht triviale Teil ist folgender: Wenn Sie einen Black-Box-Algorithmus A haben, der ganzzahlige Programme mit einer konstanten Anzahl von Einschränkungen (aber beliebig vielen Variablen) lösen kann, ist es nicht offensichtlich, wie A zum Lösen von 0-1-Programmen verwendet wird mit einer konstanten Anzahl von Einschränkungen. Sie können nicht einfach Einschränkungen der Form

für jede Variable

hinzufügen .

0 \leq x_{i} \leq 1

$0 \le x_i \le 1$

x_{i}

$x_i$

Jukka Suomela

3

Was ist "ein 0-1-Programm mit einer konstanten Anzahl von Einschränkungen"? Zählen die Bedingungen

nicht?

0 \leq x_{i} \leq 1

$0\le x_i \le 1$

Jeffs

20

Ich gehe davon aus, dass mit "0-1-Programmierung mit einer konstanten Anzahl von Einschränkungen" das folgende Problem gemeint ist:

Maximieren Sie eine lineare Funktion von (x_1, x_2, ..., x_n) unter Berücksichtigung der Einschränkungen, dass jedes x_i in {0,1} ist, und einer konstanten Anzahl zusätzlicher linearer Einschränkungen.

Dieses Problem ist NP-vollständig, selbst mit 1 zusätzlichen Einschränkung, da 0-1 Rucksack in dieser Form geschrieben werden kann.

Robin Kothari
quelle

1

Auch "unbegrenzter Rucksack", bei dem Sie nur die Nicht-Negativitätsgrenzen und Integritätsbeschränkungen ohne die Obergrenzen von 1 haben, ist immer noch NP-hart.

Daveagp

0

Lenstra zeigte in dem genannten Papier, daß das ganzzahlige lineares Programm Feasibility Problem

$A_{m,n}$ $b \in \mathbb{Z}^m$
$x \in \mathbb{Z}^n$ $Ax \le b$

ist polynomiell lösbar, wenn n oder m konstant sind. (Beachten Sie das Fehlen einer Zielfunktion.) Dieses Ergebnis wird häufig bei der Analyse parametrisierter Probleme verwendet, dh es kann verwendet werden, um die Traktierbarkeit fester Parameter durch eine Reduktion nachzuweisen.

Muede
quelle

3

Ich bin nicht sicher, warum Sie dies gepostet haben, aber wenn Sie implizieren, dass der Unterschied zwischen der Machbarkeitsversion und der Optimierungsversion wichtig ist, dann ist dies nicht wichtig: Ein Polynom-Zeit-Algorithmus für die Machbarkeitsversion kann zur Lösung verwendet werden die Optimierungsversion auch in Polynomzeit durch Kombination mit binärer Suche.

Tsuyoshi Ito

-1

0-1 Ganzzahlprogrammierung oder binäre Ganzzahlprogrammierung (BIP) ist der Spezialfall der Ganzzahlprogrammierung, bei dem Variablen 0 oder 1 sein müssen (anstelle beliebiger Ganzzahlen). Dieses Problem wird auch als NP-hart eingestuft, und tatsächlich ist die Entscheidungsversion NP-vollständig.

Karan Sapra
quelle

3

Während sowohl IP als auch BIP NP-hart sind, sagt dies nicht viel darüber aus, ob IP und BIP mit einer konstanten Anzahl von Einschränkungen NP-hart sind. In der Tat ist IP mit einer konstanten Anzahl von Einschränkungen in P, während BIP mit einer konstanten Anzahl von Einschränkungen immer noch NP-hart ist.

Robin Kothari

-1

$k$ $2^k$

user8477
quelle

Ist 0-1-Programmierung mit konstanter Anzahl von Einschränkungen polynomiell lösbar?

Antworten: