≡

Benutzer­handbuch

Vorwort

ermöglicht wirtschaftliche Abläufe zu organisieren, abzustimmen und zu optimieren. Die involvierten Prozesse werden dafür in ein mathematisches Modell überführt, das sich durch ein gemischt-ganzzahliges System von (linearen) Gleichungen, Ungleichungen und geeigneter Zielfunktionen (GGL-S) darstellen lässt.

Diesen (einmaligen) Modelllierungsprozess müssen Sie selbst bzw. ein Mathematiker Ihres Vertrauens übernehmen. Aber keine Angst - dieser Leitfaden wird Sie anhand verschiedener praxis-relevanter Beispiele an dieses Handwerk heranführen.

bestimmt (optimale) Lösungen für dieses modellierte System. Die Lösungen lassen sich auf die ursprünglichen Prozesse zurücktransformieren und liefern schließlich optimierte Strategien für deren Ablauf.

Für diese Aufgabe verwendet einen Gitter-basierten Ansatz und implementiert Methodiken, die ihren Ursprung in der Dissertation Gitterbasenreduktion mit Random Sampling und heuristischen Methoden haben.

Es werden Ihnen nun verschiedene Problemstellungen vorgestellt, die in GGL-Systemen resultieren und Sie werden kurz in die mathematische Modellbildung entführt. Nach diesem Exkurs werden Sie die vielfältigen Optionen von kennenlernen und bekommen in einfachen Tutorials das für die Anwendung erforderliche Wissen vermittelt.

Problemstellungen

Die nachfolgenden (exemplarischen) Probleme sollen die Herangehensweise verdeutlichen, wie sie ihre tatsächlichen, realen Prozesse in eine Form bringen können, so dass sie mit gelöst werden können. Wenn Sie in der nachfolgenden Auflistung ein Problem gefunden haben, das ihrem Prozess (mehr oder weniger) in analoger Weise entspricht, dann sollten Sie dieses als Basis für die Formulierung Ihres eigene Szenarios verwenden.

Kompositionsprobleme

Ladeproblem

Es seien n Objekte mit Nutzwerten c1,c2,,cn und ihren jeweiligen Gewichten g1,g2,,gn gegeben. In einen Container mit der Kapazität K sollen derart Objekte gepackt werden, dass bei gleichzeitiger Einhaltung dessen Fassungsvermögens, die Summe über die Nutzwerte aller verstauten Objekte maximal wird.

Die mathematische Formulierung hierzu lautet:

Maximiere
n
∑ cixi
i=1
so dass
n
∑ gixiK
i=1

und xi0,1 für i=1,2,,n

Demnach landet das i-te Objekt genau dann im Container, wenn der Lösungsvektor an der i-ten Position eine 1 enthält, bzw. bleibt im Falle eines Eintrags gleich 0 unberücksichtigt.

In der Literatur wird das Ladeproblem auch als Rucksackproblem bezeichnet, weil sich die geschilderte Fragestellung insbesondere beim Packen eines Rucksacks bzw. Koffers stellt.

Mischungsproblem

Das Mischungsproblem ergibt sich aus Fragestellungen der Zusammensetzung von Baustoffen, Diätplänen oder Futtermitteln.

Betrachten Sie beispielsweise folgendes Problem:

Ein Futtermittelkonzern hat mehrere Nährstoffpräparate für die Zusammensetzung eines neuartigen Spezialfutters zur Auswahl. Das Spezialfutter soll ein vorgegebenes Mindestmaß an Nährstoffen bereitstellen und dabei möglichst preisgünstig sein.

Die Zusammensetzung der Nährstoffpräparate und die geforderten Mindestwerte für das Spezialfutter in tabellenhafter Darstellung:

Kohlenhydrate Proteine Vitamine Kosten
Kraftfutter 20 15 5 12 €
Pflanzenteile 10 3 10 7 €
Getreidepräparat 12 2 3 9 €
Mastfutter 30 15 5 18 €
Mindestmenge 50 30 40

Es soll nun entschieden werden, welche Präparate für die Produktion des Spezialfutters zu verwenden sind, um kostenminimal und bedarfsgerecht zu produzieren.

Die Antwort liefert wiederum ein lineares Gleichungssystem, dessen Lösungsvektor (x1,x2,x3,x4) die Anteile an Kraftfutter, Pflanzenteilen, Getreidepräparaten und Mastfutter enthält, die eine kostenminimale Produktion des Futtermix, bei gleichzeitiger Einhaltung der Mindestmengen, sicherstellen.

In dieser Form verlangt das System noch keine Ganzzahligkeit des Lösungsvektors - um allerdings zu berücksichtigen, das (beispielsweise) Mastfutter nur in kompletten Einheiten verarbeiten werden darf, ist ein GGL-System unabdinglich:

Minimiere 12x17x29x318x4

so dass 20x110x212x330x450,
15x13x22x315x430,
5x110x23x35x440,

0x1K1, 0x2K2,
0x3K3, 0x4K4

und x1,x2,x3, x4

( Ki bezeichnet für i=1,2,3,4 den Vorrat an Nährstoffpräparaten )

Einkaufsprobleme

Bundleproblem

Für die Produktion von Elektrogeräten benötigt eine Firma täglich eine gewisse Anzahl von Kondensatoren, Widerständen und Platinen. Die Materialien können dabei nur in vorgegebenen Stückzahlen (Bundles) vom Großhandel eingekauft werden. Das Ziel der Elektrogerätefirma besteht darin, die Angebote so zu kombinieren, dass einerseits der Bedarf gestillt ist, andererseits aber nicht unnötig viel Geld ausgegeben wird.

Die Bundle-Angebote der Großhändler:

Kondensatoren Widerstände Platinen Preis
Großhändler A 20000 15000 5000 1000 €
Großhändler B 16000 3000 10000 800 €
Großhändler C 16000 10000 8000 750 €
Großhändler A 20000 0 0 450 €
Großhändler B 10000 0 4000 300 €
Großhändler C 0 3000 0 200 €
Großhändler C 0 0 4000 100 €
Mindestbedarf 40000 30000 20000

Damit ergibt sich die mathematische Formulierung:

