Okruženje za cjelobrojno programiranje
Riješite mali cjelobrojni linearni program tačnim grananjem i ograničavanjem i pregledajte svaki čvor pretrage. Najbolja tačka navodi se kao dokazano optimalna samo kada je pretraženo cijelo stablo.
Programi su ograničeni na 4.000 znakova i 40 redova, 8 varijabli i 8 ograničenja s dvije ili više varijabli; ograničenje broja čvorova je od 1 do 5.000, a pretraga se zaustavlja i nakon 3.000.000 koraka tačne aritmetike. Sve se računa na vašem uređaju u pozadinskom procesu s ograničenjem od 15 sekundi. Preuzimanja su JSON izvještaj i CSV čvorova. Prvi red: maximize ili minimize i ciljna funkcija. Zatim unesite po jedno ograničenje u svaki red. Do 4.000 znakova. Pregledajte postavke prije pokretanja.
Vaš rezultat
Okruženje za cjelobrojno programiranje
- Ciljnu funkciju napišite u prvom redu, npr. maximize 5x + 4y.
- Dodajte jedno ograničenje po redu, granice poput x, y >= 0 i neobavezne redove poput integer x ili binary z.
- Postavite ograničenje broja čvorova i pokrenite pretragu.
- Pročitajte status, trenutno najbolje rješenje, najbolju granicu i razliku, a zatim preuzmite JSON izvještaj ili CSV čvorova.
Šta možete očekivati
Programi su ograničeni na 4.000 znakova i 40 redova, 8 varijabli i 8 ograničenja s dvije ili više varijabli; ograničenje broja čvorova je od 1 do 5.000, a pretraga se zaustavlja i nakon 3.000.000 koraka tačne aritmetike. Sve se računa na vašem uređaju u pozadinskom procesu s ograničenjem od 15 sekundi. Preuzimanja su JSON izvještaj i CSV čvorova.
Grananje i ograničavanje
U svakom čvoru linearna relaksacija rješava se tačno simpleks metodom. Cjelobrojna varijabla s necjelobrojnom vrijednošću dijeli se na dvije grane, x <= floor i x >= ceiling. Čvorovi se odbacuju kada je njihova relaksacija neizvodiva ili ne može nadmašiti najbolju pronađenu cjelobrojnu tačku. Metoda: Wolsey, Integer Programming, 2. izdanje, 7. poglavlje (2020.).
Šta znači dokazano
Kada je svaki čvor riješen ili odbačen tačnom granicom, trenutno najbolje rješenje dokazano je optimalno ili je problem dokazano neizvodiv. Ako pretragu ranije zaustavi ograničenje broja čvorova ili koraka, trenutno najbolje rješenje samo je najbolja dosad pronađena tačka, a izvještaj daje 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. Neograničena relaksacija zaustavlja pretragu jer cjelobrojni program tada može biti neograničen ili neizvodiv.