Lineare Programmierung - Constraints - Hervorragende Bibliothek

Ich versuche, diese (einen kleinen Teil eines Projektes) zu kodieren, um die lineare Programmierung:Lineare Programmierung - Constraints

Für jedes Paket p wir seine Länge (xDimp) und Breite (yDimp) kennen. Außerdem haben wir die Länge (xTruck) und die Breite (yTruck) des Trucks. Alle Zahlen sind ganze Zahlen.

Aufgrund der Konstruktion der Pakete können sie nicht gedreht werden, wenn sie in einem LKW platziert werden.

Der Truck wird als Matrix von 2 Dimensionen dargestellt, nur mit x- und y-Koordinaten. Wir ignorieren die Höhe.

Entscheidungsvariablen:

- PXY [p, x, y] = Packung P ist in der Zelle mit dem oberen rechten Koordinaten (x, y)

- PBL [p, x, y] = die untere linke Zelle von p hat oberen rechten Koordinaten (x, y)

Example

Wie kann ich solche Einschränkungen schreiben PBL und PXY Variablen gesetzt? Ich sage, dass ich die Variable pbl setzen sollte, um sicherzustellen, dass das Paket in den LKW passt und der Wert von pxy variabel vom Wert von pbl abhängt.

Danke,

Quelle

2016-05-22 Cristian Morales

Ist das Hausaufgaben? –

Ist keine Hausaufgabe, aber ist ein kleiner Teil eines Projekts, das ich mache (selbstlernend), um lineare Programmierung und CPLEX zu lernen. –

Die Überlappungsbeschränkungen für dieses Packungsproblem können nicht in einer (kontinuierlichen) linearen Programmierformulierung angegeben werden. Sie benötigen dazu binäre Variablen. –

Dies ist eine Variante des Bin Packing Problems ist, eine zweidimensionale Packung von mehreren Rechtecken von Breiten und Höhen in einem umschließenden Rechteck (2BP) variiert. Wenn sie nur um 90 ° gedreht werden können, haben wir das rechtwinklige Packungsproblem für orthogonale Orientierungen, und in Ihrem Fall haben wir ein nicht-drehbares rechteckiges Packungsproblem. Seine rechnerische Komplexität ist NP-schwer, aber nicht durchführbar. Aus Ihrer Beschreibung ist das Problem bereits diskretisiert, wodurch die möglichen Platzierungen im Grid eingeschränkt werden, so dass das Optimum der fortlaufenden Version möglicherweise nicht mehr verfügbar ist.

Ein approch ist sicher Konfliktdiagramm im Voraus zu berechnen, die Platz für Ihre Suche darstellt und hält Informationen über die Überlappung der Rechtecke:

img.us svg file

Jede Kante repräsentiert einen Konflikt und jeder Knoten repräsentiert eine mögliche Platzierung in Ihrem LKW. Zwei Pakete p und q schneiden iff

img.us svg file

und paarweise.

Jetzt ist das Verpackungsproblem im Grid ein höchstmögliches unabhängiges Set-Problem im Konfliktdiagramm (MIS), vorausgesetzt, Sie möchten die Anzahl der Pakete auf dem LKW maximieren. Die MIS, die wiederum haben die folgende Formulierung ILP:

img.us svg file

Dies ist eine ganze Zahl Entspannung des MIS aber immer noch nicht gut für die Verzweigung und gebundene Lösungsmethode.Wenn C Clique in G ist dann jede unabhängige Menge kann daher höchstens einen Knoten wählen aus C, verwenden, um die folgende Bedingung:

img.us svg file

Das resultierende lineare Programm der Anzahl variabler exponentiell wächst.

Um weiter zu gehen, können Sie einen Meta Constraint Zufriedenheitsansatz versuchen. Erstens die folgenden contraints verwenden, um Ihre Pakete innerhalb des LKW sicher:

img.us svg file