Technische Samenvatting: Over het afleiden van cumulatieve restricties

Probleemstelling

Cumulatieve restricties vormen een hoeksteen van constraint programming (CP) voor planning, waarbij beperkte hernieuwbare hulpbronnen worden gemodelleerd. Echter, standaard propagatietechnieken redeneren doorgaans onafhankelijk over elke hulpbronrestrictie. Dit "single-resource viewpoint" faalt bij het vastleggen van interacties tussen meerdere hulpbronnen, wat leidt tot ernstige prestatievermindering op specifieke benchmarks (bijv. de "3n problem" structuur).

Eerdere pogingen om dit aan te pakken, zoals de "Unite and Lead" (UNL) benadering door Sidorov et al. [2025a], identificeerden succesvol verborgen disjunctieve structuren (sets van taken die niet parallel kunnen draaien). UNL lijdt echter aan twee kritieke beperkingen:

1. Gebrek aan Generaliteit: Het is beperkt tot disjunctieve redenering en kan geen meer algemene interacties tussen meerdere hulpbronnen afleiden.
2. Zoekoverhead: Het vereist expliciete probing naar disjunctieve cliques tijdens de zoektocht, wat aanzienlijke overhead veroorzaakt die solvers vaak met een factor orde van grootte vertraagt op instanties die dergelijke structuren missen.

Het kernprobleem dat in dit artikel wordt aangepakt, is hoe men geldige interacties tussen meerdere hulpbronnen kan afleiden en het model kan versterken zonder de zoektijd-penaliteiten te dragen die gepaard gaan met dynamische clique-detectie.

Methodologie

De voorgestelde aanpak herformuleert cumulatieve restricties als lineaire ongelijkheden over bezettingvectoren en past technieken uit de polyhedrale meetkunde en mixed-integer programming (MIP) toe om nieuwe restricties af te leiden in de root node (preprocessing).

1. Theoretische Fundering

De methode rust op de representatie van taakstarttijden $s_i$ en duur $d_i$ als bezettingsvectoren $\langle s_i | d_i \rangle$, waarbij de vector 1 is tijdens het interval $[s_i, s_i + d_i)$ en 0 anders. Een cumulatieve restrictie $\sum r_i \langle s_i | d_i \rangle \le C$ wordt hierdoor beschouwd als een lineaire ongelijkheid.

• Lemma 7 stelt vast dat elke geldige ongelijkheid voor het polytheder gedefinieerd door de bezettingsvectoren overeenkomt met een geldige cumulatieve restrictie voor het oorspronkelijke planningsprobleem.
• Dit maakt het mogelijk om het probleem van het afleiden van restricties te behandelen als het genereren van geldige snijvlakken (cutting planes).

2. De Lifting-gebaseerde Workflow

In plaats van dynamisch te zoeken naar disjunctieve cliques, voert het algoritme een statische preprocessing-stap uit bestaande uit drie stadia:

1. Cover Discovery: Het algoritme enumereert "covers" (sets van taken $C$ waar de som van de hulpbronvereisten de capaciteit overschrijdt, i.e., $\sum_{i \in C} r_i > C$). Het genereert "korte" covers (cardinaliteit 2 en 3) en "lange" covers (gegroepeerd op basis van hulpbronconsumptiewaarden) en selecteert de meest veelbelovende kandidaten op basis van een capaciteitsgrens metriek ($L$), die de minimale maaktspan schat die door de taken wordt beslagen.
2. Lifting: Voor elke ontdekte cover past de methode de lifting procedure toe (Padberg, 1975). Dit versterkt de basis cover-ongelijkheid ($\sum_{i \in C} x_i \le |C| - 1$) door de maximale coëfficiënt $\beta$ te bepalen voor variabelen die oorspronkelijk niet in de cover zaten, zodanig dat de ongelijkheid $\sum_{i \in C} x_i + \beta x_j \le |C| - 1$ geldig blijft. Dit wordt bereikt door hulp-subproblemen op te lossen (het maximaliseren van de linkerzijde van de huidige ongelijkheid onder specifieke restricties).
3. Constraint Injection: De resulterende gelifte ongelijkheden worden teruggeconverteerd naar nieuwe cumulatieve restricties en geïnjecteerd in de probleeminstantie voordat de CP-solver zijn zoektocht begint.

