Integer-Programmierung - Integer programming

Ein ganzzahliges Programmierproblem ist ein mathematisches Optimierungs- oder Machbarkeitsprogramm , bei dem einige oder alle Variablen auf ganze Zahlen beschränkt sind . In vielen Situationen bezieht sich der Begriff auf die ganzzahlige lineare Programmierung (ILP), bei der die Zielfunktion und die Nebenbedingungen (außer den ganzzahligen Nebenbedingungen) linear sind .

Integer-Programmierung ist NP-vollständig . Insbesondere der Spezialfall der 0-1 ganzzahligen linearen Programmierung, bei dem Unbekannte binär sind und nur die Restriktionen erfüllt werden müssen, ist eines der 21 NP-vollständigen Probleme von Karp .

Wenn einige Entscheidungsvariablen nicht diskret sind, wird das Problem als gemischt-ganzzahliges Programmierproblem bezeichnet.

Kanonisches und Standardformular für ILPs

Bei der ganzzahligen linearen Programmierung unterscheidet sich die kanonische Form von der Standardform . Ein ganzzahliges lineares Programm in kanonischer Form wird wie folgt ausgedrückt (beachten Sie, dass es der Vektor ist, der entschieden werden muss):

und ein ILP in Standardform wird ausgedrückt als

wobei Vektoren sind und eine Matrix ist, in der alle Einträge ganze Zahlen sind. Wie bei linearen Programmen können auch ILPs, die nicht in der Standardform vorliegen, in die Standardform umgewandelt werden, indem Ungleichungen beseitigt, Slack-Variablen ( ) eingeführt und nicht vorzeichenbeschränkte Variablen durch die Differenz zweier vorzeichenbeschränkter Variablen ersetzt werden

Beispiel

IP-Polytop mit LP-Relaxation

Die rechte Grafik zeigt das folgende Problem.

Die zulässigen ganzzahligen Punkte sind rot dargestellt, und die roten gestrichelten Linien zeigen ihre konvexe Hülle an, die das kleinste konvexe Polyeder ist, das alle diese Punkte enthält. Die blauen Linien zusammen mit den Koordinatenachsen definieren das Polyeder der LP-Relaxation, das durch die Ungleichungen ohne die Integritätsbeschränkung gegeben ist. Ziel der Optimierung ist es, die schwarze gestrichelte Linie so weit nach oben zu verschieben, dass sie das Polyeder noch berührt. Die optimalen Lösungen des ganzzahligen Problems sind die Punkte , und die beide einen objektiven Wert von 2. Der einzigartige Optimum der Entspannung ist mit Ziel - Wert von 2,8. Wenn die Lösung der Relaxation auf die nächsten ganzen Zahlen gerundet wird, ist dies für das ILP nicht möglich.

Nachweis der NP-Härte

Das Folgende ist eine Reduktion von minimaler Scheitelüberdeckung auf ganzzahlige Programmierung, die als Beweis für die NP-Härte dienen soll.

Sei ein ungerichteter Graph. Definieren Sie ein lineares Programm wie folgt:

Da die Beschränkungen entweder auf 0 oder 1 begrenzen , ist jede zulässige Lösung des Ganzzahlprogramms eine Teilmenge von Scheitelpunkten. Die erste Einschränkung impliziert, dass mindestens ein Endpunkt jeder Kante in dieser Teilmenge enthalten ist. Daher beschreibt die Lösung eine Scheitelpunktüberdeckung. Zusätzlich kann eine gegebene Scheitelpunktüberdeckung C für jeden auf 1 und für jeden auf 0 gesetzt werden, wodurch wir eine zulässige Lösung für das Integer-Programm erhalten. Daraus können wir schließen, dass wir, wenn wir die Summe von minimieren , auch die minimale Knotenüberdeckung gefunden haben.

Varianten

Die gemischt-ganzzahlige lineare Programmierung ( MILP ) beinhaltet Probleme, bei denen nur einige der Variablen, , auf ganze Zahlen beschränkt sind, während andere Variablen nicht-ganzzahlig sein dürfen.

Die lineare Null-Eins-Programmierung (oder binäre ganzzahlige Programmierung ) beinhaltet Probleme, bei denen die Variablen entweder auf 0 oder 1 beschränkt sind. Jede beschränkte ganzzahlige Variable kann als eine Kombination von binären Variablen ausgedrückt werden. Bei einer gegebenen Integer-Variablen kann die Variable beispielsweise durch binäre Variablen ausgedrückt werden :