Minimiere 1000x1800x2750x3450x4300x5200x6100x7

so dass 20000x116000x216000x320000x410000x540000,
15000x13000x210000x33000x630000,
5000x110000x28000x34000x54000x720000,

0x14, 0x210,
0x33, 0x42, 0x55,
0x610, 0x75,

xi für i=1,2,,7

Zur Ermittlung der preiswertesten Angebotskombination müssten bereits in diesem einfachem Beispiel 261360 verschiedene Varianten überprüft werden, um mit absoluter Sicherheit sagen zu können, dass es sich dabei um die beste aller möglichen Kombinationen handelt.

Lagerhaltungsproblem

Ein Einzelhändler hat Bedarf an n verschiedenen Gütern und hat für jedes Gut ein maximale Lagerkapazität. Er kann die benötigten Gütern von m Großhändlern kaufen, die die Güter jeweils mit einer Mindest- und Maximalabgabe (mi,j, Mi,j) zu einem vorgegebenen Preis pi,j abgeben. Ziel des Einzelhändlers ist es, den Bedarf bj für jedes Gut zu stillen, die jeweilige Lagerkapazität lj nicht zu überschreiten und dabei letztendlich die Gesamtkosten für die zu kaufenden Güter zu minimieren.
Minimiere
n m
∑ ∑ xi,jpi,j
i=1 j=1

so dass bi
m
∑ xi,j
j=1
li für i=1,2,,n
mi,jxi,jMi,j für i=1,2,,n bzw. j=1,2,,m

und xi,j für i=1,2,,n bzw. j=1,2,,m

Die gesuchte Variable xi,j repräsentiert die Anzahl der Einheiten vom Gut i, die der Einzehlhändler vom Großhändler j kaufen sollte, um seine Kosten zu minimieren.

Verkaufsproblem

Eine Elektrogeräte produzierende Firma möchte Ihre Produkte gewinnbringend auf dem freien Markt verkaufen. Sie hat verschiedene Angebote diverser Elektroverbrauchermärkte vorliegen. Welche Angebote sollten mit der vorhandenen Menge an Geräten befriedigt werden, um den maximal möglichen Verkaufsgewinn zu erzielen?

Die Angebotsdaten der Verbrauchermärkte:

Computer Fernseher Tablet-PC Kaufangebot
Verbrauchermarkt A 200 150 50 100000 €
Verbrauchermarkt B 160 30 100 80000 €
Verbrauchermarkt C 160 100 80 75000 €
Verbrauchermarkt A 200 0 0 45000 €
Verbrauchermarkt B 100 0 40 30000 €
Verbrauchermarkt C 0 30 0 20000 €
Verbrauchermarkt C 0 0 40 10000 €
Produktionsmenge 400 300 200

Die mathematische Modellierung lautet folgendermaßen:

Maximiere 100000x180000x275000x345000x430000x520000x610000x7

so dass 200x1160x2160x3200x4100x5400,
150x130x2100x330x6300,
50x1100x280x340x540x7200,

0x12, 0x22,
0x32, 0x42, 0x54,
0x610, 0x75,

xi für i=1,2,,7

Auslastungsproblem

Ein Betrieb setzt m Maschinen zur Herstellung von n verschiedenen Bauteilen Bj ein. Die Maschinen sind für die Herstellung der Bauteile unterschiedlich gut geeignet, was sich in der Herstellungszeit ti,j niederschlägt, die von der i-ten Maschine benötigt wird, um das j-te Bauteil zu produzieren. Es soll nun von jedem Bauteil Bj eine vorgegebene Anzahl bj produziert werden, und zwar derart, dass die Zeit, die für die Produktion aller Bauteile benötigt wird, minimiert wird - was mit einer optimalen Auslastung der Maschinen einhergeht.

Es wird also eine Matrix xmn gesucht, die nachstehendes Problem löst:

Minimiere
m n
∑ ∑ xi,jti,j
i=1 j=1

so dass
m
∑ xi,j=bj
i=1
für j=1,2,,n

und 0xi,jbj für 1im bzw. 1jn

Sollte die i-te Maschine für die Produktion des j-ten Bauteils nicht geeignet sein, ist in dem Modell die entsprechende Variable xi,j durch eine 0 zu ersetzen.

In der nachfolgenden Tabellen werden beispielhaft die Herstellungszeiten einiger Bauteile auf verschiedenene Maschinen gelistet. Der eigentliche Bedarf findet sich schließlich am Ende der Tabelle:

Radlager (B1) Zahnrad (B2) Rahmenteil (B3) Kurbelwelle (B4) Zylinder (B5)
Fräsmaschine M1 45 15 30 35 90
Fräsmaschine M2 20 10 15 40 -
Fräsmaschine M3 - 5 20 - 45
Fräsmaschine M4 20 - - 30 -
Fräsmaschine M5 - 10 40 - -
Fräsmaschine M6 30 20 60 45 120
Bedarf 40 100 20 50 30

Man erhält in diesem speziellen Fall:

Minimiere 45x1,115x1,230x1,335x1,490x1,520x2,110x2,215x2,340x2,45x3,220x3,345x3,520x4,130x4,410x5,240x5,330x6,120x6,260x6,345x6,4120x6,5

so dass x1,1x2,1x4,1x6,1=40,
x1,2x2,2x3,2x5,2x6,2=100,
x1,3x2,3x3,3x5,3x6,3=20,
x1,4x2,4x4,4x6,4=50,
x1,5x3,5x6,5=30,

x2,5=0, x3,1=0, x3,4=0, x4,2=0, x4,3=0, x4,5=0, x5,1=0, x5,4=0, x5,5=0,

0xi,140, 0xi,2100, 0xi,320, 0xi,450, 0xi,530 für i=1,2,,6

xi,j für 1i6 und 1j5

Produktionsproblem

Ein Hersteller produziert m unterschiedliche Produkte, wobei für die Produktion eines Produktes Pi diverse Bauteile Bj (1jn) benötigt werden. Welche und wieviele Produkte sind mit dem Vorrat an Bauteilen zu produzieren, damit der Gewinn maximiert, die Mindest- und Höchstproduktionsmengen eingehalten und außerdem keine Ressourceneinschränkung verletzt wird?

