Geheeloreprogrammering

Geheeltallige programmering (GP; Engels integer programming, IP) — is een deelgebied van de wiskundige optimalisatie, waarbij problemen worden bestudeerd waarbij sommige of alle variabelen uitsluitend geheeltallige waarden mogen aannemen.

Het meest bestudeerde bijzondere geval is geheeltallige lineaire programmering (GLP; Engels integer linear programming, ILP), waarbij de doelstelling en de beperkingen lineair zijn. In tegenstelling tot lineaire programmering, waarbij variabelen willekeurige reële waarden kunnen aannemen, maakt de eis van geheeltalligheid GP-problemen aanzienlijk moeilijker op te lossen.

Geheeltallige programmering wordt breed toegepast in de economie, logistiek, productieplanning en andere gebieden waar variabelen van nature discreet zijn (bijvoorbeeld het aantal geproduceerde eenheden of het aantal werknemers).

Definitie en terminologie

Het algemene probleem van geheeltallige lineaire programmering kan als volgt worden geformuleerd:

Vind een vector $x$, die:

maximaliseert (of minimaliseert) $c^{T}x$

onder de voorwaarden:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{Z}}^n$ (alle componenten van vector $x$ zijn gehele getallen)

waar $x$ de vector van variabelen is, $c$ en $b$ vectoren zijn, en $A$ een coëfficiëntenmatrix is.

Al naar gelang de eisen aan de variabelen worden de volgende typen problemen onderscheiden:

• Volledig geheeltallige programmering: alle variabelen moeten geheel zijn.
• Gemengd-geheeltallige programmering (Engels mixed-integer programming, MIP): slechts een deel van de variabelen moet geheeltallig zijn.
• Binaire (0-1) programmering: variabelen nemen alleen de waarden 0 of 1 aan, waarmee logische beslissingen van het type «ja/nee» kunnen worden gemodelleerd.

Belangrijkste eigenschappen en complexiteit

Rekenkundige complexiteit

Het probleem van geheeltallige lineaire programmering is in het algemeen NP-moeilijk. Dit betekent dat er geen bekend algoritme bestaat dat voor een willekeurig GP-probleem in polynomiale tijd een exacte optimale oplossing kan vinden. De complexiteit is het gevolg van de combinatorische aard van het probleem, omdat het aantal mogelijke geheeltallige oplossingen exponentieel kan groeien naarmate het aantal variabelen toeneemt.

Relatie met lineaire programmering (LP-relaxatie)

Voor elk GP-probleem kan men de bijbehorende lineaire relaxatie formuleren — een lineair programmeringsprobleem (LP) waarbij de eis van geheeltalligheid van de variabelen is losgelaten. De oplossing van de LP-relaxatie heeft twee belangrijke eigenschappen:

1. Ze kan aanzienlijk sneller worden gevonden (in polynomiale tijd).
2. De optimale waarde van de doelstelling van de LP-relaxatie geeft een schatting (een bovengrens voor een maximalisatieprobleem en een ondergrens voor minimalisatie) voor de optimale waarde van het oorspronkelijke geheeltallige probleem.

Eenvoudig afronden van de gebroken oplossing van de LP-relaxatie naar de dichtstbijzijnde gehele getallen leidt echter doorgaans niet tot een optimale of zelfs toelaatbare oplossing van het geheeltallige probleem.

Eigenschap van volledige unimodulariteit

Er bestaat een belangrijke klasse van GLP-problemen die even eenvoudig oplosbaar zijn als hun LP-relaxaties. Dit zijn problemen waarbij de beperkingsmatrix $A$ volledig unimodullair is (dat wil zeggen dat de determinant van elke vierkante deelmatrix gelijk is aan 0, +1 of −1). Als de matrix $A$ volledig unimodullair is en de vector $b$ geheeltallig is, dan zijn alle hoekpunten van de veelhoek van toelaatbare oplossingen van de LP-relaxatie automatisch geheeltallig. De oplossing die met de simplexmethode wordt gevonden, zal bijgevolg geheeltallig zijn. Voorbeelden van dergelijke problemen zijn het transportprobleem en het toewijzingsprobleem.

Oplossingsmethoden

Voor het oplossen van algemene GP-problemen die niet de eigenschap van volledige unimodulariteit bezitten, zijn exacte methoden ontwikkeld die gebaseerd zijn op het principe van impliciete opsomming.

• Branch and Bound (Nederlands: tak-en-grens-methode) — de belangrijkste exacte methode, gebaseerd op het systematisch opdelen van de verzameling toelaatbare oplossingen in deelverzamelingen (vertakking) en het afkappen van die deelverzamelingen die aantoonbaar geen optimale oplossing bevatten. Voor het beoordelen van de belofte van deelverzamelingen wordt de LP-relaxatie gebruikt.

• Snijvlakkenmethode (methode van Gomory; Engels Cutting Plane Method) — een iteratieve aanpak die stapsgewijs nieuwe lineaire beperkingen («snijvlakken») aan het probleem toevoegt. Deze snijvlakken «snijden» de gebroken oplossingen van de LP-relaxatie weg zonder ook maar één toelaatbare geheeltallige oplossing te raken, waardoor het toelaatbare gebied van de LP-relaxatie geleidelijk de convexe omhullende van de geheeltallige oplossingen benadert.

Moderne solvers maken doorgaans gebruik van hybride algoritmen, zoals Branch and Cut, dat de voordelen van beide benaderingen combineert.

Voorbeelden en toepassingsgebieden

Geheeltallige programmering maakt het mogelijk vele klassieke combinatorische optimalisatieproblemen te modelleren.

• Het knapzakprobleem: een klassiek 0-1 programmeringsprobleem waarbij een verzameling voorwerpen met maximale totale waarde moet worden gekozen zonder de beperking op het totale gewicht te overschrijden.
• Het handelsreizigersprobleem: het probleem van het vinden van de kortste route die langs een gegeven set steden voert. Het kan worden geformuleerd als een geheeltallig programmeringsprobleem, waarbij de variabelen bepalen welke kanten van de graaf in de uiteindelijke route worden opgenomen.

Dankzij zijn flexibiliteit is GP een van de meest gevraagde instrumenten in het operations research en wordt het toegepast in gebieden als:

• Logistiek en supply chain management: optimalisatie van transportroutes, locatiekeuze van magazijnen, voorraadbeheer.
• Productieplanning: opstellen van productieschema's, verdeling van middelen, bezetting van apparatuur.
• Financiën en economie: samenstelling van beleggingsportefeuilles, kapitaalbudgettering.
• Telecommunicatie en energiesector: ontwerp van communicatienetwerken, planning van de inzet van energiecentrales.

Zie ook

• Lineaire programmering
• Branch and Bound

Noten

</references>