Anwendungen

Es gibt zwei Hauptgründe für die Verwendung von Integer-Variablen beim Modellieren von Problemen als lineares Programm:

  1. Die ganzzahligen Variablen stellen Größen dar, die nur ganzzahlig sein können. Es ist beispielsweise nicht möglich, 3,7 Autos zu bauen.
  2. Die Integer-Variablen stellen Entscheidungen dar (zB ob eine Kante in einen Graphen aufgenommen werden soll ) und sollten daher nur den Wert 0 oder 1 annehmen.

Diese Überlegungen treten in der Praxis häufig auf und so kann die ganzzahlige lineare Programmierung in vielen Anwendungsgebieten eingesetzt werden, von denen einige im Folgenden kurz beschrieben werden.

Produktionsplanung

Die gemischt-ganzzahlige Programmierung hat viele Anwendungen in der industriellen Produktion, einschließlich der Job-Shop-Modellierung. Ein wichtiges Beispiel in der landwirtschaftlichen Produktionsplanung ist die Bestimmung des Produktionsertrags für mehrere Pflanzen, die sich Ressourcen teilen können (zB Land, Arbeit, Kapital, Saatgut, Dünger usw.). Ein mögliches Ziel besteht darin, die Gesamtproduktion zu maximieren, ohne die verfügbaren Ressourcen zu überschreiten. In einigen Fällen kann dies in Form eines linearen Programms ausgedrückt werden, aber die Variablen müssen auf Ganzzahl beschränkt sein.

Terminplanung

Diese Probleme betreffen die Dienst- und Fahrzeugplanung in Verkehrsnetzen. Problematisch kann es beispielsweise sein, Busse oder U-Bahnen einzelnen Linien so zuzuordnen, dass ein Fahrplan eingehalten werden kann und diese auch mit Fahrern auszustatten. Hier zeigen binäre Entscheidungsvariablen an, ob einer Strecke ein Bus oder eine U-Bahn und ein Fahrer einem bestimmten Zug oder einer U-Bahn zugeordnet ist. Die Null-Eins-Programmiertechnik wurde erfolgreich angewendet, um ein Projektauswahlproblem zu lösen, bei dem Projekte sich gegenseitig ausschließen und/oder technologisch voneinander abhängig sind. Es wird in einem Sonderfall der Integer-Programmierung verwendet, bei der alle Entscheidungsvariablen Integer sind. Es kann die Werte entweder als Null oder Eins annehmen.

Territoriale Aufteilung

Das Problem der territorialen Aufteilung oder des Distrikts besteht darin, eine geographische Region in Distrikte zu unterteilen, um einige Operationen unter Berücksichtigung verschiedener Kriterien oder Einschränkungen zu planen. Einige Voraussetzungen für dieses Problem sind: Kontiguität, Kompaktheit, Ausgewogenheit oder Gerechtigkeit, Respekt vor natürlichen Grenzen und sozioökonomische Homogenität. Einige Anwendungen für diese Art von Problem umfassen: politische Bezirke, Schulbezirke, Gesundheitsdienste und Abfallwirtschaftsbezirke.

Telekommunikationsnetze

Das Ziel dieser Probleme besteht darin, ein Netzwerk von zu installierenden Leitungen so zu entwerfen, dass ein vordefinierter Satz von Kommunikationsanforderungen erfüllt wird und die Gesamtkosten des Netzwerks minimal sind. Dies erfordert eine Optimierung sowohl der Topologie des Netzes als auch der Einstellung der Kapazitäten der verschiedenen Leitungen. In vielen Fällen sind die Kapazitäten auf ganzzahlige Mengen beschränkt. Üblicherweise gibt es je nach verwendeter Technologie zusätzliche Restriktionen, die als lineare Ungleichungen mit ganzzahligen oder binären Variablen modelliert werden können.

Mobilfunknetze

Die Aufgabe der Frequenzplanung in GSM- Mobilfunknetzen besteht darin, verfügbare Frequenzen auf die Antennen zu verteilen, damit Benutzer bedient werden können und Störungen zwischen den Antennen minimiert werden. Dieses Problem kann als ganzzahliges lineares Programm formuliert werden, bei dem binäre Variablen anzeigen, ob einer Antenne eine Frequenz zugewiesen ist.

Andere Anwendungen

Algorithmen

