Okruženje za cjelobrojno programiranje
Riješite mali cjelobrojni linearni program točnim grananjem i omeđivanjem te pogledajte svaki čvor pretraživanja. Najbolja se točka navodi kao dokazano optimalna samo ako je pretraženo cijelo stablo.
Programi su ograničeni na 4.000 znakova i 40 redaka, 8 varijabli te 8 ograničenja s dvije ili više varijabli; ograničenje broja čvorova iznosi od 1 do 5.000, a pretraživanje se zaustavlja i nakon 3.000.000 koraka točne aritmetike. Sve se računa na vašem uređaju u pozadinskom radniku s ograničenjem od 15 sekundi. Preuzimanja su JSON izvješće i CSV čvorova. Prvi redak: maximize ili minimize i ciljna funkcija. Zatim unesite po jedno ograničenje u svaki redak. Do 4.000 znakova. Pregledajte postavke prije pokretanja.
Vaš rezultat
Okruženje za cjelobrojno programiranje
- Ciljnu funkciju napišite u prvom retku, primjerice maximize 5x + 4y.
- Dodajte jedno ograničenje po retku, granice poput x, y >= 0 te neobvezne retke poput integer x ili binary z.
- Postavite ograničenje broja čvorova i pokrenite pretraživanje.
- Pročitajte status, trenutačno najbolje rješenje, najbolju granicu i razliku, a zatim preuzmite JSON izvješće ili CSV čvorova.
Što možete očekivati
Programi su ograničeni na 4.000 znakova i 40 redaka, 8 varijabli te 8 ograničenja s dvije ili više varijabli; ograničenje broja čvorova iznosi od 1 do 5.000, a pretraživanje se zaustavlja i nakon 3.000.000 koraka točne aritmetike. Sve se računa na vašem uređaju u pozadinskom radniku s ograničenjem od 15 sekundi. Preuzimanja su JSON izvješće i CSV čvorova.
Grananje i omeđivanje
U svakom se čvoru linearna relaksacija točno rješava simpleksnom metodom. Cjelobrojna varijabla s necjelobrojnom vrijednošću dijeli se u dvije grane, x <= floor i x >= ceiling. Čvorovi se odbacuju kada je njihova relaksacija neizvediva ili ne može nadmašiti najbolju pronađenu cjelobrojnu točku. Metoda: Wolsey, Integer Programming, 2. izdanje, 7. poglavlje (2020.).
Što znači dokazano
Kada je svaki čvor riješen ili odbačen pomoću točne granice, trenutačno najbolje rješenje dokazano je optimalno ili je dokazano da je zadatak neizvediv. Ako pretraživanje prije toga zaustavi ograničenje čvorova ili koraka, trenutačno rješenje samo je najbolja dosad pronađena točka, a izvješće navodi najbolju granicu i razliku između njih.
Pravila unosa
Varijable su cjelobrojne osim ako neke ne navedete uz integer x, y; tada su ostale kontinuirane. Ograničenja s jednom varijablom postaju granice. Neomeđena relaksacija zaustavlja pretraživanje jer cjelobrojni program tada može biti neomeđen ili neizvediv.