Der Verkaufspreis von Pi wird mit pi und die Herstellungskosten mit hi bezeichnet. Der Vorrat an Bauteilen des Typs Bj wird abgekürzt mit bj, die maximale Produktionsmenge eines Produkts mit ui und die Mindestproduktionsmenge mit li. Die Kosten eines Bauteils Bj betragen cj und die Anzahl der benötigten Bauteile Bj zur Produktion von Pi wird deklariert mit bi,j.

Demnach wird ein Vektor xm gesucht, der das folgende Problem löst:

Maximiere
m n
∑ xipihi ∑ bi,jcj
i=1 j=1

so dass 0
m
∑ xibi,j
i=1
bj für j=1,2,,n
und lixiui für i=1,2,,m

Mit diesem einfachem und flexiblem Modell kann in Echtzeit auf Änderungen bei Bauteilpreisen oder Herstellungskosten reagiert werden.

Transportproblem

Das klassische Transportproblem wird auch als das "Problem des Handlungsreisenden" bezeichnet und lautet:

Ein Reisender möchte ausgehend von einer vorgegebenen Stadt eine Rundreise durch n Städte machen und zwar derart, das der Weg, den er dabei zurücklegen muss, minimal wird.
Rundreise bedeutet dabei, das die Reise in derselben Stadt endet, wo sie begonnen wurde.

Wenn di,j die Entfernung zwischen der i-ten und j-ten Stadt bezeichnet, lässt sich dieses Problem in folgender Weise mathematisieren:

Minimiere
n n
∑ ∑ di,jxi,j
i=1 j=1,j≠i

so dass
n
∑ xi,j=1
i=1,j≠i
für j=1,2,,n
n
∑ xi,j=1
j=1,i≠j
für i=1,2,,n
uiuj(n1)xi,jn2 für 2ijn

und xi,j0,1 für i,j=1,2,,n
sowie ui2,3,,n für i=2,3,,n

Die Variable xi,j ist dabei gleich 1 wenn die Rundreise direkt von der i-ten in die j-te Stadt führt und gleich 0 wenn nicht. Die zusätzlichen Variable ui spiegelt wider, an welcher Position der Rundreise sich die i-te Stadt befindet.

Die ersten beiden Gleichungssysteme für die xi,j gewährleisten, das die gesuchte Rundreise in jede Stadt nur einmal hinein- und auch nur einmal hinausführt. Die Ungleichungen, die sich mit ui befassen, stellen sicher, dass die Rundreise zusammenhängend ist. Eine genauere Beschreibung der mathematischen Hintergründe ist hier zu finden:
https://en.wikipedia.org/wiki/Travelling_salesman_problem

Logistikproblem

Eine im Logistik-Bereich immer wieder anzutreffende Variante des Transportproblems, bei der als zusätzlicher Parameter das Ladungsgewicht der transportierten Gütern mitberücksichtigt wird, lautet:

Ein LKW ist mit n Gütern beladen und startet in einer vorgegebenen Stadt. Jedes Gut ist für eine spezifische Stadt i bestimmt und hat ein Ladungsgewicht gi in Kilogramm. Es wird eine Rundreise gesucht, die den Treibstoffverbrauch des LKWs minimiert.

Den Treibstoffverbrauch des unbeladenen LKW pro 100 km beinhaltet die Konstante L. Der zusätzliche Treibstoffverbrauch je Tonne Ladung pro 100 km wird durch die Konstante T widergespiegelt.

Das Problem lässt sich damit nun in ähnlicher Weise wie das "Problem des Handlungsreisenden" formulieren – es kommmen nun allerdings noch Variable yi,j hinzu, die repräsentieren wieviel Kilogramm Ladung von Stadt i nach Stadt j transportiert wird.

Minimiere
n n
∑ ∑ di,jL/100(xi,jyi,jT/1000)
i=1 j=1,j≠i

so dass
n
∑ xi,j=1
i=1,j≠i
für j=1,2,,n
n
∑ xi,j=1
j=1,i≠j
für i=1,2,,n
uiuj(n1)xi,jn2 für 2ijn

n
∑ yj,i
j=1,j≠i
-
n
∑ yi,j
j=1,j≠i
=gifür i=1,2,,n
0yi,jxi,jG für 1ijn
mit G:=
n
∑ gi
i=2

und xi,j0,1 für i,j=1,2,,n
ui2,3,,n für i=2,3,,n yi,j0,1,2,,G für i,j=1,2,,n
In der Literatur bezeichnet man ein Logistik-Problem dieser Art auch als Green Vehicle Routing Problem.

Marktaufteilungs­problem

Marktaufteilungsprobleme ergeben sich, wenn ein Unternehmen Sitze in mehreren Ländern hat und aufgrund unterschiedlich hoher Steuersätze in den betreffenden Ländern, das Vertriebsgeschäft so aufteilen möchte, das in Ländern mit geringerer Steuerlast die Vertriebsmenge entsprechend größer ausfällt.

Ein Unternehmen umfasst zwei Abteilungen, D1 und D2, die mehrere Vertriebspartner mit unterschiedlichen Produkten versorgen. Das Marktaufteilungsproblem besteht darin, jedem Vertriebspartner genau einer Abteilung zuzuordnen (d.h. entweder D1 oder D2), so dass D1 ein p-tel des Marktes für jedes Produkt des Unternehmens kontrolliert und D2 die restlichen 100(1p) Prozent.

Bezeichnet m die Anzahl der Vertriebspartner, n die Anzahl der verschiedenen Produkte und ai,j den Bedarf von Vertriebspartner i am Produkt j, ergibt sich die mathematische Formulierung:

Minimiere
m
∑ si
i=1

so dass
m
∑ ai,jxjsi=bi
j=1
für i=1,2,,m
xj0,1 für j=1,2,,n
und si für i=1,2,,m.

Die rechte Seite

bi=p
m
∑ ai,j
j=1
i=1,2,,m

ergibt sich aus dem gewünschten Market-Split zwischen D1 und D2.

Die Komponenten des (binären) Lösungsvektors x ordnen jeden Vertriebspartner einer der beiden Divisionen zu und enthalten eine 0 für Division D1 und eine 1 für Division D2.

