Sandbox voor gehele programmering
Los een klein geheel lineair programma op met exact branch-and-bound en bekijk elke zoeknode. Het beste punt wordt alleen bewezen optimaal genoemd wanneer de volledige boom is doorzocht.
Programma’s zijn beperkt tot 4.000 tekens en 40 regels, 8 variabelen en 8 beperkingen met twee of meer variabelen; de nodelimiet is 1 tot 5.000 en de zoekopdracht stopt ook na 3.000.000 stappen van exacte rekenkunde. Alles wordt op je apparaat op de achtergrond berekend, met een limiet van 15 seconden. Downloads: een JSON-rapport en een CSV met nodes. Eerste regel: maximize of minimize en het doel. Daarna één beperking per regel. Maximaal 4.000 tekens. Controleer de instellingen voordat je de tool uitvoert.
Je resultaat
Sandbox voor gehele programmering
- Schrijf het doel op de eerste regel, zoals maximize 5x + 4y.
- Voer één beperking per regel in, grenzen zoals x, y >= 0 en optionele regels zoals integer x of binary z.
- Stel de nodelimiet in en start de zoekopdracht.
- Bekijk de status, de incumbent, de beste grens en het verschil. Download daarna het JSON-rapport of de CSV met nodes.
Wat je kunt verwachten
Programma’s zijn beperkt tot 4.000 tekens en 40 regels, 8 variabelen en 8 beperkingen met twee of meer variabelen; de nodelimiet is 1 tot 5.000 en de zoekopdracht stopt ook na 3.000.000 stappen van exacte rekenkunde. Alles wordt op je apparaat op de achtergrond berekend, met een limiet van 15 seconden. Downloads: een JSON-rapport en een CSV met nodes.
Branch-and-bound
Elke node lost de lineaire relaxatie exact op met de simplex-methode. Een fractionele gehele variabele wordt in twee takken gesplitst: x <= floor en x >= ceiling. Nodes worden geschrapt wanneer hun relaxatie niet uitvoerbaar is of het beste gevonden gehele punt niet kan verbeteren. Methode: Wolsey, Integer Programming, 2e editie, hoofdstuk 7 (2020).
Wat bewezen betekent
Wanneer elke node exact is opgelost of geschrapt met een exacte grens, is de incumbent bewezen optimaal of is het probleem bewezen onuitvoerbaar. Als de nodelimiet of staplimiet de zoekopdracht eerder stopt, is de incumbent alleen het beste punt dat tot dan is gevonden; het rapport geeft de beste grens en het verschil ertussen.
Invoerregels
Variabelen zijn geheel, tenzij je enkele opgeeft met integer x, y; de overige variabelen zijn dan continu. Beperkingen met één variabele worden grenzen. Een onbegrensde relaxatie stopt de zoekopdracht, omdat het gehele programma dan onbegrensd of niet uitvoerbaar kan zijn.