Okruženje za celobrojno programiranje
Rešite mali celobrojni linearni program tačnim grananjem i ograničavanjem i pogledajte svaki čvor pretrage. Najbolja tačka navodi se kao dokazano optimalna samo kada je celo stablo pretraženo.
Programi su ograničeni na 4.000 znakova i 40 redova, 8 promenljivih i 8 ograničenja s dve ili više promenljivih; ograničenje čvorova je od 1 do 5.000, a pretraga se zaustavlja i posle 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 izveš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 pre pokretanja.
Vaš rezultat
Okruženje za celobrojno programiranje
- Ciljnu funkciju napišite u prvom redu, na primer maximize 5x + 4y.
- Dodajte po jedno ograničenje u svaki red, 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, najbolje dosadašnje rešenje, najbolju granicu i razliku, pa preuzmite JSON izveštaj ili CSV čvorova.
Šta možete očekivati
Programi su ograničeni na 4.000 znakova i 40 redova, 8 promenljivih i 8 ograničenja s dve ili više promenljivih; ograničenje čvorova je od 1 do 5.000, a pretraga se zaustavlja i posle 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 izveštaj i CSV čvorova.
Grananje i ograničavanje
Svaki čvor tačno rešava linearnu relaksaciju simpleks metodom. Celobrojna promenljiva s razlomljenom vrednošću deli se na dve grane, x <= floor i x >= ceiling. Čvorovi se odbacuju kada je relaksacija neizvodljiva ili kada ne može da pruži rešenje bolje od najbolje pronađene celobrojne tačke. Metoda: Wolsey, Integer Programming, 2. izdanje, 7. poglavlje (2020).
Šta znači dokazano
Kada je svaki čvor rešen ili odbačen tačnom granicom, najbolje dosadašnje rešenje dokazano je optimalno ili je dokazano da je zadatak neizvodljiv. Ako pretragu ranije zaustavi ograničenje broja čvorova ili koraka, to rešenje je samo najbolja dosad pronađena tačka, a izveštaj navodi najbolju granicu i razliku između njih.
Pravila unosa
Promenljive su celobrojne osim ako neke ne navedete uz integer x, y; tada su ostale kontinuirane. Ograničenja s jednom promenljivom postaju granice. Neograničena relaksacija zaustavlja pretragu jer celobrojni program tada može biti neograničen ili neizvodljiv.