Der Wert von si reflektiert, inwiefern es möglich war, den Market-Split für das i-te Produkt zu realisieren. Ist si=0, dann war der exakte Split möglich.

Wenn ein exakter Split nicht möglich ist, dann garantiert die in der Formulierung enthaltene Minimierungsfunktion, das nach einer Lösung gesucht wird, bei der die Abweichung am geringsten ausfällt.

Mathematische Beschreibung

Eine abstrakte, mathematische Beschreibung, die alle diese gemischt-ganzzahligen, linearen Systeme erfasst, lässt sich in folgender Weise formulieren:

Die linearen Zielfunktionen seien repräsentiert durch eine Zielfunktionsmatrix Ctn und einen Vektor d∞,∞t⋃t. Die Zeilen von C enthalten die Koeffizienten der Zielfunktionen, während die Einträge von d die Zielfunktionswerte definieren.

Des weiteren sei A eine Matrix qn und b ein Vektor q. Sie repräsentieren das lineare Gleichungssystem, das eine Lösung erfüllen muss. Das Ungleichungssystem sei beschrieben durch eine Matrix Hrn und Vektoren v,wr, deren Einträge Intervalle definieren, innerhalb derer die Ungleichungsresultate einer Optimallösung liegen müssen.

Zwei zusätzliche Vektoren l und u enthalten die Intervallgrenzen, innerhalb derer sich die Komponenten eines Vektors xn bewegen müssen, um als Lösung in Frage zu kommen.

Das resultierende allgemeine, lineare Optimierungsproblem (GGL-S) lautet dann:

Finde ein xn mit:
Ax=b, vHxw und lxu
so dass für y:=Cx die Zielfunktionssumme
 
∑ yi
di=
 
∑ yi
di=
 
∑ yidi
di
minimal wird.
Die Teilsumme
 
∑ yidi
di
wird auch als Schlupfabweichung bezeichnet.

Die Lösung eines solchen GGL-Systems lässt sich in polynomialer Rechenzeit bis hin zur Optimalität bestimmen. Fordert man allerdings, dass einzelne Komponenten des Lösungsvektors x ganzzahlig sein sollen, sind exponentiell viele Rechenschritte nötig.

Die Notwendigkeit einer Ganzzahligkeitsbedingung resultiert aus praktischen Überlegungen, etwa weil nur ganze Stückzahlen produziert werden können, oder - im Falle von Entscheidungsprozessen - nur zwei verschiedene Zustände erlaubt sind.

Um derlei Ganzzahligkeitsforderungen abzubilden, sei nun noch ein Vektor p0n gegeben, der für die Komponenten von x, die jeweilige maximale Anzahl von Nachkommastellen enthält.

Man erhält damit als letzte Forderung für die Anzahl der Nachkommastellen f von x:

f:n0n,xf(x)p

Programmpaket

Der Inhalt des Pakets besteht neben dem Hauptprogramm aus diversen Zusatztools und kann auf Rechnern mit Intel-Prozessor(en) unter den Betriebssystemen FreeBSD, Linux, macOS und Windows benutzt werden. Die Programme werden von der Kommandozeile aus bedient und setzen demnach etwas Anwenderwissen bezüglich der Handhabung von Windows-Konsolen bzw. UNIX-Shells voraus. Eine graphische (per Browser bedienbare) Benutzeroberfläche befindet sich gegenwärtig noch im Entwicklungsstadium.

Im Paket befinden sich folgende Programmdateien:
0ptX (Hauptprogramm)
opt2lp, lp2opt (Konverter)
sol (Verifizierer)
Exemplarische Problemdateien im lp bzw. opt-Format befinden sich in entsprechend bezeichneten Unterordnern.

Kurzbeschreibung

Das Hauptprogramm liest Dateien im opt-Format ein, welche die zu lösenden Gleichungssysteme beinhalten, und übersetzt diese Daten zunächst in ein äquivalentes Gitterproblem, das in einer Datei mit der Endung lat zwischengespeichert wird.

Bei mehrfachen Aufrufen des Hauptprogramms mit derselben opt-Datei wird direkt mit der einfacher zu verarbeitenden lat-Datei gestartet, was eine gesteigerte Performance zur Folge hat.

Damit mit dem Konkurrenzprodukt IBM ILOG CPLEX verglichen werden kann, muss dessen lp-Format ins opt-Format überführt werden. Dies wird von lp2opt bewerkstelligt. Die entgegengesetzte Konvertierung übernimmt opt2lp.

Nachdem das Hauptprogramm gestartet wurde, wird eine Datei mit der Endung sol im Verzeichnis der zugehörigen opt bzw. lat-Datei angelegt, in der alle bisher gefundenen Lösungsvektoren und (heuristisch) kürzesten Gittervektoren gespeichert werden.

Die sol-Dateien werden in verschlüsselter Form abgespeichert. Die Entschlüsselung und Übersetzung in entsprechende Lösungen des ursprünglichen Systems, übernimmt das Hilfsprogramm sol, das Sie in Verbindung mit einem Entschlüsselungskontingent nutzen können.
Damit Sie sich auch ohne Entschlüsselungskontingent einen vollumfänglichen Eindruck von verschaffen können, werden die Lösungen zu Problemen, deren Dimension n10 ist, nicht verschlüsselt und können demnach uneingeschränkt begutachtet werden.

Eingabeformate

Das opt-Format

Das opt-Format fungiert als das Standardformat zur Speicherung eines allgemeinen linearen Optimierungs-Problems, wie es im zweiten Kapitel dargestellt wurde.

Die Auszeichnung eines Vektors v erfolgt derart, das die Einträge durch Leerzeichen voneinander getrennt, innerhalb eines eckigen Klammerpaares, angegeben werden:

[v1v2vn]

Analog lässt sich eine Matrix A=(ai,j) darstellen:

[
[a1,1a1,2a1,n]
[a2,1a2,2a2,n]
⋮
[am,1am,2am,n]
]

Die Speicherung der Problemdaten als Datei im opt-Format, geschieht damit in der folgenden Art und Weise:

