Heltallsprogrammeringssandkasse
Løs et lite lineært heltallsprogram med eksakt gren-og-grense-metode, og se hver søkenode. Punktet rapporteres som bevist optimalt bare når hele søketreet er utforsket.
Programmer er begrenset til 4,000 tegn og 40 linjer, 8 variabler og 8 betingelser med to eller flere variabler. Nodetallet er fra 1 til 5,000, og søket stopper også etter 3,000,000 eksakte regneoperasjoner. Alt beregnes på enheten din i en bakgrunnsarbeider med en tidsgrense på 15 sekunder. Nedlastinger: JSON-rapport og CSV-fil med noder. Første linje: maximize eller minimize og målfunksjonen. Deretter én betingelse per linje. Opptil 4,000 tegn. Se gjennom innstillingene før du kjører.
Resultatet ditt
Heltallsprogrammeringssandkasse
- Skriv målfunksjonen på første linje, for eksempel maximize 5x + 4y.
- Legg til én betingelse per linje, grenser som x, y >= 0 og valgfrie linjer som integer x eller binary z.
- Angi nodetallet, og kjør søket.
- Les statusen, den hittil beste heltallsløsningen, den beste grensen og gapet. Last deretter ned JSON-rapporten eller CSV-filen med noder.
Dette bør du vite
Programmer er begrenset til 4 000 tegn og 40 linjer, 8 variabler og 8 betingelser med to eller flere variabler. Nodetallet er fra 1 til 5 000, og søket stopper også etter 3 000 000 eksakte regneoperasjoner. Alt beregnes på enheten din i en bakgrunnsarbeider med en tidsgrense på 15 sekunder. Nedlastinger: JSON-rapport og CSV-fil med noder.
Gren- og grensemetoden
Hver node løser den lineære relaksasjonen eksakt med simplexmetoden. En heltallsvariabel med brøkverdi deles i to grener, x <= floor og x >= ceiling. Noder forkastes når relaksasjonen er umulig eller ikke kan slå det beste heltallspunktet som er funnet. Metode: Wolsey, Integer Programming, 2. utgave, kapittel 7 (2020).
Dette betyr «bevist»
Når hver node er løst eller forkastet med en eksakt grense, er den beste heltallsløsningen bevist optimal, eller problemet er bevist ugjennomførbart. Hvis nodetallet eller trinnbudsjettet stopper søket først, er løsningen bare den beste som er funnet hittil; rapporten viser den beste grensen og gapet mellom dem.
Inndataregler
Variabler er heltall med mindre du oppgir noen med integer x, y; da er de andre kontinuerlige. Betingelser med én variabel blir grenser. Et ubegrenset relaksasjonsproblem stopper søket fordi heltallsprogrammet da kan være ubegrenset eller ugjennomførbart.