De implementatie gebruikt Gurobi 12 om de lifting-subproblemen op te lossen en beperkt het aantal gegenereerde restricties ($N_{out}$) en initiële covers ($N_{cover}$) om de preprocessing-tijd te beheersen.

Belangrijkste Bijdragen

• Algoritmisch Kader: Een nieuwe methode voor het afleiden van cumulatieve restricties die verder gaat dan disjunctieve redenering en interacties tussen meerdere hulpbronnen vastlegt via geldige ongelijkheden.
• Preprocessing Strategie: Een root-node aanpak die de zoektijd-overhead van dynamische clique-detectie vermijdt, waardoor de instabiliteit van eerdere UNL-gebaseerde methoden wordt geëlimineerd.
• Integratie van MIP-technieken: De toepassing van lifting en cover-ongelijkheden uit integer programming op het domein van constraint programming scheduling.
• Kwaliteitsmetriek: De introductie van de capaciteitsgrensratio als een heuristiek voor het selecteren van welke covers gelift moeten worden en welke afgeleide restricties behouden moeten blijven.

Experimentele Resultaten

De methode werd geëvalueerd op standaard RCPSP (736 instanties) en RCPSP/max (349 instanties) benchmarks met behulp van state-of-the-art solvers (Pumpkin en CP-SAT).

• Prestatiewinsten:
  • Optimaliteit: Voor instanties die tot optimaliteit werden opgelost, verminderde lifting de oplostijd aanzienlijk, soms van tientallen minuten naar fracties van een seconde.
  • Zoekprogressie: Op instanties die niet tot optimaliteit werden opgelost, verbeterde de aanpak de duale integraal (snelheid van de verbetering van de ondergrens) aanzienlijk, wat wijst op snellere convergentie naar strakkere grenzen.
  • Stabiliteit: In tegen tegenstelling tot UNL was de degradatie in prestaties (toename in oplostijd) zeldzaam. Slechts 19 paren van runs vertoonden significante vertragingen, en zelfs de "2x degradatie" gebeurtenis kwam slechts op het 9ste percentiel voor.
• Nieuwe Grenzen:
  • De aanpak ontdekte 25 nieuwe ondergrenzen en vijf nieuwe beste oplossingen (bovengrenzen).
  • Acht van de nieuwe ondergrenzen werden direct geverifieerd door de afgeleide restricties zonder dat er een zoektocht nodig was.
• Preprocessing Overhead: De preprocessing-fase (cover generatie en lifting) nam doorgaans slechts enkele seconden in beslag. Instanties waarbij dit langer duurde (>1 minuut) waren uitsluitend grootschalige instanties (UBO500/UBO1000) met meer dan 500 taken.
• Restrictietypes: De meest significante winsten werden waargenomen wanneer de beste afgeleide restrictie disjunctief was (eenheidscapaciteit), hoewel algemene cumulatieve restricties ook matige verbeteringen boden.

Betekenis en Claims

Het artikel claimt dat deze aanpak erin slaagt de positieve eigenschappen van de UNL-methode (substantiële winsten op instanties met verborgen structuren) te behouden terwijl het de primaire zwakte (instabiliteit en ernstige vertragingen op instanties zonder dergelijke structuren) vermijdt.

Door cumulatieve restricties te interpreteren via de lens van de polyhedrale meetkunde, biedt de methode een systematische manier om modellen te versterken met geldige ongelijkheden. De auteurs benadrukken dat dit een preprocessing techniek is; het vervangt de solver niet maar verbetert de input-instantie. De resultaten suggeries dat het afleiden van restricties via lifting een robuuste strategie is om de state-of-the-art op scheduling benchmarks te verbeteren, met name voor het aanscherpen van ondergrenzen en het verminderen van de zoekinspanning, zonder het risico op de "orde van grootte" vertragingen die geassocieerd worden met eerdere dynamische probing-technieken.