/*ZielfunktionsSektion:d,C*/

[d1d2dt]
[
[c1,1c1,2c1,n]
[c2,1c2,2c2,n]
⋮
[ct,1ct,2ct,n]
]

/*GleichungsSektion:A,b*/

[
[a1,1a1,2a1,n]
[a2,1a2,2a2,n]
⋮
[aq,1aq,2aq,n]
]
[b1b2bq]

/*UngleichungsSektion:H,v,w*/

[
[h1,1h1,2h1,n]
[h2,1h2,2h2,n]
⋮
[hr,1hr,2hr,n]
]
[v1v2vr]
[w1w2wr]

/*LösungsvektorSektion:p,l,u*/

[p1p2pn]
[l1l2ln]
[u1u2un]

Um die praktische Verwendung des Dateiformats zu demonstrieren, folgen nun einige exemplarische Beispiele:

Beispiel (ohne Zielfunktion)

Finde ein x4 mit (1,0,0,1)Tx(2,3,4,5)T,
so dass: 2x24x3=16, 3x17x4=31,
0x15x421, 2x2x37

Man erhält daraus:

C =
 
, d =
 
,
A =
0 2 4 0
3 0 0 7
, b =
16
31
,
H =
1 0 0 5
0 1 1 0
, v =
0
2
w =
21
7
,
p =
0 0 0 0
T, l =
1 0 0 1
T, u =
2 3 4 5
T
Demgemäß hat die zugehörige Datei „beispiel.opt” den folgenden Inhalt:
[ ]
[
]

[
[ 0 2 4 0 ]
[ 3 0 0 7 ]
]
[ 16 31 ]

[
[ 1 0 0 5 ]
[ 0 1 1 0 ]
]
[ 0 2 ]
[ 21 7 ]

[ 0 0 0 0 ]
[ 1 0 0 1 ]
[ 2 3 4 5 ]

Beispiel (mit einer Zielfunktion)

Finde einx4mit
(1,0,0,1)Tx(2,3,4,5)T,

so dass: 2x24x3=16, 3x17x4=31
0x15x421, 2x2x37

wobei5x1x22x36x4 maximal wird.

Hieraus erhält man:

C =
5 1 2 6
, d =
,
A =
0 2 4 0
3 0 0 7
, b =
16
31
,
H =
1 0 0 5
0 1 1 0
, v =
0
2
, w =
21
7
,
p =
0 0 0 0
T, l =
1 0 0 1
T, r =
2 3 4 5
T
Der Inhalt der zugehörigen opt-Datei lautet damit:
[ inf ]
[
[ 5 1 -2 6 ]
]

[
[ 0 2 4 0 ]
[ 3 0 0 7 ]
]
[ 16 31 ]

[
[ 1 0 0 5 ]
[ 0 1 1 0 ]
]
[ 0 2 ]
[ 21 7 ]

[ 0 0 0 0 ]
[ 1 0 0 1 ]
[ 2 3 4 5 ]

Beispiel (mit zwei Zielfunktionen)

Finde ein x4
mit (1,0,0,1)Tx(2,3,4,5)T,

so dass: 2x24x3=16, 3x17x4=31
0x15x421, 2x2x37

wobei x13x2x3x4 minimal,
und 5x1x22x36x4 maximal wird.

Es ergeben sich die Daten:

C =
1 3 1 1
5 1 2 6
, d =
,
A =
0 2 4 0
3 0 0 7
, b =
16
31
,
H =
1 0 0 5
0 1 1 0
, v =
0
2
, w =
21
7
,
p =
0 0 0 0
T, l =
1 0 0 1
T, u =
2 3 4 5
T
Und der Inhalt der zugehörigen opt-Datei lautet:
[ -inf inf ]
[
[ 1 -3 1 1 ]
[ 5 1 -2 6 ]
]

[
[ 0 2 4 0 ]
[ 3 0 0 7 ]
]
[ 16 31 ]

[
[ 1 0 0 5 ]
[ 0 1 1 0 ]
]
[ 0 2 ]
[ 21 7 ]

[ 0 0 0 0 ]
[ 1 0 0 1 ]
[ 2 3 4 5 ]

Beispiel (mit drei Zielfunktionen)

Finde ein x4
mit(1,0,0,1)Tx(2,3,4,5)T,

so dass: 2x24x3=16, 3x17x4=31
0x15x421, 2x2x37

wobei x13x2x3x4 minimal
5x1x22x36x4 maximal,
und 9x1x22x38x410 minimiert wird.

Dies liefert:

C =
1 3 1 1
5 1 2 6
9 1 2 8
, d =
10
,
A =
0 2 4 0
3 0 0 7
, b =
16
31
,
H =
1 0 0 5
0 1 1 0
, v =
0
2
, w =
21
7
,
p =
0 0 0 0
T, l =
1 0 0 1
T, u =
2 3 4 5
T
Und in Form einer opt-Datei:
[ -inf inf 10 ]
[
[ 1 -3 1 1 ]
[ 5 1 -2 6 ]
[ 9 -1 2 -8 ]
]

[
[ 0 2 4 0 ]
[ 3 0 0 7 ]
]
[ 16 31 ]

[
[ 1 0 0 5 ]
[ 0 1 1 0 ]
]
[ 0 2 ]
[ 21 7 ]

[ 0 0 0 0 ]
[ 1 0 0 1 ]
[ 2 3 4 5 ]

Das nun folgende, letzte Beispiel, wird sämtliche Möglichkeiten des opt-Dateiformats ausschöpfen und insbesondere für einige Komponenten des Lösungsvektors keine Ganzzahligkeit mehr fordern, es muss dann allerdings angegeben werden, wieviele Nachkommastellen maximal erlaubt sind.

Beispiel (mit gemischt-ganzzahligen Lösungen)

Finde ein x
mit (1,0,0,1)Tx(2,3,4,5)T,

und höchstens 4 bzw. 1 Nachkommastelle(n)
in der zweiten bzw. dritten Komponente,

so dass: 2x24x3=16, 3x17x4=31
0x15x421, 2x2x37

