Sandlåda för heltalsprogrammering
Lös ett litet heltalslinjärt program med exakt gren-och-gränssökning och visa varje söknod. Den bästa punkten anges som bevisat optimal endast när hela trädet har undersökts.
Program begränsas till 4 000 tecken och 40 rader, 8 variabler och 8 villkor med två eller fler variabler; nodgränsen är 1 till 5 000 och sökningen stannar också efter 3 000 000 exakta aritmetiksteg. Allt beräknas på din enhet i en bakgrundsarbetare med en gräns på 15 sekunder. Nedladdningar: JSON-rapport och CSV-fil med noder. Första raden: maximera eller minimera och målfunktionen. Därefter ett villkor per rad. Upp till 4 000 tecken. Kontrollera inställningarna innan du kör.
Ditt resultat
Sandlåda för heltalsprogrammering
- Skriv målfunktionen på första raden, till exempel maximera 5x + 4y.
- Lägg till ett villkor per rad, begränsningar som x, y >= 0 och valfria rader som integer x eller binary z.
- Ställ in nodgränsen och kör sökningen.
- Läs statusen, den bästa hittade lösningen, den bästa gränsen och gapet. Ladda sedan ned JSON-rapporten eller CSV-filen med noder.
Vad du kan förvänta dig
Program begränsas till 4 000 tecken och 40 rader, 8 variabler och 8 villkor med två eller fler variabler; nodgränsen är 1 till 5 000 och sökningen stannar också efter 3 000 000 exakta aritmetiksteg. Allt beräknas på din enhet i en bakgrundsarbetare med en gräns på 15 sekunder. Nedladdningar: JSON-rapport och CSV-fil med noder.
Gren-och-gränsmetoden
Varje nod löser den linjära relaxation exakt med simplexmetoden. En heltalsvariabel med bråkvärde delas upp i två grenar: x <= floor och x >= ceiling. Noder tas bort när deras relaxation saknar tillåtna lösningar eller inte kan slå den bästa heltalslösningen som hittats. Metod: Wolsey, Integer Programming, 2:a upplagan, kapitel 7 (2020).
Vad bevisat betyder
När varje nod har lösts eller gallrats bort med en exakt gräns har den bästa hittade heltalslösningen bevisats optimal, eller så har problemet bevisats sakna lösning. Om nodgränsen eller stegbudgeten avbryter sökningen först är den bästa heltalslösningen hittills inte bevisat optimal; rapporten visar den bästa gränsen och skillnaden mellan dem.
Inmatningsregler
Variablerna är heltal om du inte anger några med integer x, y; då är de övriga kontinuerliga. Villkor med en enda variabel blir gränser. Om en relaxation är obegränsad avbryts sökningen, eftersom heltalsprogrammet då kan vara obegränsat eller sakna lösning.