0-1 Lineare Programmierung: Berechnung der optimalen Formulierung

14

Betrachte den dimensionalen Raum und sei eine lineare Beschränkung der Form , wobei , und .{ 0 , 1 } n c ein 1 x 1 + ein 2 x 2 + ein 3 x 3 + . . . + a n - 1 x n - 1 + a n x nk a iR x i{ 0 , 1 } k Rn{0,1}nca1x1+a2x2+a3x3+ ... +an1xn1+anxnkaiRxi{0,1}kR

Es ist klar, dass die Wirkung hat, in zwei Teilmengen und . enthält alle und nur die Punkte, die erfüllen , während alle und nur die Punkte enthält, die verfälschen .{ 0 , 1 } n S C S ¬ c S c c S ¬ c cc{0,1}nScS¬cSccS¬cc

Es sei angenommen, dass . Sei nun eine Teilmenge von so dass alle folgenden drei Aussagen gelten:O S c|Sc|nOSc

  1. O enthält genau Punkte.n
  2. Solche Punkte sind linear unabhängig.n
  3. Solche Punkte sind diejenigen in minimalem Abstand von der durch Hyperebene . Genauer gesagt sei der Abstand eines Punktes von der Hyperebene . Dann ist so dass 1 und 2 erfüllt, es ist der Fall, dass . Mit anderen Worten ist unter allen Teilmengen von die beide Bedingungen 1 und 2 erfüllen, diejenige, die die Summe der Abstände ihrer Punkte von der Hyperebene minimiert .c d ( x , c ) x { 0 , 1 } n c B S c B Σ x B d ( x , C ) Σ x O d ( x , c ) O S c cncd(x,c)x{0,1}ncBScBxBd(x,c)xOd(x,c)OScc

Fragen

  1. Ist es bei gegebenem möglich, effizient zu berechnen ? OcO
  2. Welches ist der bekannteste Algorithmus, um es zu berechnen?

 

Beispiel mit n=3

Beispiel mit n = 3

S¬c={(1,0,1)} , .O={(0,0,1),(1,1,1),(1,0,0)}

 

Update 12.05.2012

Motivation

Die Motivation ist, dass es mit möglich sein sollte, die optimale Bedingung zu bestimmen , da dies die Hyperebene sein sollte, die durch die Punkte in definiert wird . OcnO

Die optimale Bedingung ist diejenige, die zum optimalen Polytop .cP

Das optimale Polytop ist dasjenige, dessen Scheitelpunkte alle und nur die ganzzahligen Scheitelpunkte des anfänglichen Polytops (ein ganzzahliger Scheitelpunkt ist ein Scheitelpunkt, dessen Koordinaten alle ganzzahlig sind). PPP

Optimale Formulierung

Der Prozess kann für jeden Einschränkungs iteriert wird ein 0-1 L P Beispiel I , jedesmal Substituieren c mit seinem entsprechenden optimalen constraint c * . Am Ende wird dies zu optimalem Polytop führt P * von I . Dann wird , da die Scheitelpunkte P * sind alle und nur die ganze Zahl Vertices des anfänglichen Polytop P von I , jeder Algorithmus für L P verwendet werden kann , um die optimale ganzzahlige Lösung zu berechnen. Ich weiß , dass die Fähigkeit, berechnen P * effizient bedeuten würde PcLPIccPIPPILPP , jedoch steht noch folgende Zusatzfrage:P=NP

Zusätzliche Frage

Gibt es eine frühere Arbeit in dieser Richtung? Hat jemand bereits die Aufgabe des Rechnens untersucht, wenn man ein Polytop und sein entsprechendes optimales Polytop P voraussetzt ? Welcher Algorithmus ist dafür am bekanntesten?PP

