Operationeel onderzoek
Geheeltallige programmering
1. Geheeltallige variabelen
Hoe formuleren?
1. Beslissingsvariabelen
2. Doelfunctie
3. Beperkingen
→ We werken in Lingo, hier wordt standaard uitgegaan van een niet-negativiteitsvoorwaarde. Je moet
dit dus enkel vermelden als je dit tegen wilt gaan.
Zijn fractionele waardes (bv. x = 3,78) een probleem?
= deelbaarheidsassumptie
o Hangt af van de context, van de situatie
o In het geval van de tafels, kunnen we geen halve tafels maken.
o Maar als we bvb. werken met een rolling horizon (vandaag beginnen aan een stuk en
morgen afmaken) of werken met duizendtallen (3,78 wordt 3780), dan kan dit natuurlijk
wel
Indien de deelbaarheidsassumptie van LP niet opgaat dan moet de restrictie x1, x2 ∈ {0,1,2, … }
uitdrukkelijk meegenomen worden. We spreken dan van geheeltallige programmering (= integer
programmering IP) , soms ook ILP (linear).
- We werken ook met MILP = mixed-integer LP → sommige variabelen zijn geheeltallig, anderen
niet
- We werken ook met ZOIP = zero-one LP of BIP = binary IP → variabelen zijn 0 of 1
Als we de geheeltalligheidseis van een IP weglaten dan krijgen we een LP-relaxatie van dit IP.
Grafische analyse:
- Werkt alleen bij 2 variabelen
- Creatie van een veelhoek door beperkingen (= polyheder,
polyhedron)
- Normaalvector van de doelfunctie is het punt van de waarden
voor de variabelen in de doelfunctie (vb. (8,5))
Stelling: als er een optimale oplossing bestaat, dan bestaat er
minstens één extreem punt van het polyhedron dat optimaal is.
Als we een eindig bereik hebben (gesloten veelhoek) kunnen
we elk hoekpunt overlopen en zo de optimale oplossing eruit halen
Om onze ongelijkheden te kunnen verwijderen uit onze vorm, moeten we variabelen toevoegen (=
verschilvariabelen). Zo bekomen we een standaardvorm.
,Bij stelsels in kanonieke vorm onderscheiden we:
- Basisvariabelen (BV) = afhankelijke, endogene, gebonden variabelen
- Niet-basisvariabelen (NBV) = onafhankelijke, exogene, vrije variabelen
→ Via ero’s (elementaire rij-operaties) kunnen we niet-basisvariabelen manipuleren naar
basisvariabelen
Basisoplossing is het resultaat van het stelsel bij het nemen van de niet-basisvariabelen gelijk
aan 0.
Een toelaatbare basisoplossing (=tbo) heeft alle variabelen ≥ 0
Stelling: elk extreem punt van de LP-oplossingsruimte is een tbo, en omgekeerd.
→ In plaats van alles te enumereren gaat het simplex algoritme verstandiger te werk en wordt LP als
redelijk ‘gemakkelijk beschouwd (later meer)
De oplossingsruimte van een IP is niet convex: het concept van een ‘extreem punt’ is hier zelfs niet
gedefinieerd… kunnen we LP gebruiken om het IP op te lossen
Wat is convex? Als je een lijnstuk trekt tussen 2 punten van het gebied, ligt het lijnstuk ook in
het gebied.
o Afronden gaat niet altijd het optimum leveren (zelfs een toelaatbare oplossing vinden is
soms al moeilijk)
o Wat indien de oplossing van de LP-relaxatie geheeltallig is?
▪ De oplossingsruimte van een IP is een deelverzameling van de oplossingsruimte
van de LP-relaxatie. Bijgevolg is:
𝑚𝑖𝑛 − 𝑝𝑟𝑜𝑏𝑙𝑒𝑒𝑚: 𝑍 ∗ > 𝑍 𝐿𝑃 𝑚𝑎𝑥 − 𝑝𝑟𝑜𝑏𝑙𝑒𝑒𝑚: 𝑍 𝐿𝑃 > 𝑍 ∗
▪ We vinden dus een beneden (lowerbound) - en respectievelijk een bovengrens
(upperbound)
o Eender welk toelaatbaar punt heeft x1≤ 3 ofwel x1 ≥ 4. Partitioneren van de zoekruimte:
branching (vertakken)
▪ Zo kunnen we het grote probleem opdelen in
stukken, zonder geheeltallen te verliezen
▪ Opdelen in deelverzamelingen zodat de unie
alles omvat en de doorsnede leeg is
,Brand-and-bound (= B&B, vertak-en-begrens)
→ Zoekvolgorde in eerste instantie arbitrair, bvb.
1 (LP-relaxatie) → 2 → 4 (infeasible) → 5 → 6 (incumbent) → 5 (fathomed) → backtracking → 3
(fathomed)
GUB = Global upper bound, LUB = local upper bound
We kunnen ook werken met een tolerantie. Wanneer we deze instellen op 0% zijn we enkel tevreden
met de best toelaatbare oplossing, maar dit kan natuurlijk sterk oplopen in rekentijd. Wanneer we
deze anders bvb. definiëren op 5%, dan mag deze hier lichtelijk van afwijken, wat sterke invloed kan
hebben op rekentijd.
Werkwijze LP-gebaseerde B&B:
- Los LP-relaxatie op, indien geheeltallig stop
- Opsplitsen (branching) van de oplossingsruimte van de LP-relaxatie in deelverzamelingen door
beperkingen toe te voegen op de waarden van de geheeltallige, beslissingsvariabelen
- Los een LP op over één deelverzameling
- Indien geheeltallig, bewaar de beste gevonden geheeltallige oplossing (= kandidaat oplossing,
incumbent, momenteel beste GLB) en backtrack
o Anders moet je verder vertakken, behalve indien een LP-relaxatie (lokale bovengrens)
een slechtere (of dezelfde) doelfunctiewaarde heeft dan de huidige incumbent, dan
moet je niet verder opsplitsen en kan je deze tak elimineren in de zoekboom (=
fathomed = afgewerkt) want de doelfunctiewaarde zal lager in de boom nooit
verbeteren.
De beste keuze voor zowel de vertakkingsbeslissing als de keuze van volgorde van oplossen van sub-
problemen is probleem-afhankelijk.
Wanneer X1 en wanneer X2? → welke ligt het dichtste bij 0,5
Eerst linkse tak of eerst rechtse tak? → welke waarde ligt het dichtst bij de variabele (vb. 3,75
ligt dichter bij 4 dus daar beginnen)
, 2. Knapzak
Voorbeeld: capital budgeting
→ Zie ook voorbeeld op papier in video
Voorgaand probleem wordt in de literatuur meestal 0/1 knapzak genoemd. De variant geheeltallige
knapzak werkt niet met binaire variabelen maar wel x1, x2 ∈ {0,1,2, … }
Conclusie van het voorgaande:
- Voordelen van geheeltalligheidseis: realistischer en flexibeler
- Nadelen: moeilijker modelleren, veel moeilijker op te lossen
- Vandaar: gebruik integraliteits-eis spaarzaam
Voor bovenstaande knapzak formuleringen, hoe zou je de volgende logische beperkingen modelleren?
1. We kunnen slechts twee investeringen doen: x1 + x2 + x3 + x4 <= 2
2. Indien investering 2 wordt gedaan, moet 4 ook worden gedaan: x4 >= x2
3. Als investering 1 wordt gedaan, dan kan investering 3 niet worden uitgevoerd: x3 <= 1-x1
4. Idem 3
5. Als investering 1 en investering 2 worden gedaan, dan kan investering 3 niet worden gedaan: x3
<= 2 – (x1+x2)
3. Set covering/packaging/partitioning
3.1. Locatie van brandweerstations
Heuristiek: 5 of 4 of …?
Optimum: 3 (4, 6, 15)
→ hoe weten we met zekerheid wat de optimale doelfunctiewaarde is?
Formulering:
1. Beslissingsvariabelen: 𝑥 𝑖 ∈ {0,1} 𝑣𝑜𝑜𝑟 𝑖 = 1, … , 16
2. Doelfunctie: MIN x1 + x2 + …. + x16
Geheeltallige programmering
1. Geheeltallige variabelen
Hoe formuleren?
1. Beslissingsvariabelen
2. Doelfunctie
3. Beperkingen
→ We werken in Lingo, hier wordt standaard uitgegaan van een niet-negativiteitsvoorwaarde. Je moet
dit dus enkel vermelden als je dit tegen wilt gaan.
Zijn fractionele waardes (bv. x = 3,78) een probleem?
= deelbaarheidsassumptie
o Hangt af van de context, van de situatie
o In het geval van de tafels, kunnen we geen halve tafels maken.
o Maar als we bvb. werken met een rolling horizon (vandaag beginnen aan een stuk en
morgen afmaken) of werken met duizendtallen (3,78 wordt 3780), dan kan dit natuurlijk
wel
Indien de deelbaarheidsassumptie van LP niet opgaat dan moet de restrictie x1, x2 ∈ {0,1,2, … }
uitdrukkelijk meegenomen worden. We spreken dan van geheeltallige programmering (= integer
programmering IP) , soms ook ILP (linear).
- We werken ook met MILP = mixed-integer LP → sommige variabelen zijn geheeltallig, anderen
niet
- We werken ook met ZOIP = zero-one LP of BIP = binary IP → variabelen zijn 0 of 1
Als we de geheeltalligheidseis van een IP weglaten dan krijgen we een LP-relaxatie van dit IP.
Grafische analyse:
- Werkt alleen bij 2 variabelen
- Creatie van een veelhoek door beperkingen (= polyheder,
polyhedron)
- Normaalvector van de doelfunctie is het punt van de waarden
voor de variabelen in de doelfunctie (vb. (8,5))
Stelling: als er een optimale oplossing bestaat, dan bestaat er
minstens één extreem punt van het polyhedron dat optimaal is.
Als we een eindig bereik hebben (gesloten veelhoek) kunnen
we elk hoekpunt overlopen en zo de optimale oplossing eruit halen
Om onze ongelijkheden te kunnen verwijderen uit onze vorm, moeten we variabelen toevoegen (=
verschilvariabelen). Zo bekomen we een standaardvorm.
,Bij stelsels in kanonieke vorm onderscheiden we:
- Basisvariabelen (BV) = afhankelijke, endogene, gebonden variabelen
- Niet-basisvariabelen (NBV) = onafhankelijke, exogene, vrije variabelen
→ Via ero’s (elementaire rij-operaties) kunnen we niet-basisvariabelen manipuleren naar
basisvariabelen
Basisoplossing is het resultaat van het stelsel bij het nemen van de niet-basisvariabelen gelijk
aan 0.
Een toelaatbare basisoplossing (=tbo) heeft alle variabelen ≥ 0
Stelling: elk extreem punt van de LP-oplossingsruimte is een tbo, en omgekeerd.
→ In plaats van alles te enumereren gaat het simplex algoritme verstandiger te werk en wordt LP als
redelijk ‘gemakkelijk beschouwd (later meer)
De oplossingsruimte van een IP is niet convex: het concept van een ‘extreem punt’ is hier zelfs niet
gedefinieerd… kunnen we LP gebruiken om het IP op te lossen
Wat is convex? Als je een lijnstuk trekt tussen 2 punten van het gebied, ligt het lijnstuk ook in
het gebied.
o Afronden gaat niet altijd het optimum leveren (zelfs een toelaatbare oplossing vinden is
soms al moeilijk)
o Wat indien de oplossing van de LP-relaxatie geheeltallig is?
▪ De oplossingsruimte van een IP is een deelverzameling van de oplossingsruimte
van de LP-relaxatie. Bijgevolg is:
𝑚𝑖𝑛 − 𝑝𝑟𝑜𝑏𝑙𝑒𝑒𝑚: 𝑍 ∗ > 𝑍 𝐿𝑃 𝑚𝑎𝑥 − 𝑝𝑟𝑜𝑏𝑙𝑒𝑒𝑚: 𝑍 𝐿𝑃 > 𝑍 ∗
▪ We vinden dus een beneden (lowerbound) - en respectievelijk een bovengrens
(upperbound)
o Eender welk toelaatbaar punt heeft x1≤ 3 ofwel x1 ≥ 4. Partitioneren van de zoekruimte:
branching (vertakken)
▪ Zo kunnen we het grote probleem opdelen in
stukken, zonder geheeltallen te verliezen
▪ Opdelen in deelverzamelingen zodat de unie
alles omvat en de doorsnede leeg is
,Brand-and-bound (= B&B, vertak-en-begrens)
→ Zoekvolgorde in eerste instantie arbitrair, bvb.
1 (LP-relaxatie) → 2 → 4 (infeasible) → 5 → 6 (incumbent) → 5 (fathomed) → backtracking → 3
(fathomed)
GUB = Global upper bound, LUB = local upper bound
We kunnen ook werken met een tolerantie. Wanneer we deze instellen op 0% zijn we enkel tevreden
met de best toelaatbare oplossing, maar dit kan natuurlijk sterk oplopen in rekentijd. Wanneer we
deze anders bvb. definiëren op 5%, dan mag deze hier lichtelijk van afwijken, wat sterke invloed kan
hebben op rekentijd.
Werkwijze LP-gebaseerde B&B:
- Los LP-relaxatie op, indien geheeltallig stop
- Opsplitsen (branching) van de oplossingsruimte van de LP-relaxatie in deelverzamelingen door
beperkingen toe te voegen op de waarden van de geheeltallige, beslissingsvariabelen
- Los een LP op over één deelverzameling
- Indien geheeltallig, bewaar de beste gevonden geheeltallige oplossing (= kandidaat oplossing,
incumbent, momenteel beste GLB) en backtrack
o Anders moet je verder vertakken, behalve indien een LP-relaxatie (lokale bovengrens)
een slechtere (of dezelfde) doelfunctiewaarde heeft dan de huidige incumbent, dan
moet je niet verder opsplitsen en kan je deze tak elimineren in de zoekboom (=
fathomed = afgewerkt) want de doelfunctiewaarde zal lager in de boom nooit
verbeteren.
De beste keuze voor zowel de vertakkingsbeslissing als de keuze van volgorde van oplossen van sub-
problemen is probleem-afhankelijk.
Wanneer X1 en wanneer X2? → welke ligt het dichtste bij 0,5
Eerst linkse tak of eerst rechtse tak? → welke waarde ligt het dichtst bij de variabele (vb. 3,75
ligt dichter bij 4 dus daar beginnen)
, 2. Knapzak
Voorbeeld: capital budgeting
→ Zie ook voorbeeld op papier in video
Voorgaand probleem wordt in de literatuur meestal 0/1 knapzak genoemd. De variant geheeltallige
knapzak werkt niet met binaire variabelen maar wel x1, x2 ∈ {0,1,2, … }
Conclusie van het voorgaande:
- Voordelen van geheeltalligheidseis: realistischer en flexibeler
- Nadelen: moeilijker modelleren, veel moeilijker op te lossen
- Vandaar: gebruik integraliteits-eis spaarzaam
Voor bovenstaande knapzak formuleringen, hoe zou je de volgende logische beperkingen modelleren?
1. We kunnen slechts twee investeringen doen: x1 + x2 + x3 + x4 <= 2
2. Indien investering 2 wordt gedaan, moet 4 ook worden gedaan: x4 >= x2
3. Als investering 1 wordt gedaan, dan kan investering 3 niet worden uitgevoerd: x3 <= 1-x1
4. Idem 3
5. Als investering 1 en investering 2 worden gedaan, dan kan investering 3 niet worden gedaan: x3
<= 2 – (x1+x2)
3. Set covering/packaging/partitioning
3.1. Locatie van brandweerstations
Heuristiek: 5 of 4 of …?
Optimum: 3 (4, 6, 15)
→ hoe weten we met zekerheid wat de optimale doelfunctiewaarde is?
Formulering:
1. Beslissingsvariabelen: 𝑥 𝑖 ∈ {0,1} 𝑣𝑜𝑜𝑟 𝑖 = 1, … , 16
2. Doelfunctie: MIN x1 + x2 + …. + x16