wobei x13x2x3x4 minimal,
5x1x22x36x4 maximal
und 9x1x22x38x410 minimiert wird.
[ -inf inf 10 ]
[
[ 1 -3 1 1 ]
[ 5 1 -2 6 ]
[ 9 -1 2 -8 ]
]

[
[ 0 2 4 0 ]
[ 3 0 0 7 ]
]
[ 16 31 ]

[
[ 1 0 0 5 ]
[ 0 1 1 0 ]
]
[ 0 2 ]
[ 21 7 ]

[ 0 4 1 0 ]
[ 1 0 0 1 ]
[ 2 3 4 5 ]

lp opt

Um ein lineares Problem im CPLEX lp-Format einzulesen, wird das Programm lp2opt benötigt, mit dessen Hilfe man das Problem ins opt-Format umwandeln kann.

Die einzulesende Datei „beispiel.lp” besitze den folgenden Inhalt:
Minimize
 obj: 2x1 - 4x2 + 5x3

Subject To
 1x1 + 5x4 <= 21
 1x1 + 5x4 >= 0
 2x2 + 4x3 = 16
 3x1 + 7x4 = 31

Bounds
 0 <= x1 <= 2
 0 <= x2 <= 3
 0 <= x3 <= 4
 0 <= x4 <= 5

General
 x1 x2 x3 x4
End
Durch den folgenden Kommandoaufruf wird die Datei ins opt-Format konvertiert und unter dem Namen „beispiel.opt” abgespeichert:
# ./lp2opt beispiel.lp
Die resutierende Datei „beispiel.opt” besitzt den Inhalt:
[ -inf ]
[
[ 2 -4 5 0 ]
]

[
[ 0 2 4 0 ]
[ 3 0 0 7 ]
]
[ 16 31 ]

[
[ 1 0 0 5 ]
]
[ 0 ]
[ 21 ]

[ 0 0 0 0 ]
[ 0 0 0 0 ]
[ 2 3 4 5 ]
Falls der entgegengesetzte Weg gewünscht ist, d.h. eine Konvertierung vom opt-Format ins CPLEX lp-Format ist das Hilfsprogramm opt2lp zu verwenden.
Der Konverter lp2opt wird in den meisten Fällen gute Dienste leisten. Allerdings versagt er, wenn nicht sämtliche Variable innerhalb der lp-Datei mit x bezeichnet sind. Demnach sollten Sie dies sicherstellen, wenn Sie den Konverter nutzen möchten. Es ist allerdings empfehlenswert, direkt das opt-Format zu verwenden, da dieses vielfältigere Möglichkeiten für die Formulierung von Problemstellungen bietet.

Programmaufruf

Verwendungsweise

Sobald das eigentliche Problem in Form einer opt-Datei vorliegt, kann es durch einen Aufruf von gelöst werden. Hierzu werden einige exemplarische Verwendungsweisen aufgeführt.

Bei der ersten Variante wird das Programm mit Default-Optionen gestartet und durch die Angabe von --verb=2 dazu veranlasst, möglichst viele Statusmeldungen auf der Konsole auszugeben:

# ./0ptX --verb=2 beispiel.opt

Die nächste Kommandozeile erhöht die Enumerations-Blockweite auf 25 und aktiviert ein Skalierungsverfahren. Sobald 4 unterschiedliche Lösungen vorliegen, terminiert das Programm:

# ./0ptX --beta=25 --scale=1 --sol=4 beispiel.opt

Mit den Parametern snorm bzw. tnorm kann eingestellt werden, inwieweit die Vorgaben des Zielfunktionsystems erfüllt sein müssen. Die damit zutage geförderten Lösungen genügen dann neben dem Gleichungs- und Ungleichungsanteil des linearen Systems auch den gewünschten Zielfunktionsvorgaben.

# ./0ptX --tnorm=13 --sol=1 beispiel.opt

Bei dieser Kommandozeile wird der Programmlauf abgebrochen, sobald eine Lösung x gefunden wird, für die gilt:

 
∑ yi
di=
 
∑ yi
di=
 
∑ yidi
di
13

Wenn die Abbruchbedingung nur Zielfunktionen mit Zielfunktionswerten di berücksichtigen soll, verwenden Sie stattdessen den Parameter snorm. Es wird dann lediglich der Wert der dritten Summe herangezogen.

Wenn die Zielfunktionen des Optimierungsproblems ausschließlich endliche Zielvorgabewerte haben, unterscheiden sich die Parameter snorm und tnorm nicht in ihrer Wirkungsweise - die ersten beiden Summen sind dann nämlich gleich 0.

Die Nützlichkeit von snorm wird an folgendem Beispiel deutlich werden: Es soll das lineare Gleichungssystem

1 2 3
4 5 6
7 8 9
x =
10
20
30


mit
0 0 0
T x
40 50 60
T
und x3

gelöst werden.

Die resultierende opt-Datei besitzt also den Inhalt:

[ ]
[
]

[
[ 1 2 3 ]
[ 4 5 6 ]
[ 7 8 9 ]
]
[ 10 20 30 ]

[
]
[ ]
[ ]

[ 0 0 0 ]
[ 0 0 0 ]
[ 40 50 60 ]

Wenn Sie jetzt mit keine Lösung finden, so hat dies einen einfachen Grund - das System ist unlösbar. Um dennoch zu einem befriedigenden Ergebnis zu gelangen, könnte man an einer Lösung interessiert sein, die das Gleichungssystem „fast” erfüllt.

Um dies zu bewerkstelligen, muss das Gleichungssystem als ein System von Zielfunktionen mit Zielwertvorgabe formuliert werden:

Minimiere
1 2 3
Tx - 10
4 5 6
Tx - 20
7 8 9
Tx - 30

wobei
0 0 0
T x
40 50 60
T
und x3
Die entsprechende opt-Datei sieht demnach wie folgt aus:
[ 10 20 30 ]
[
[ 1 2 3 ]
[ 4 5 6 ]
[ 7 8 9 ]
]

[
]
[ ]

[
]
[ ]
[ ]

[ 0 0 0 ]
[ 0 0 0 ]
[ 40 50 60 ]

