Preizkusno okolje za celoštevilsko programiranje
Rešite majhen celoštevilski linearni program z natančnim razvejanjem in omejevanjem ter si oglejte vsako vozlišče iskanja. Najboljša točka je označena kot dokazana optimalna šele, ko je pregledano celotno drevo.
Programi so omejeni na 4.000 znakov in 40 vrstic, 8 spremenljivk ter 8 omejitev z dvema ali več spremenljivkami; omejitev vozlišč je od 1 do 5.000, iskanje pa se ustavi tudi po 3.000.000 korakih natančne aritmetike. Vse se izračuna v ozadju na vaši napravi z omejitvijo 15 sekund. Prenesete lahko poročilo JSON in CSV vozlišč. V prvo vrstico vnesite maximize ali minimize in ciljno funkcijo. Nato vnesite po eno omejitev v vsako vrstico. Do 4.000 znakov. Pred zagonom preglejte nastavitve.
Vaš rezultat
Preizkusno okolje za celoštevilsko programiranje
- Ciljno funkcijo zapišite v prvi vrstici, na primer maximize 5x + 4y.
- Vsako omejitev vnesite v svojo vrstico, tudi meje, kot je x, y >= 0, in neobvezne vrstice, kot sta integer x ali binary z.
- Nastavite omejitev števila vozlišč in zaženite iskanje.
- Preberite stanje, trenutno najboljšo celoštevilsko rešitev, najboljšo mejo in vrzel, nato prenesite poročilo JSON ali CSV vozlišč.
Kaj lahko pričakujete
Programi so omejeni na 4.000 znakov in 40 vrstic, 8 spremenljivk ter 8 omejitev z dvema ali več spremenljivkami; omejitev vozlišč je od 1 do 5.000, iskanje pa se ustavi tudi po 3.000.000 korakih natančne aritmetike. Vse se izračuna v ozadju na vaši napravi z omejitvijo 15 sekund. Prenesete lahko poročilo JSON in CSV vozlišč.
Razvejanje in omejevanje
Vsako vozlišče natančno reši linearno relaksacijo z metodo simpleks. Celoštevilska spremenljivka z neceloštevilsko vrednostjo se razdeli na veji x <= floor in x >= ceiling. Vozlišče se odreže, če je njegova relaksacija neizvedljiva ali ne more izboljšati najboljše doslej najdene celoštevilske točke. Metoda: Wolsey, Integer Programming, 2. izdaja, 7. poglavje (2020).
Kaj pomeni dokazano
Ko je vsako vozlišče rešeno ali odrezano z natančno mejo, je dokazana optimalnost trenutno najboljše rešitve ali neizvedljivost problema. Če iskanje prej ustavi omejitev vozlišč ali korakov, je trenutna rešitev le najboljša doslej najdena točka, poročilo pa navede najboljšo mejo in razmik med njima.
Pravila za vnos
Spremenljivke so celoštevilske, razen če nekatere navedete kot integer x, y; v tem primeru so druge zvezne. Omejitve ene spremenljivke postanejo meje. Če je relaksacija neomejena, se iskanje ustavi, saj je celoštevilski program lahko neomejen ali neizvedljiv.