Giorgio Camerani
quelle
Dies scheint NP-schwierig zu sein, wenn man es von der Teilmengen-Summe her reduziert. Bei gegebenen binären Ganzzahlen können wir testen, ob es eine Teilmenge gibt, die zu s summiert. Dann können wir testen, ob es einen Punkt auf der Hyperebene gibt: v 1 x 1 + + v 1 x n = s . Interessieren Sie sich für Annäherungen? v1,,vnsv1x1++v1xn=s
Colin McQuillan
@ColinMcQuillan: Die Frage war für eine genaue Lösung gedacht, mich interessieren aber sicherlich auch Annäherungen. Warum wandelst du deinen Kommentar nicht in eine Antwort um?
Giorgio Camerani
@ColinMcQuillan: Außerdem wird Ihre Hyperebene mit einer Gleichheit definiert, während meine mit einer Ungleichheit definiert wird. Sind Sie sicher, dass dies keinen Unterschied in Bezug auf die Härte macht? Ich habe das noch nicht überprüft, also frage ich nur.
Giorgio Camerani
Ich bin ein wenig über alle Beschränkungen verwechselt . Wenn Sie sich für Informationen über die konvexe Hülle der Suche S c dann gibt es viele Ergebnisse in den Operationen Literatur über die 0-1 Tornister Polytop Forschung. Bezüglich ungefährer Formulierungen siehe dies . OSc
Austin Buchanan

Antworten:

6

Dies scheint NP-schwierig zu sein, wenn man es von der Teilmengen-Summe her reduziert. Angenommen , wir ein effizientes Verfahren zu berechnen hatten . Wenn positive ganze Zahlen v 1 , ... , v n binär codiert sind, möchten wir testen, ob es eine Teilmenge gibt, die zu s summiert . Bereiten Sie dies vor, indem Sie alle Ganzzahlen ausgeben, die größer als s sind .Ov1,,vnss

Rufen Sie die Prozedur auf, um eine kleine Menge von Punkten zu erhalten, die v 1 x 1 + + v 1 x ns erfüllen und Ihre Minimalitätsbedingungen erfüllen (die Vorverarbeitung stellt | S c |n sicher ). Diese Menge enthält sicherlich einen Punkt auf der Hyperebene v 1 x 1 + + v 1 x n = s, falls es einen gibt.Ov1x1++v1xns|Sc|nv1x1++v1xn=s

Colin McQuillan
quelle
Vielleicht habe ich hier etwas Makroskopisches übersehen, aber ich habe 2 Fragen: 1) Wenn Sie "Gegebene binäre Ganzzahlen" sagen, was meinen Sie mit binär ? gehören in R . Vielleicht meinst du binär codiert? Oder wolltest du vielleicht positiv sagen? 2) Warum alle ganzen Zahlen rauswerfen, die größer als s sind ? Sie können zur Lösung beitragen. Zum Beispiel: v 1 = - 3 , v 2 = 7 , v 3 = - 5 ,v1,...,vnRs Wenn Sie v 2 wegwerfen, verlieren Sie die einzige Lösung { v 2 , v 3 } . v1=3,v2=7,v3=5,s=2v2{v2,v3}
Giorgio Camerani
2
Ich denke , was Colin Mittel ist , dass , wenn die Beschränkungskoeffizienten rationale Zahlen sind , in ihrer üblichen binären Darstellung, dann Ihr Problem scheint NP-hart. (Das Mischen von reellen Zahlen und NP-Härte ist immer schwierig.)ai
Jeffs
1
@GiorgioCamerani: Ich musste positiv sagen - ich habe meine Antwort aktualisiert.
Colin McQuillan
1

Mir scheint, dass Sie versuchen, an die konvexe Hülle der IP heranzukommen - im Wesentlichen ist dies das, was mit Schnittalgorithmen erreicht werden soll. Diese Methoden sind zwar theoretisch ansprechend, schneiden aber in der Praxis schlecht ab.

Es gibt alle Theorien zur Erzeugung gültiger Ungleichungen. Ein guter Ausgangspunkt wäre Shrijvers Buchtheorie der Integer-Programmierung.

AJ Student
quelle