Der nächste Aufruf soll nun nach einer Lösung, mit einer summierten Zielwert-Abweichung 4 suchen. Demnach wird also abgebrochen, sobald eine Lösung x gefunden wird, für die gilt:

 
∑ yidi
di
4
Eine derartige „Fast“-Lösung wird auch als Lösung mit Schlupf bezeichnet.
Der folgende Aufruf, liefert dann als Ausgabe:
# ./0ptX --snorm=4 opt/showcases/simple.opt
<< 0ptX v2.1.3 +++ (c) BirdWorX Solutions 2023 +++ PID: 3648 >> [ Registered standard license for: xxx@yyy.zz ] Got signal: Terminated: 15 ************************** Terminated ************************** T(bestTarget) = 4, S(bestTarget) = 4 -- { 0 sec(s) } { The first solution/s was/were found after: 0 sec(s) } The following file contains the results: opt/showcases/simple.sol Total iterations: 11 Total running time: 0 sec(s) -- Program end

Die gefundenen Lösungen (mit Schlupf) können mit dem Hilfsprogramm sol entschlüsselt und angezeigt werden:

# ./sol opt/showcases/simple.sol
x = [ 2 0 2 ] Target values: [ 8→10 20→20 32→30 ] Target Norm: 4 Slack Norm: 4 Found after: 1 sec(s) --- x = [ 1 2 1 ] Target values: [ 8→10 20→20 32→30 ] Target Norm: 4 Slack Norm: 4 Found after: 1 sec(s) --- x = [ 0 4 0 ] Target values: [ 8→10 20→20 32→30 ] Target Norm: 4 Slack Norm: 4 Found after: 3 sec(s)

Kommando­zeilen­parameter

In diesem Abschnitt erhalten Sie einen Überblick über die Kommandozeilenparameter von . Sie können damit einerseits das Abbruchverhalten steuern, aber auch verschiedene Algorithmen (de-)aktivieren, um die Lösungsfindung zu begünstigen.

Nachfolgend werden Name, Typ, mögliche Werte, Defaultwert und die Wirkungsweise aufgelistet:

help ganzzahlig 0, 1 0
Listet sämtliche Kommamdozeilenparameter auf und beschreibt deren Wirkungsweise.
verb ganzzahlig 0, 1, 2 0
Normalerweise werden zur Laufzeit keine Statusmeldungen ausgegeben. Um nach jedem Hauptschleifendurchlauf statistische Informationen zu erhalten, ist die Einstellung 1 zu wählen. Bevorzugt man Informationen, die auch den Status der unterschiedlichen Programmfunktionen reflektieren, ist der Wert gleich 2 zu setzen.

Zur Begegnung von Programmabbrüchen wegen Genauigkeitsproblemen, dient die nächste Einstellmöglichkeit:

consistency ganzzahlig 0, 1 0
Hiermit wird an verschiedenen Stellen innerhalb des Programms überprüft, ob das aktuelle Gitter mit der Transformation des ursprünglichen Gitters übereinstimmt. Sollte es zu Rechen-, bzw. Präzisionsfehler kommen, empfielt es sich diesen Parameter gleich 1 zu setzen. Damit werden Inkonsistenzen im Berechnungsverlauf frühzeitig erkannt und eliminiert. Da dies allerdings auch Einfluss auf die Laufzeit des Programms hat, sind diese Checks defaultmässig deaktiviert.

Das Kernstück zur Ermittlung kurzer Gittervektoren ist ein Abzählverfahren, das innerhalb von Blöcken von Basivektoren operiert, um darin kürzeste Gittervektoren aufzuspüren. Die nachfolgenden Parameter ermöglichen eine Steuerung dieser Abzählmethodik.

eenum ganzzahlig 0, 1 1
Die Verwendung eines Enumerations-Verfahrens zur Auffindung kurzer Gittervektoren ist per Default aktiv. Diesen Parameter sollten Sie im Normalfall nicht deaktivieren. Wenn Sie die Laufzeit des Enumerationsschritts beeinflussen möchten, sollten Sie stattdessen mit den nächsten vier Parametern experimentieren.
beta ganzzahlig ≥ 2 20
Damit lässt sich die im Enumerationsverfahren verwendete Blockgröße festlegen.
eprune ganzzahlig 1, 2, 3 3
Wenn es wahrscheinlich ist, das im weiteren Verlauf der Enumeration keine Verbesserung mehr eintritt, lässt sich mit diesem Parameter festlegen, wie stark Enumerationsbäume abgeschnitten werden. Je größer dieser Wert, desto mehr bzw. öfters wird abgeschnitten.
btime ganzzahlig ≥ 0 0
Diese Einflußgröße entscheidet, wie viele Sekunden die Enumeration eines Blocks maximal dauern darf. Ist das Sekundenlimit erreicht, wird das Enumerations-Verfahren beendet und eine abschließende LLL-Reduktion durchgeführt. Das Programm wird allerdings nicht abgebrochen, lediglich der Laufzeitanteil der Enumeration wird geregelt.
deep ganzzahlig ≥ 0 0
Ein Wert 0 bedeutet, dass die LLL-Variante mit Tiefeneinfügungen verwendet wird. Der Wert von deep gibt dabei an, auf wieviele Vektoren der Lovász-Schritt ausgedehnt wird.

Ergänzend zum Abzählverfahren, das implizit nur nach kurzen Gittervektoren suchen kann, kommen auch heuristische Prozeduren zum Einsatz, mit denen sich die eigentlich geforderten Anforderungen an eine Lösung genauer abbilden lassen.

