Miljø til heltalsprogrammering
Løs et lille lineært heltalsprogram med eksakt branch and bound, og se alle søgningens knuder. Det bedste punkt angives kun som bevist optimalt, når hele træet er gennemgået.
Programmer er begrænset til 4.000 tegn og 40 linjer, 8 variabler og 8 begrænsninger med to eller flere variabler. Knudegrænsen er 1 til 5.000, og søgningen stopper også efter 3.000.000 eksakte regnetrin. Alt beregnes på din enhed i en baggrundsproces med en grænse på 15 sekunder. Hent en JSON-rapport og en CSV-fil med knuder. Første linje: maximize eller minimize efterfulgt af målfunktionen. Skriv derefter én begrænsning pr. linje. Op til 4.000 tegn. Gennemgå indstillingerne, før du kører.
Dit resultat
Miljø til heltalsprogrammering
- Skriv målfunktionen på første linje, for eksempel maximize 5x + 4y.
- Tilføj én bibetingelse pr. linje, grænser som x, y >= 0 og eventuelt linjer som integer x eller binary z.
- Angiv knudegrænsen, og kør søgningen.
- Læs status, det bedste fundne punkt, den bedste grænse og gabet, og hent derefter JSON-rapporten eller CSV-filen med knuder.
Det skal du vide
Programmer er begrænset til 4.000 tegn og 40 linjer, 8 variabler og 8 begrænsninger med to eller flere variabler. Knudegrænsen er 1 til 5.000, og søgningen stopper også efter 3.000.000 eksakte regnetrin. Alt beregnes på din enhed i en baggrundsproces med en grænse på 15 sekunder. Hent en JSON-rapport og en CSV-fil med knuder.
Forgrenings- og afgrænsningsmetoden
Hver knude løser den lineære relaxation eksakt med simplexmetoden. En ikke-heltallig variabel deles i to grene, x <= floor og x >= ceiling. Knuder beskæres, hvis deres relaxation er umulig at opfylde eller ikke kan slå det bedste fundne heltalspunkt. Metode: Wolsey, Integer Programming, 2. udgave, kapitel 7 (2020).
Hvad det vil sige, at noget er bevist
Når hver knude er løst eller beskåret med en eksakt grænse, er det bedste fundne punkt bevist optimalt, eller opgaven er bevist umulig at opfylde. Hvis knudegrænsen eller tringrænsen stopper søgningen først, er punktet kun det hidtil bedste fundne; rapporten angiver den bedste grænse og afstanden mellem dem.
Regler for input
Variabler er heltal, medmindre du angiver nogle med integer x, y; i så fald er de øvrige kontinuerte. Begrænsninger for én variabel bliver til grænser. En ubegrænset relaxation stopper søgningen, fordi heltalsprogrammet derefter kan være ubegrænset eller umuligt at opfylde.