Der naive Weg, ein ILP zu lösen, besteht darin, einfach die Einschränkung zu entfernen, dass x ganzzahlig ist, das entsprechende LP zu lösen (als LP-Relaxation des ILP bezeichnet) und dann die Einträge der Lösung auf die LP-Relaxation zu runden. Aber diese Lösung kann nicht nur nicht optimal, sondern auch nicht machbar sein; das heißt, es kann eine Einschränkung verletzen.

Verwendung der totalen Unimodularität

Während im Allgemeinen die Lösung der LP-Relaxation nicht garantiert integral ist , ist jede zulässige Basislösung ganzzahlig, wenn der ILP die Form hat , dass where und alle ganzzahligen Einträge haben und vollständig unimodular sind. Folglich ist die vom Simplex-Algorithmus zurückgegebene Lösung garantiert ganzzahlig. Um zu zeigen, dass jede zulässige Basislösung ganzzahlig ist, sei eine beliebige zulässige Basislösung . Da ist machbar, das wissen wir . Seien die Elemente, die den Basisspalten für die Basislösung entsprechen . Per Definition einer Basis gibt es eine quadratische Untermatrix von mit linear unabhängigen Spalten, so dass .

Da die Spalten linear unabhängig sind und quadratisch ist , ist nicht singulär, und daher nach Voraussetzung ist unimodular und so . Da es sich um Nichtsingular handelt, ist es auch invertierbar und daher . Definitionsgemäß . Hier bezeichnet die adjugate von und ist ein integraler Bestandteil , da ist ein integraler Bestandteil. Deshalb,

Wenn also die Matrix eines ILP völlig unimodular ist, kann anstelle eines ILP-Algorithmus das Simplex-Verfahren verwendet werden, um die LP-Relaxation zu lösen, und die Lösung wird ganzzahlig sein.

Genaue Algorithmen

Wenn die Matrix nicht vollständig unimodular ist, gibt es eine Vielzahl von Algorithmen, die verwendet werden können, um ganzzahlige lineare Programme exakt zu lösen. Eine Klasse von Algorithmen sind Schnittebenenverfahren, die funktionieren, indem sie die LP-Relaxation lösen und dann lineare Beschränkungen hinzufügen, die die Lösung dahin treiben, ganzzahlig zu sein, ohne ganzzahlige zulässige Punkte auszuschließen.

Eine weitere Klasse von Algorithmen sind Varianten der Branch-and-Bound- Methode. Zum Beispiel die Verzweigungs- und Schnittmethode , die sowohl Verzweigungs- und gebundene als auch Schnittebenenmethoden kombiniert. Branch-and-Bound-Algorithmen haben gegenüber Algorithmen, die nur Schnittebenen verwenden, eine Reihe von Vorteilen. Ein Vorteil besteht darin, dass die Algorithmen frühzeitig beendet werden können und solange mindestens eine ganzzahlige Lösung gefunden wurde, eine praktikable, wenn auch nicht unbedingt optimale Lösung zurückgegeben werden kann. Außerdem können die Lösungen der LP-Relaxationen verwendet werden, um eine Worst-Case-Schätzung zu liefern, wie weit die zurückgegebene Lösung von der Optimalität entfernt ist. Schließlich können Branch- und Bound-Methoden verwendet werden, um mehrere optimale Lösungen zurückzugeben.

Exakte Algorithmen für eine kleine Anzahl von Variablen

Angenommen ist ein m -by- n ganzzahlige Matrix und ist eine m -mit-1 ganzzahligen Vektor. Wir konzentrieren uns auf das Machbarkeitsproblem, das darin besteht, zu entscheiden, ob es einen n- mal-1-Vektor gibt, der erfüllt .

Sei V der maximale Absolutwert der Koeffizienten in und . Wenn n (die Anzahl der Variablen) eine feste Konstante ist, dann kann das Machbarkeitsproblem zeitpolynomiell in m und log V gelöst werden . Dies ist für den Fall n = 1 trivial . Der Fall n = 2 wurde 1981 von Herbert Scarf gelöst . Der allgemeine Fall wurde 1983 von Hendrik Lenstra gelöst , der Ideen von Laszlo Lovasz und Peter van Emde Boas kombinierte .

