Ganzzahligkeit 1 Ganzzahligkeit in LP-Modellen Problematik * Modellierung * Lösungswege

Ganzzahligkeit 1

Ganzzahligkeit in LP-Modellen

Problematik * Modellierung * Lösungswege

Ganzzahligkeit 2

Agenda

1. Problematik

2. Modelle mit Ganzzahligkeitsbedingung21. Direkte Modelle

22. Codierte Modelle

23. Transformierte Modelle

3. Lösungswege31. Schnittebenen

32. Branch and Bound

Ganzzahligkeit 3

1. Problematik der Ganzzahligkeit

Als Lösungen kommen nur die ganzzahligen Punkte in Betracht:

Ganzzahligkeit 4

Schwierigkeiten

Lösungsraum ist nicht konvex. Lösungen liegen i.d.R. nicht auf dem Rand. Gerundete Lösungen sind vom Optimum i.d.R. weit entfernt. Dieses gilt besonders für sog. 0-1-Probleme.

Ganzzahligkeit 5

Klassifizierung von IP-Problemen

Klassifizierung von Integer Problemen:

Wertebereich der ganzzahligen Variablen xj 0 ganzzahlig xj = 0 oder xj = 1

Ganz- zahligkeit für

alleVariablen xj jN

ganzzahliges Prog. IP 'all-integer'

bivalentes Prog. oder (0,1)-LP BIP 'zero/one-integer'

Ganz- zahligkeit für

einen Teil der Variablen xj jIN

gemischt-ganzz. Prog. MIP 'mixed integer'

gemischt bival. Prog. MBIP 'mixed-zero/one-integer'

Ganzzahligkeit 6

2.1 Direkte Modelle

1

1

Min

mit

u.d.N. für A,B,C,D

0

n

j jj

n

ij j ij

j

z

z r x

a x b i

x

ganzzahlig

Durch Hinzufügen der Anweisung "ganzzahlig" für einzelne oder alle Variablen (z.B. beim Verschnittproblem):

Man bezeichnet das entsprechende LP-Probleme ohne die Ganzzahlig-keitsbedingung als relaxiertes Problem.

Ganzzahligkeit 7

2.2 Codierte Modelle

Wenn die Entscheidungsvariablen einen qualitativen Aspekt repräsentieren, für den es genau definierte, endliche Zustände gibt, erhält man codierte Modelle.

Besonders häufig: Es gibt nur zwei definierte Zustände, die man durch sog. Binärvariablen abbilden kann.

Beispiele hierfür: Kapitalbudgetierung (Investition: ja / nein) Maschinenbelegung (Auftrag auf Anlage: ja/nein) Stundenplanerstellung (Zuordnung: ja/nein) Knapsackproblem (Gut: ja/nein) Travelling Salesman (Strecke: ja/nein) Lieferplan (Lieferung: ja/nein) Standort (Ort: ja/nein) Graphenprobleme (Covering, Matching, Colouring)

Ganzzahligkeit 8

2.3 Tranformierte Modelle

Eine Binärvariable wird als Indikator-variable benutzt, die einen bestimmten Zustand in Abhängigkeit des Wertes einer anderen Variable eine Beschränkung induziert.

Typisch sind dabei "Wenn … dann …"-Bedingungen, also logische Abhängigkeiten.

Ganzzahligkeit 9

2.3.1 Diskretwertmodelle

Eine Aktivität (Variable) soll nur einen von mehreren, vorher bestimmte Werte annehmen dürfen:

1 2W= , ,..., 2,5,7,9j nx w w w

1 1 2 2

1 2

...

... 1

0,1

j n n

n

j

x w y w y w y

y y y

y

Jedem Wert ordnet man eine Indikatorvaiable zu:

Ganzzahligkeit 10

2.3.2 Batch Size Probleme

Einfache Dichotomie

Eine Variable soll entweder Null sein oder eine bestimmte Untergrenze nicht unterschreiten: Ein Produkt j soll entweder nicht oder – wenn schon – dann mindestens in der Menge lj gefertigt werden.Es sei uj eine künstliche oder natürliche Obergrenze für die Variable xj:

0

0

0,1

0

j j j

j j j

j

j

x l y

x u y

y

x

Ganzzahligkeit 11

2.3.3 Disjunkte Variablen

Von n Variablen (die bestimmten Aktivitäten zugeordnet sind), soll entweder

(1) eine einen Wert größer Null haben oder

(2) mindestens p einen Wert größer Null haben oder

(3) höchstens q einen Wert größer Null haben.

Zu jeder Aktivitätsvariablen xj mit der Obergrenze uj wird ein Indikatorvariable yj gewählt:

0

1. 1

2.

3.

j j j

jj

jj

jj

x u y

y

y p

y q

für alle 1,2,...,j n

0,1 für alle 1,2,...,jy j n

Ganzzahligkeit 12

2.3.4 Disjunkte Nebenbedingungen

Aus einer Menge von Nebenbedingungen fi(x1,x2,…,xn) bi seien aktiv:

1. genau eine ( m-1 sind relaxiert)

2. mindestens p ( höchstens m-p sind relaxiert)

3. höchstens q ( mindestens m-q sind relaxiert).

Es sei M eine große Zahl (M>>bi):

1. 1

2.

3.

ii

ii

ii

y m

y m p

y m q

1 2

0,1

( , ,..., ) M für alle 1,2,...,i

i n i i

y

f x x x b y i m

Ganzzahligkeit 13

2.3.5 Nebenbedingung mit alternativen RS

