Sandbox de programare întreagă
Rezolvă un program liniar întreg mic cu branch-and-bound exact și vezi fiecare nod al căutării. Cel mai bun punct este raportat ca optim demonstrat numai după explorarea întregului arbore.
Programele sunt limitate la 4.000 de caractere și 40 de rânduri, 8 variabile și 8 constrângeri cu cel puțin două variabile; limita de noduri este între 1 și 5.000, iar căutarea se oprește și după 3.000.000 de pași de aritmetică exactă. Totul se calculează pe dispozitiv în fundal, cu o limită de 15 secunde. Descărcări: raport JSON și CSV de noduri. Primul rând: maximize sau minimize și funcția obiectiv. Apoi, câte o constrângere pe rând. Până la 4.000 de caractere. Verifică setările înainte de rulare.
Rezultatul tău
Sandbox de programare întreagă
- Scrie funcția obiectiv pe primul rând, precum maximize 5x + 4y.
- Introdu câte o constrângere pe rând, limite precum x, y >= 0 și rânduri opționale precum integer x sau binary z.
- Setează limita nodurilor și pornește căutarea.
- Consultă starea, incumbentul, cea mai bună limită și diferența, apoi descarcă raportul JSON sau CSV-ul nodurilor.
La ce să te aștepți
Programele sunt limitate la 4.000 de caractere și 40 de rânduri, 8 variabile și 8 constrângeri cu cel puțin două variabile; limita de noduri este între 1 și 5.000, iar căutarea se oprește și după 3.000.000 de pași de aritmetică exactă. Totul se calculează pe dispozitiv în fundal, cu o limită de 15 secunde. Descărcări: raport JSON și CSV de noduri.
Branch and bound
Fiecare nod rezolvă exact relaxarea liniară cu metoda simplex. O variabilă întreagă fracționară este împărțită în două ramuri: x <= floor și x >= ceiling. Nodurile sunt eliminate când relaxarea este imposibilă sau nu poate depăși cel mai bun punct întreg găsit. Metodă: Wolsey, Integer Programming, ediția a 2-a, capitolul 7 (2020).
Ce înseamnă demonstrat
Când fiecare nod a fost rezolvat sau eliminat cu o limită exactă, incumbentul este demonstrat optim sau problema este demonstrată imposibilă. Dacă limita nodurilor sau a pașilor oprește căutarea mai devreme, incumbentul este doar cel mai bun punct găsit până acum, iar raportul arată cea mai bună limită și diferența dintre ele.
Reguli de introducere
Variabilele sunt întregi, cu excepția cazului în care le listezi pe unele cu integer x, y; atunci celelalte sunt continue. Constrângerile cu o singură variabilă devin limite. O relaxare nemărginită oprește căutarea, deoarece programul întreg poate fi nemărginit sau imposibil.