Im Spezialfall von 0-1 ILP ist der Algorithmus von Lenstra äquivalent zur vollständigen Aufzählung: Die Anzahl aller möglichen Lösungen ist fest (2 n ) und die Überprüfung der Durchführbarkeit jeder Lösung kann in der Zeit erfolgen poly( m , log V ) . Im allgemeinen Fall, in dem jede Variable eine beliebige ganze Zahl sein kann, ist eine vollständige Aufzählung unmöglich. Hier verwendet der Algorithmus von Lenstra Ideen aus der Geometrie der Zahlen . Es transformiert das ursprüngliche Problem in ein äquivalentes Problem mit der folgenden Eigenschaft: Entweder ist die Existenz einer Lösung offensichtlich, oder der Wert (der n- ten Variablen) gehört zu einem Intervall, dessen Länge durch eine Funktion von n begrenzt ist . Im letzteren Fall wird das Problem auf eine begrenzte Anzahl von niederdimensionalen Problemen reduziert.

Der Algorithmus von Lenstra impliziert, dass ILP auch im dualen Fall in polynomieller Zeit lösbar ist, in dem n variiert, aber m (die Anzahl der Beschränkungen) konstant ist.

Der Algorithmus von Lenstra wurde anschließend von Kannan und Frank und Tardos verbessert. Die verbesserte Laufzeit ist , wobei die Anzahl der Eingangsbits ist, die in .

Heuristische Methoden

Da ganzzahlige lineare Programmierung NP-hart ist , sind viele Probleminstanzen hartnäckig und daher müssen stattdessen heuristische Methoden verwendet werden. Beispielsweise kann die Tabu-Suche verwendet werden, um nach Lösungen für ILPs zu suchen. Um die Tabu-Suche zum Lösen von ILPs zu verwenden, können Bewegungen als Inkrementieren oder Dekrementieren einer ganzzahligen eingeschränkten Variablen einer zulässigen Lösung definiert werden, während alle anderen ganzzahligen eingeschränkten Variablen konstant gehalten werden. Dann wird nach den uneingeschränkten Variablen aufgelöst. Das Kurzzeitgedächtnis kann aus zuvor ausprobierten Lösungen bestehen, während das Mittelzeitgedächtnis aus Werten für die ganzzahligen eingeschränkten Variablen bestehen kann, die zu hohen objektiven Werten geführt haben (vorausgesetzt, der ILP ist ein Maximierungsproblem). Schließlich kann das Langzeitgedächtnis die Suche nach ganzzahligen Werten lenken, die zuvor noch nicht ausprobiert wurden.

Andere heuristische Methoden, die auf ILPs angewendet werden können, umfassen

Daneben gibt es noch eine Vielzahl anderer problemspezifischer Heuristiken, wie beispielsweise die k-opt-Heuristik für das Travelling-Salesman-Problem. Ein Nachteil heuristischer Verfahren besteht darin, dass bei Fehlschlagen einer Lösung nicht festgestellt werden kann, ob es daran liegt, dass es keine zulässige Lösung gibt oder ob der Algorithmus einfach keine finden konnte. Außerdem ist es in der Regel unmöglich zu quantifizieren, wie nahe eine Lösung, die von diesen Methoden zurückgegeben wird, am Optimum liegt.

Sparse-Integer-Programmierung

Es kommt oft vor, dass die Matrix, die das Integer-Programm definiert, spärlich ist . Dies tritt insbesondere dann auf, wenn die Matrix eine Blockstruktur aufweist, was bei vielen Anwendungen der Fall ist. Die Sparsity der Matrix kann wie folgt gemessen werden. Der Graph von hat Scheitelpunkte, die den Spalten von entsprechen , und zwei Spalten bilden eine Kante, wenn er eine Zeile hat, in der beide Spalten Einträge ungleich null haben. Äquivalent entsprechen die Scheitelpunkte Variablen, und zwei Variablen bilden eine Kante, wenn sie eine Ungleichung teilen. Die sparsity Maß der das Minimum zwischen der Baumtiefe des Graphen und die Baumtiefe des Graphen des Transponierte . Sei das numerische Maß von definiert als der maximale Absolutwert eines beliebigen Eintrags von . Sei die Anzahl der Variablen des Integer-Programms. Dann wurde 2018 gezeigt, dass die ganzzahlige Programmierung in stark polynomialer und festparametrischer lenkbarer Zeit, parametrisiert durch und , gelöst werden kann . Das heißt, für einige berechenbare Funktionen und einige Konstanten kann die ganzzahlige Programmierung zeitlich gelöst werden . Insbesondere ist die Zeit unabhängig von der rechten Seite und der Zielfunktion . Im Gegensatz zum klassischen Ergebnis von Lenstra, bei dem die Anzahl der Variablen ein Parameter ist, ist hier die Anzahl der Variablen außerdem ein variabler Teil der Eingabe.

Siehe auch

Verweise

Weiterlesen

Externe Links