Piaskownica programowania całkowitoliczbowego
Rozwiąż mały całkowitoliczbowy program liniowy za pomocą dokładnego branch-and-bound i zobacz każdy węzeł wyszukiwania. Punkt najlepszy jest zgłaszany jako optymalny dopiero po przejściu całego drzewa.
Programy są ograniczone do 4000 znaków i 40 wierszy, 8 zmiennych oraz 8 ograniczeń obejmujących dwie lub więcej zmiennych; limit węzłów wynosi od 1 do 5000, a wyszukiwanie zatrzymuje się również po 3 000 000 kroków dokładnej arytmetyki. Wszystko jest obliczane na urządzeniu w tle, z limitem 15 sekund. Pobrane pliki: raport JSON i CSV węzłów. Pierwszy wiersz: maximize lub minimize i funkcja celu. Następnie po jednym ograniczeniu w każdym wierszu. Do 4000 znaków. Sprawdź ustawienia przed uruchomieniem.
Twój wynik
Piaskownica programowania całkowitoliczbowego
- W pierwszym wierszu zapisz funkcję celu, np. maximize 5x + 4y.
- Wpisz po jednym ograniczeniu w wierszu, ograniczenia takie jak x, y >= 0 oraz opcjonalne wiersze, np. integer x lub binary z.
- Ustaw limit węzłów i uruchom wyszukiwanie.
- Odczytaj status, rozwiązanie incumbent, najlepsze ograniczenie i lukę, a następnie pobierz raport JSON lub CSV węzłów.
Warto wiedzieć
Programy są ograniczone do 4000 znaków i 40 wierszy, 8 zmiennych oraz 8 ograniczeń obejmujących dwie lub więcej zmiennych; limit węzłów wynosi od 1 do 5000, a wyszukiwanie zatrzymuje się również po 3 000 000 kroków dokładnej arytmetyki. Wszystko jest obliczane na urządzeniu w tle, z limitem 15 sekund. Pobrane pliki: raport JSON i CSV węzłów.
Branch and bound
Każdy węzeł rozwiązuje dokładnie relaksację liniową metodą simpleks. Ułamkowa zmienna całkowita jest dzielona na dwie gałęzie: x <= floor i x >= ceiling. Węzły są odrzucane, gdy relaksacja jest niewykonalna lub nie może poprawić najlepszego znalezionego punktu całkowitego. Metoda: Wolsey, Integer Programming, wyd. 2, rozdział 7 (2020).
Co oznacza „udowodniono”
Gdy każdy węzeł zostanie rozwiązany lub odrzucony na podstawie dokładnego ograniczenia, rozwiązanie incumbent jest udowodnione jako optymalne albo problem jako niewykonalny. Jeśli limit węzłów lub kroków zatrzyma wyszukiwanie wcześniej, incumbent jest tylko najlepszym znalezionym dotąd punktem; raport podaje najlepsze ograniczenie i różnicę między nimi.
Zasady wprowadzania danych
Zmienne są całkowite, chyba że niektóre z nich zostaną zadeklarowane jako całkowite przez integer x, y; wtedy pozostałe są ciągłe. Ograniczenia pojedynczej zmiennej stają się granicami. Nieograniczona relaksacja zatrzymuje wyszukiwanie, ponieważ program całkowitoliczbowy może być nieograniczony lub niewykonalny.