Für eine Nebenbedingung f(x1,x2,…,xn)=b soll alternativ eine RS b{b1 oder b2 oder… } gelten:

0,1iy

1 2( , ...)

1

k kk

kk

f x x b y

y

j j k kj k

z c x d y

Falls mit einer schrittweisen Kapazitätserweiterung b1<b2<… Kosten d1<d2<… verbunden sind, berücksichtigt man ín der Zielfunktion:

Ganzzahligkeit 14

2.3.6 Fixed Charge Problem

Klassisches Fixkostenproblem:

0 für 0( )

für 0j

jj j j j

xk x

f c x x

Für jede Variable xj ist eine Indikatorvariable yj zu definieren:

Min

mit

M 0,1

j j j jj j

j j j

z

z c x f y

x y y

Ganzzahligkeit 15

2.3.7 Vereinigung konvexer Gebiete (1)

Die Vereinigung konvexer Gebiete ist i.d.R. nicht konvex:

TG1 TG2

3

x2

1x

{or3ab304.pre}

1

2

1 2 3 4 5

TG3

Ganzzahligkeit 16


Jedes Gebiet ist für sich durch lineare Ungleichungen definiert:

2

1 2

1 2

TG1: 3 (1.1)

4 (1.2)

, 0 (1.3)

x

x x

x x

1 2

1 2

1 2

TG2: 0 (2.1)

3 8 (2.2)

, 0 (2.3)

x x

x x

x x

1

2

1 2

TG3: 5 (3.1)

1 (3.2)

, 0 (3.3)

x

x

x x

Ganzzahligkeit 17

Formulierung logischer Verknüpfungen

Xi eine Aussage, z.B. Xi = wahr, wenn Produkt i hergestellt wird, d.h. xi > 0

yi = 1, wenn Xi = wahr; yi = 0, wenn Xi = falsch

Verknüpfung Bezeichnung Formulierung

Negation Xi yi = 0 (alternativ: 1 yi = 1)

Konjunktion Xi Xj yi = 1 UND yj = 1 yi + yj = 2

Disjunktion Xi Xj yi = 1 ODER yj = 1 yi + yj 1

Implikation Xi Xj yi yj 0

Äquivalenz Xi Xj yi yj = 0

Ganzzahligkeit 18

Logische Impliklationen (1)

Voraussetzung:

( 0 sei natürliche Untergrenze)

m x

m

Formulierung: 0x m y

Implikation: 1 0y x m

Ganzzahligkeit 19


Implikation: 0 1x y

Voraussetzung: 0

( natürliche Obergrenze = große Zahl)

x M

M

Formulierung: 0x M y

Ganzzahligkeit 20


Voraussetzung:

( sei Obergrenze des Funktionals)

j jj

a x b M

M

j

Formulierung: j ja x M y b M

Implikation: 1 j jj

y a x b

Ganzzahligkeit 21


Voraussetzung:

( 0 sei Untergrenze des Funktionals)

j jj

m a x b

m

j

Formulierung: ( )j ja x m y b

Implikation: 1j jj

a x b y

Ganzzahligkeit 22


Voraussetzung:

( sei Untergrenze des Funktionals)

j jj

m a x b

m

j

Formulierung: j ja x m y b m

Implikation: 1 j jj

y a x b

Ganzzahligkeit 23


Voraussetzung:

( sei Obergrenze des Funktionals)

j jj

a x b M

M

j

Formulierung: ( )j ja x M y b

Implikation: 1j jj

a x b y

Ganzzahligkeit 24


Jedes Gebiet ist für sich durch lineare Ungleichungen definiert:

1 2 1 2

2 1 2 1 2

3 1 2

TG1: y 1 ( 3) ( 4)

TG2: y 1 ( 0) (3 8)

TG3: y 1 ( 5) ( 1)

x x x

x x x x

x x

1 2Für alle Gebiete gilt gemeinsam: 5 und 4x x

Ganzzahligkeit 25

Anwendung der logischen Implikation Typ (3)

1 1 1

1 2 1 2

Durch Abschätzung erhält man Obergrenzen M

zu den Nebenbedingungen:

3 3 0 : 3 4 3 1 M 1

4 0 : 4 4 5 4 5 M 5

x x x

x x x x

1

2 1

1 2 1

Die Indikatorvariable 1 aktiviert damit

die obigen Nebenbedingungen genau dann, wenn:

1 3 1

5 4 5

y

x y

x x y

Ganzzahligkeit 26


1 2 1 2 1 2

1 2 1 2 1 2

Analog erhält man Obergrenzen M zu den Neben-

bedingungen des TG2:

0 0; 4 : 4 M 4

3 8 5; 0 : 3 8 15 0 8 5 M 7

x x x x x x

x x x x x x

2

1 2 2

1 2 2

Die Indikatorvariable 1 aktiviert damit

die obigen Nebenbedingungen genau dann, wenn:

4 4

3 7 15

y

x x y

x x y

Ganzzahligkeit 27


2 1

1 2 1

1 2 2

1 2 2

2 3

1

Die äquivalente Formulierung erhält man für TG3.

Zusammen ergibt sich:

4 (TG1)

5 9

4 4 (TG2)

3 7 15

3 4 (TG3)

5

x y

x x y

x x y

x x y

x y

x

1, 2, 3 1 2 3

Da die Lösung in mindestens einem Teilgebiet

liegen muss, aber in allen liegen kann, gilt:

0,1 : 1y y y y y y

Documents

Ganzzahligkeit 1 Ganzzahligkeit in LP-Modellen Problematik * Modellierung * Lösungswege