Pískoviště celočíselného programování
Vyřešte malý celočíselný lineární program pomocí přesné metody větví a mezí a prohlédněte si každý uzel hledání. Nejlepší bod je označen jako prokázaně optimální pouze tehdy, když byl prozkoumán celý strom.
Programy jsou omezeny na 4 000 znaků a 40 řádků, 8 proměnných a 8 omezení zahrnujících dvě nebo více proměnných; limit uzlů je 1 až 5 000 a hledání také končí po 3 000 000 krocích přesné aritmetiky. Vše se počítá na zařízení na pozadí s limitem 15 sekund. Ke stažení: zpráva JSON a CSV uzlů. První řádek: maximize nebo minimize a účelová funkce. Poté jedno omezení na řádek. Nejvýše 4 000 znaků. Před spuštěním zkontrolujte nastavení.
Váš výsledek
Pískoviště celočíselného programování
- Účelovou funkci zapište na první řádek, například maximize 5x + 4y.
- Zadejte jedno omezení na řádek, meze jako x, y >= 0 a volitelné řádky jako integer x nebo binary z.
- Nastavte limit uzlů a spusťte hledání.
- Přečtěte si stav, dosud nejlepší řešení, nejlepší mez a rozdíl a poté stáhněte zprávu JSON nebo CSV uzlů.
Co očekávat
Programy jsou omezeny na 4 000 znaků a 40 řádků, 8 proměnných a 8 omezení zahrnujících dvě nebo více proměnných; limit uzlů je 1 až 5 000 a hledání také končí po 3 000 000 krocích přesné aritmetiky. Vše se počítá na zařízení na pozadí s limitem 15 sekund. Ke stažení: zpráva JSON a CSV uzlů.
Metoda větví a mezí
Každý uzel řeší přesně lineární relaxaci simplexovou metodou. Zlomková celočíselná proměnná se rozdělí do dvou větví: x <= floor a x >= ceiling. Uzly se ořezávají, pokud je jejich relaxace neproveditelná nebo nemohou překonat dosud nejlepší nalezený celočíselný bod. Metoda: Wolsey, Integer Programming, 2. vydání, kapitola 7 (2020).
Co znamená dokázáno
Pokud byl každý uzel vyřešen nebo oříznut přesnou mezí, je prokázáno, že dosud nejlepší řešení je optimální, nebo že úloha nemá přípustné řešení. Pokud hledání zastaví limit počtu uzlů nebo kroků dříve, dosud nejlepší řešení je pouze nejlepším nalezeným bodem; zpráva uvádí nejlepší mez a rozdíl mezi nimi.
Pravidla vstupu
Proměnné jsou celočíselné, pokud některé neuvedete pomocí integer x, y; ostatní jsou pak spojité. Omezení jedné proměnné se převedou na meze. Pokud je relaxace neomezená, hledání se zastaví, protože celočíselná úloha může být také neomezená nebo nemusí mít přípustné řešení.