Prostredie na celočíselné programovanie
Riešte malú celočíselnú lineárnu úlohu presným vetvením a ohraničovaním a zobrazte každý uzol vyhľadávania. Najlepší bod je označený ako dokázane optimálny iba po preskúmaní celého stromu.
Programy môžu mať najviac 4 000 znakov, 40 riadkov, 8 premenných a 8 obmedzení s dvoma alebo viacerými premennými. Hranica uzlov je 1 až 5 000 a vyhľadávanie sa zastaví aj po 3 000 000 presných aritmetických krokoch. Všetko sa počíta vo vašom zariadení na pozadí s časovým limitom 15 sekúnd. Stiahnite si správu JSON a CSV s uzlami. Prvý riadok: maximize alebo minimize a cieľová funkcia. Potom jedno obmedzenie na každý riadok. Najviac 4 000 znakov. Pred spustením skontrolujte nastavenia.
Váš výsledok
Prostredie na celočíselné programovanie
- Cieľ zapíšte na prvý riadok, napríklad maximize 5x + 4y.
- Pridajte jedno obmedzenie na riadok, hranice ako x, y >= 0 a prípadné riadky ako integer x alebo binary z.
- Nastavte hranicu uzlov a spustite vyhľadávanie.
- Prečítajte si stav, najlepší nájdený bod, najlepšiu hranicu a rozdiel; potom si stiahnite správu JSON alebo CSV s uzlami.
Čo môžete očakávať
Programy môžu mať najviac 4 000 znakov, 40 riadkov, 8 premenných a 8 obmedzení s dvoma alebo viacerými premennými. Hranica uzlov je 1 až 5 000 a vyhľadávanie sa zastaví aj po 3 000 000 presných aritmetických krokoch. Všetko sa počíta vo vašom zariadení na pozadí s časovým limitom 15 sekúnd. Stiahnite si správu JSON a CSV s uzlami.
Vetvenie a ohraničovanie
Každý uzol rieši lineárnu relaxáciu presne simplexovou metódou. Neceločíselná celočíselná premenná sa rozdelí na dve vetvy, x <= floor a x >= ceiling. Uzly sa orežú, ak je ich relaxácia nesplniteľná alebo nemôže prekonať najlepší nájdený celočíselný bod. Metóda: Wolsey, Integer Programming, 2. vydanie, kapitola 7 (2020).
Čo znamená „dokázané“
Keď sa každý uzol vyrieši alebo odreže presnou hranicou, najlepší nájdený bod je dokázane optimálny alebo je dokázané, že úloha nemá riešenie. Ak vyhľadávanie zastaví limit uzlov alebo krokov, bod je iba najlepší nájdený doteraz; správa uvádza najlepšiu hranicu a rozdiel medzi nimi.
Pravidlá pre vstup
Premenné sú celé čísla, pokiaľ niektoré nevymenujete na samostatnom riadku, napríklad integer x, y; ostatné sú spojité. Obmedzenia jednej premennej sa zmenia na hranice. Neohraničená relaxácia zastaví vyhľadávanie, pretože celočíselná úloha môže byť neohraničená alebo nesplniteľná.