collectLimit ganzzahlig ≥ 0 1000
Im Programmverlauf werden heuristisch gut bewertete Gittervektoren gesammelt. Die Größe dieser Sammlung lässt sich mit diesem Parameter festlegen. Die nachfolgenden heuristischen Methoden bedienen sich im Rahmen ihrer Auswahlprozesse dann aus dieser Sammlung.
pair ganzzahlig 0, 1 1
Aktiviert eine Routine, die Paare heuristisch gut bewerteter Gittervektoren miteinander kombiniert und prüft, ob der daraus resultierende Vektor eine bessere Bewertung hat, als einer der Ausgangsvektoren. Ist dies der Fall, wird das Resultat in die Sammlung der heuristisch gut bewerteten Gittervektoren aufgenommen. Paarweise Reduktionen werden defaultmässig immer durchgeführt und können mit dem Wert 0 deaktiviert werden.
pairLimit ganzzahlig ≥ 0 10
Damit lässt sich festlegen, wieviele Vektoren bei jedem Aufruf der paarweisen Reduktion maximal für die Rekombination aus der Sammlung mit heuristisch gut bewerteten Gittervektoren ausgewählt werden.
sieve ganzzahlig 0, 1 0
Zur Auffindung heuristisch gut bewerter Gittervektoren wird die Sammlung der heuristisch gut bewerteten Gittervektoren einem Sieb-Verfahren unterzogen. Das Resultat wird dann mit der Sammlung vereint und diese danach wieder auf die maximal erlaubte Größe reduziert. Mit dem Wert 1 können Sie dieses Verfahren aktivieren.

Die nächsten beiden Parameter regeln einen Mechanismus zur zufälligen Erzeugung von Gittervektoren.

sample ganzzahlig 0, 1 0
Aktiviert ein Sampling-Verfahren, das zufällig verteilte Gittervektoren erzeugt und gegebenfalls in die Sammlung der heuristisch gut bewerteten Gittervektoren aufnimmt. Defaultmässig ist das Verfahren deaktiviert.
sampleLimit ganzzahlig ≥ 0 1000
Die Anzahl der Vektoren, die pro Sampling - Aufruf maximal erzeugt werden.

Die beiden folgenden Parameter begünstigen das Auffinden von zulässigen Gittervektoren, allerdings hat dies aber auch zur Folge, das sich die Wahrscheinlichkeit verringert, das sich die bisherige Zielfunktionssumme verbessert. Die Effektivität der paarweisen Reduktion und des heuristischen Siebverfahrens, kann damit aber wiederum gesteigert werden. Per Default sind die Parameter nicht gesetzt.

scale ganzzahlig 0, 1 0
Ist dieser Parameter gesetzt, werden diejenigen Komponenten von Gittervektoren skaliert, die sich am stärksten auf die Zulässigkeitsbedingung auswirken.
translate ganzzahlig 0, 1 0
Ist dieser Parameter gesetzt, wird das gesamte Gitter verschoben und zwar derart, das bevorzugt, diejenigen Komponenten von Gittervektoren reduziert werden, die die Zulässigkeitsbedingung am stärksten verletzten.

In der Praxis zeigt sich, das sich die bisher vorgestellten Routinen nach einer gewissen Zeit "festfahren" können und aus lokalen Minima nicht mehr herausfinden. Es ist deshalb ab und an notwendig für etwas "Abwechslung" zu sorgen. Die nachfolgenden Parameter sind per Default aktiv, können aber mit dem Wert 0 deaktiviert werden.

reinsert ganzzahlig 0, 1 1
Diese Routine fügt nach jeder Iteration die bisher gefundenen besten Gittervektoren in die Gitterbasis ein.
variate ganzzahlig 0, 1 1
Diese Routine wird aktiv, wenn sich nach einer gewissen Anzahl von Iterationen kein Fortschritt bei der Zielfunktionssummen-Minimierung erzielen lässt. Es werden sodann die Basisvektoren zunächst der Größe nach aufsteigend anordnet und danach zufällig durchmischt. Die Anzahl der Mischvorgänge richtet sich dabei nach der Anzahl der erfolglosen Iterationen. Je mehr erfolglose Iterationen, desto mehr Mischvorgänge.

Die nächsten drei Parameter sind relevant für das Abbruchverhalten von .

rtime ganzzahlig ≥ 0 0
Hiermit wird festgelegt, nach wie vielen Sekunden Laufzeit das Programm beendet wird. Standardmäßig ist der Parameter mit 0 initialisiert, was unendlich langer Laufzeit entspricht.
iters ganzzahlig ≥ 0 0
Hiermit lässt sich spezifizieren nach wievielen Iterationen das Programm beendet wird. Defaultmässig ist dieses Limit nicht gesetzt.
sol ganzzahlig ≥ 0 1
Bevorzugt man einen Programmabbruch aufgrund der Anzahl der gefundenen Lösungen, dann ist dieses Kriterium zu verwenden. Defaultmäßig terminiert das Programm, sobald eine Lösung gefunden wurde. Wird kein Limit gewünscht, ist der Wert gleich 0 zu setzen.

Die Qualität von aufgefunden Lösungen lässt sich mit den nächsten zwei Parameter festlegen.

snorm reellwertig ≥ 0 -1
Welche Schlupfabweichung darf ein zulässiger Gittervektor maximal haben, um als Lösung gelistet zu werden.
tnorm reellwertig ≥ 0 -∞
Welche Zielfunktionssumme darf ein zulässiger Gittervektor maximal haben, um als Lösung gelistet zu werden.

Der letzte Parameter ist für Benchmarks und Laufzeitvergleiche gedacht:

bench ganzzahlig 0, 1 0
Wenn dieser Parameter gesetzt wird, dann wird auf das Einlesen einer eventuell existierenden lat bzw. sol-Datei verzichtet. Die Resultate eignen sich damit um die Wirksamkeit unterschiedlicher Parametersätze vergleichen zu können.

Den Abschluss bildet eine Liste mit Parameterkombination, die sich in der Praxis als durchschlagskräftig erwiesen haben.

  • --eenum=1 --sieve=0 --sample=0 --scale=0 --translate=0 (das Default-Setting)
  • --eenum=1 --sieve=1 --sample=0 --scale=1 --translate=0
  • --eenum=0 --sieve=0 --sample=1 --scale=1 --translate=0
  • --eenum=0 --sieve=0 --sample=1 --scale=0 --translate=1
  • --eenum=1 --sieve=1 --sample=0 --scale=1 --translate=1
  • --eenum=1 --sieve=0 --sample=0 --scale=1 --translate=1
Gegenwärtig befindet sich eine KI-unterstützte Parameter-Empfehlung in Entwicklung, die als Eingabe eine opt-Datei entgegennimmt und für diese die vielversprechendste Parameterkombination zurückgibt.

Videos

Datenschutz Kontakt Impressum