De Branch-and-Bound methode

De Branch-and-Bound methode Een eigenschap van het ILP probleem is dat er meestal maar een eindig aantal mogelijke oplossingen toegelaten zijn, of op zijn slechtst zijn de oplossingen aftelbaar (eventueel oneindig). In het bijzonder zijn er voor een 0-1 ILP met n binaire variabelen hooguit 2n mogelijke toegelaten toepassingen. Dus 1024 bij 10 binaire variabelen, > 1.000.000 bij 20 binaire variabelen en > 1040 bij 150 variabelen. Gegeven dat de snelste huidige computers 1012 operaties per seconde kunnen uitvoeren, betekent dat alle mogelijke oplossingen nagaan en de beste selecteren 1028 seconden duurt wat aardig in de buurt komt van de laatste schattingen omtrent het bestaan van het universum. Daar kunnen we dus niet op wachten. Het kan bij sommige ILP problemen nog een optie zijn om te doen alsof er helemaal geen geheeltalligheidsrestricties zijn, het probleem op te lossen als een gewoon LP-probleem (dit heet de zogenaamde LP-relaxatie van het ILP probleem) en achteraf de oplossing af te ronden. Meestal verliezen we dan de garantie dat dit de optimale oplossing geeft voor het ILP probleem. Bij de meeste 0-1 ILP problemen is het echter verre van duidelijk hoe af te ronden tot een toegelaten oplossing: Stel dat in een optimale oplossing van de LP-relaxatie de waarden van alle variabelen kleiner dan 1/2 zijn dan is direct afronden geen optie want alles zou naar 0 afgerond worden en dat geeft een niet-toegelaten oplossing. Slechte afronding bij het 0-1 Knapzak probleem. Er bestaat een theorie dat ILP een probleem is waarvoor geen echt efficient algoritme bestaat. We zullen een algoritme bestuderen dat op een impliciete manier alle mogelijke oplossingen afgaat en de beste selecteert. Dit algoritme heeft het nadeel dat in het algemeen slechts kleinere probleeminstanties opgelost kunnen worden. Er zijn ook algoritmen toegesneden op het specifieke ILP probleem die sneller werken. Voor veel problemen geven deze algoritmen niet pers´e de optimale oplossing maar een benadering. Deze aspecten zullen buiten dit college blijven. A general purpose solution method for ILP is Branch-and-Bound (B&B). This method enumerates all possible feasible solutions of an ILP-problem instance in a smart way, trying to save as much as possible. It does so by dividing the original problem into sub-problems by imposing mutually excluding restrictions on values of some of the decision variables. The method 1

will be explained at the hand of a 0-1 ILP problem instance, extracted from [Hillier and Lieberman] Chapter 11. Remember that we argued that a 0-1 ILP instance with n variables has 2n possible solutions. We will see that B&B tries to avoid evaluating all of them.

Branch-and-Bound for 0-1 ILP Consider the following problem instance: max Z = s.t.

9x1 + 5x2 + 6x3 6x1 + 3x2 + 5x3 + x3 −x1 + x3 − x2

+ 4x4 + 2x4 ≤ 10 + x4 ≤ 1 ≤ 0 + x4 ≤ 0

x1 , x2 , x3 , x4 ∈ {0, 1}.

The LP-relaxation of this problem obtained by relaxing the constraints xi ∈ {0, 1}, i = 1, . . . , 4, to 0 ≤ xi ≤ 1, i = 1, . . . , 4, appears to have an optimal solution (x1 , x2 , x3 , x4 ) = ( 56 , 1, 0, 1) with value Z0LP = 16 12 . Lemma 0.1 Een optimale oplossing van de LP-relaxatie is altijd beter dan de optimale oplossing van het bijbehorende ILP-probleem. Dus in geval van maximaliseren zegt dit lemma dat de optimale waarde van de LP-relaxatie altijd een bovengrens geeft op de optimale waarde van het ILP-probleem. Dit is wel logisch als we even andersom denken, namelijk dat de ILP-formulering uit de LP-relaxatie wordt verkregen door de extra restrictie toe te voegen dat alle variabelen geheeltallig moeten zijn. Een probleem zal nooit een betere oplossing krijgen door extra restricties toe te voegen. In het gunstigste geval blijken die extra restricties geen invloed op de optimale oplossing te hebben. Omdat het ILP-probleem nooit een betere oplossing kan hebben dan de LPrelaxatie, geldt ook het volgende lemma. 2

Lemma 0.2 Als de LP-relaxatie een geheeltallige optimale oplossing heeft, dan is dat ook de optimale oplossing van het ILP-probleem. Thus, we know that no feasible solution of the original integer problem will have a value higher than 16 12 . Denoting the optimal value of the ILP problem by Z I we have Z I ≤ 16 12 . Actually we even have Z I ≤ 16 since the objective coefficients are all integer, whence any integer solution should have an integer objective value. In this way we have bounded the optimal value from above. Clearly, the optimal solution of the LP-relaxation is not all-integer. Now we divide the problem into two sub-problems, while enforcing one of the variables into an integer value. I.e.: in sub-problem 1 we enforce x1 = 0, whereas in sub-problem 2 we enforce x1 = 1. This is the way we do our first branching. Thus Sub-problem 1 becomes the original problem with the extra constraint x1 = 0 and Sub-problem 2 becomes the original problem with the extra constraint x1 = 1. In principle we could remove x1 from these sub-problems. E.g. this would give for Sub-problem 2: max Z = s.t.

5x2 + 6x3 3x2 + 5x3 + x3 x3 −x2

+ 4x4 + 9 + 2x4 ≤ 4 + x4 ≤ 1 ≤ 1 + x4 ≤ 0

x2 , x3 , x4 ∈ {0, 1}.

It is left to the student to formulate Sub-problem 1 without x1 . The optimal solution of the LP-relaxation of Sub-problem 1 is (x1 , x2 , x3 , x4 ) = (0, 1, 0, 1) with value Z1LP = 9. The optimal solution of the LP-relaxation of Sub-problem 2 is (x1 , x2 , x3 , x4 ) = (1, 54 , 0, 45 ) with value Z2LP = 16 15 . The calculations are represented in a so-called branch-and-bound search tree. The root-node (mother-node), called node 0, represents the original problem. 3

From this node there are two edges leading to the two (children) nodes, nodes 1 and 2, representing Sub-problems 1 and 2, respectively. The edges are labelled according to the branching they imply. Thus the edge between node 0 and node 1 is labelled x1 = 0, and the other edge is labelled x1 = 1. In the root-node we read the number 16 indicating an upper bound on the optimal value of the whole problem. In node 2 we read again 16, which indicates that once we prefix the value of x1 to 1 we cannot attain a solution with value higher than 16. In node 1 we read 9, indicating an upper bound of 9 on the value of any feasible solution of the problem with the property that x1 = 0. However, there is something special in node 1. The upper bound of 9 is attained in a solution that is integer: (x1 , x2 , x3 , x4 ) = (0, 1, 0, 1). Thus, according to Lemma 0.2 we have already found the best possible solution given that x1 = 0. Hence, it does not make any sense to further consider sub-problems that have x1 = 0. We say that we prune the search tree in this node. It also give us the value of a feasible solution, which so far is the best feasible solution. We have encountered one pruning criterion, based on which we can discard parts of the tree. We list all pruning criteria below. They are very logical once thinking about them a little bit and are based on Lemmas 0.2 and 0.1. The B&B search tree is pruned in a node if (P1) The upper bound on the solution value of the sub-problem in that node is attained by a feasible integer solution; (P2) The upper bound on the solution value of the sub-problem in that node is lower than or equal to the value of the best feasible (integer) solution found so far; (P3) The sub-problem in that node is infeasible. Continuing with the example only node 2 remains to be branched from. We define Sub-problems 2.1 and 2.2 by adding, respectively, the constraints x2 = 0 and x2 = 1 to Sub-problem 2. The optimal solution of Sub-problem 2.1 is (x1 , x2 , x3 , x4 ) = (1, 0, 45 , 0) with LP = 13 45 . value Z2.1 The optimal solution of Sub-problem 2.2 is (x1 , x2 , x3 , x4 ) = (1, 1, 0, 21 ) with LP = 16. value Z2.2 4

None of these two nodes can be pruned. We have to choose which of the two nodes to branch from. There is no optimal criterion to guide this choice. Usually, one takes the node with highest potential, i.e. the one with the highest upper bound. Thus, we choose to branch from the node corresponding to Sub-problem 2.2, by setting x3 = 0 and x3 = 1, leading to Sub-problems 2.2.1 and 2.2.2, respectively. The optimal solution of Sub-problem 2.2.1 is (x1 , x2 , x3 , x4 ) = (1, 1, 0, 21 ) with LP value Z2.2.1 = 16. For Sub-problem 2.2.2 there is no feasible solution. Thus, this node can be pruned by criterion P3. There are still three nodes that are active: nodes (sub-problems) 1, 2.1, and 2.2.1. The first one has been pruned for further investigation. The second and the third one are still open. Since the 2.2.1 has the higher upper bound we branch from that one, by setting x4 = 0 and x4 = 1, leading to Sub-problems 2.2.1.1 and 2.2.1.2, respectively The optimal solution of Sub-problem 2.2.1.1 is (x1 , x2 , x3 , x4 ) = (1, 1, 0, 0) LP with value Z2.2.1.1 = 14. Sub-problem 2.2.1.2 is infeasible. Of course, the optimal solution of Sub-problem 2.2.1.1 is attained in an integer point. It gives a solution with value 14, the best solution found so far. First of all this means that Node 1, can be discarded. Secondly, Node 2.1 can be pruned on basis of criterion P2 since the upper bound of 13 is lower than 14. Since we don’t have any further active nodes, the problem is solved and the optimal solution value is 14. In the example the branching was done based on the values of the upper bounds in the nodes. This is not necessarily the best strategy. The two most extreme branching strategies are depth-first search (DFS) and breadth-first search (BFS). DFS has the advantages of giving a feasible solution quickly, which can be used for pruning the tree, and it requires little computer space for intermediate storing of unpruned nodes. With respect to bounding it is always better to try to achieve the best possible bounds. In maximization, the best upper bounds are not necessarily achieved through LP-relaxations. One could often improve enormously on this bound by adding cuts (see later), or by considering other relaxations (see later as well). For finding good lower bounds we may rely on good approximation 5

algorithms. Both in computing lower- and upper bounds there is always the trade-off between quality and time. Within the context of B&B the aim of good bounds is to save computing time, and therefore the time used for computation of the bounds should not be higher than the time saved by having these stronger bounds available. Tuning the B&B method to the specific practical applications is a matter of craftmanship, attainable through working a lot with the technique.

Branch-and-bound voor het knapzak probleem Het 0-1 Knapzak probleem was het probleem van het selecteren van items, waarbij ieder item j een gewicht aj heeft en een waarde cj . De knapzak heeft gewichtscapaciteit b. Gevraagd wordt een selectie te maken met maximale totale waarde, waarvan het totale gewicht b niet overschrijdt. Met behulp van de 0-1 beslissingsvariabelen xj , waarbij xj = 1 aangeeft dat item j geselecteerd wordt en xj = 0 dat item j niet geselecteerd wordt, kunnen we het volgende 0-1 ILP model opstellen: Pn max cj xj Pj=1 n s.t. j=1 aj xj ≤ b, 0 ≤ xj ≤ 1, xj ∈ ZZ , j = 1, 2, . . . , n. De LP-relaxatie van dit probleem wordt verkregen door de restricties xj ∈ ZZ te laten vervallen: Pn max cj xj Pj=1 n s.t. j=1 aj xj ≤ b, 0 ≤ xj ≤ 1, j = 1, 2, . . . , n. De LP-relaxatie heeft de plezierige eigenschap dat het heel gemakkelijk op te lossen is zonder daarvoor het LP-probleem met behulp van LP-methoden op te lossen. Om de LP-relaxatie op te lossen moeten we ons bedenken dat de capaciteit volledig benut zal worden, omdat we eventueel een item slechts gedeeltelijk mee mogen nemen. Het beste is dus om items te selecteren die een zo hoog mogelijke waarde per eenheid gewicht geven. Deze twee observaties geven precies het algoritme wat de LP-relaxatie oplost: Greedy Algoritme: Orden de items op afnemende ratio cj /aj in een lijst en voeg de items in die volgorde aan de selectie toe zolang dat past. Voor 6

het eerste item dat niet meer past wordt bepaald welke fractie van dit item nog wel meegenomen kan worden en deze fractie wordt geselecteerd waarmee de capaciteit b bereikt wordt. Laten we dit illustreren aan de hand van het volgende voorbeeld. Gegeven een verzameling van 5 items met item 1 2 3 4 5 cj 9 7 6 5 7 aj 4 3 3 2 4 De capaciteit van de knapzak b = 11. Om de LP-relaxatie van de ILP-formulering van dit knapzak problem op te lossen, moeten we eerst de items ordenen op afnemende ratio cj /aj . Dit geeft item 4 2 1 3 5 cj 5 7 9 6 7 aj 2 3 4 3 4 Om de oplossing voor de LP-relaxatie te bepalen gaan we deze lijst af: Item 4 past en wordt opgenomen, dus x4 = 1. Dit geeft restcapaciteit 11 − 2 = 9. Dus wordt item 2 ook opgenomen, x2 = 1 wat restcapaciteit 9 − 3 = 6 geeft. Dus wordt item 1 ook opgenomen, x1 = 1 wat restcapaciteit 6 − 4 = 2 geeft. We zien dat item 3, het vierde item in de geordende lijst, niet meer in zijn geheel opgenomen kan worden want het heeft gewicht 3. Dit item nemen we dan dus slechts gedeeltelijk mee. Dat is niet toegelaten voor het ILP probleem maar wel voor de LP-relaxatie. We nemen dit item dus voor 2/3 op, x3 = 2/3. De overige items worden niet geselecteerd, x5 = 0. De totale waarde is dan Z LP = 5 + 7 + 9 + 6 · 23 = 25. Maar op een simpele manier kunnen we hier nog meer informatie uithalen. Namelijk door de gevonden oplossing naar beneden af te ronden krijgen we een oplossing die waarschijnlijk niet optimaal, maar wel toegelaten is voor het oorspronkelijke geheeltallige probleem: x4 = 1, x2 = 1, x1 = 1, x3 = 0, x5 = 0 met waarde Z = 21. Dit vormt een mooie start voor de Branch-and-Bound methode om het knapzak probleem op te lossen. We weten dus uit de eerste zoekknoop, het 7

probleem wat we juist opgelost hebben, dat de optimale oplossing een waarde zal hebben van hooguit 25. Maar in dit geval hebben we met de afronding een toegelaten oplossing waarmee we iedere knoop kunnen wegsnoeien, die een waarde krijgt lager dan 21. Dit voorbeeld probleem laat zien dat we niet altijd een heel korte Branchand-Bound boom hebben, maar soms heel veel knopen uit moeten zoeken. We branchen op x3 en cre¨eren twee subproblemen. Subprobleem 1 met x3 = 0: max 9x1 + 7x2 + 5x4 + 7x5 s.t. 4x1 + 3x2 + 2x4 + 4x5 ≤ 11, 0 ≤ xj ≤ 1, xj ∈ ZZ , j = 1, 2, 4, 5 en Subprobleem 2 met x3 = 1: max 9x1 + 7x2 + 5x4 + 7x5 + 6 s.t. 4x1 + 3x2 + 2x4 + 4x5 ≤ 8, 0 ≤ xj ≤ 1, xj ∈ ZZ , j = 1, 2, 4, 5 Gebruikmakend van de oplossingsmethode zoals hierboven beschreven lossen we de LP-relaxaties van deze twee subproblemen op: 2 LP − Oplossing Subprobleem 1 : x4 = 1, x2 = 1, x1 = 1, x5 = , x3 = 0 4 1 LP met waarde Z = 24 . 2 3 LP − Oplossing Subprobleem 2 : x4 = 1, x2 = 1, x1 = , x5 = 0, x3 = 1 4 3 met waarde Z LP = 24 . 4 Dit geeft bovengrens 24 voor Subprobleem 1 en 24 voor Subprobleem 2. De afronding van de oplossing van Subprobleem 1 geeft een toegelaten oplossing x4 = 1, x2 = 1, x1 = 1, x5 = 0, x2 = 0 met waarde 21. De afronding van de oplossing van Subprobleem 2 geeft een toegelaten oplossing x4 = 1, x2 = , x4 = 0, x5 = 0, x1 = 0, x2 = 1 met waarde 45. 1, x1 = 0 10 13 8

We zullen eerst Subprobleem 1 verder onderzoeken door te branchen op x5 . Dit geeft Subprobleem 1.1 met x5 = 0 max 9x1 + 7x2 + 5x4 s.t. 4x1 + 3x2 + 2x4 ≤ 11, 0 ≤ xj ≤ 1, xj ∈ ZZ , j = 1, 2, 4 en Subprobleem 1.2 met x5 = 1 max 9x1 + 7x2 + 5x4 + 7 s.t. 4x1 + 3x2 + 2x4 ≤ 7, 0 ≤ xj ≤ 1, xj ∈ ZZ , j = 1, 2, 4 Oplossingen van de LP-relaxaties worden: LP − Oplossing Subprobleem 1.1 : x4 = 1, x2 = 1, x1 = 1, x3 = 0, x5 = 0 met waarde Z LP = 21. 2 LP − Oplossing Subprobleem 1.2 : x4 = 1, x2 = 1, x1 = , x3 = 0, x5 = 1, 4 1 met waarde Z LP = 23 . 2 Er is een optimale oplossing gevonden van de LP-relaxatie van Subprobleem 1.1 die geheeltallig is. De best gevonden oplossing tot nu toe blijft waarde 21 hebben. We zullen Subprobleem 1.2 onderzoeken door te branchen op x1 . Dit geeft Subprobleem 1.2.1 met x1 = 0 max 7x2 + 5x4 + 7 s.t. 3x2 + 2x4 ≤ 7, 0 ≤ xj ≤ 1, xj ∈ ZZ , j = 2, 4 en Subprobleem 1.2.2 met x1 = 1 max 7x2 + 5x4 + 16 s.t. 3x2 + 2x4 ≤ 3, 0 ≤ xj ≤ 1, xj ∈ ZZ , j = 2, 4 9

Oplossingen van de LP-relaxaties worden: LP − Oplossing Subprobleem 1.2.1 : x4 = 1, x2 = 1, x1 = 0, x3 = 0, x5 = 1 met waarde Z LP = 19. 1 LP − Oplossing Subprobleem 1.2.2 : x4 = 1, x2 = , x1 = 1, x3 = 0, x5 = 1 3 1 met waarde Z LP = 23 . 3 Subprobleem 1.2.1. kan weer gesnoeid worden vanwege een geheeltallige oplossing. De waarde is slechter dan de beste tot nu toe gevonden. Bovengrens voor Subprobleem 1.2.2 is 23. De afronding van de oplossing van Subprobleem 1.2.2 geeft een toegelaten oplossing x4 = 1, x2 = 0, x1 = 1, x3 = 0, x5 = 1 met waarde 21. Nu doe ik nog de branching van Subprobleem 1.2.2 en branch ik op x2 . Dit geeft Subprobleem 1.2.1.1 met x2 = 0 max 5x4 + 16 s.t. 2x4 ≤ 3, 0 ≤ xj ≤ 1, xj ∈ ZZ , j = 4 en Subprobleem 1.2.1.2 met x2 = 1 max 5x4 + 23 s.t. 2x4 ≤ 0, 0 ≤ xj ≤ 1, xj ∈ ZZ , j = 1, 2, 4 Beiden hebben een geheeltallige oplossing en kunnen dus gesnoeid worden. Subprobleem 1.2.1.1 heeft oplossing x4 = 1, x2 = 0, x1 = 1, x3 = 0, x5 = 1 met waarde Z LP = 21. Subprobleem 1.2.1.2 heeft oplossing x4 = 0, x2 = 1, x1 = 1, x3 = 0, x5 = 1 met waarde Z LP = 23. Dit is de best gevonden waarde waarmee we een ondergrens van 23 hebben nu. Helaas is dat niet voldoende om het enige open subprobleem te kunnen snoeien. We moeten Subprobleem 2 dus onderzoeken. Daartoe branchen we op x1 . Ik zal stoppen met de subproblemen uit te schrijven en verwacht ook niet van de studenten op het tentamen dat alle subproblemen uitgeschreven 10

worden. Hooguit zal ik expliciet vragen er een of twee uit te schrijven. Dus Subprobleem 2.1 heeft x1 = 0 en x3 = 1 en restcapaciteit van de knapzak is 8. Dus de oplossing van dit probleem wordt x4 = 1, x2 = 1, x5 = 34 , x1 = 0, x3 = 1 met waarde Z LP = 23 14 . Dit kan gesnoeid worden op het 2de snoeicriterium: de bovengrens voor deze knoop is 23, de afronding van 23 41 , en dit is gelijk aan de waade van de beste reeds gevonden oplossing. Subprobleem 2.2 heeft x1 = 1 en x3 = 1 en restcapaciteit van de knapzak is 4. Dus de LP-oplossing van dit probleem wordt x4 = 1, x2 = 23 , x5 = 0, x1 = 1, x3 = 1 met waarde Z LP = 24 23 . De afronding van de oplossing heeft een waarde van 18. Wederom kan deze knoop niet gesnoeid worden. We branchen op x2 . Subprobleem 2.2.1 heeft dan x2 = 0 en x1 = 1 en x3 = 1 en restcapaciteit van de knapzak 4. De LP-oplossing van dit probleem wordt x4 = 1, x5 = 23 , x2 = 0, x1 = 1, x3 = 1 met waarde Z LP = 23 12 . Dit kan gesnoeid worden op het 2de snoeicriterium: de bovengrens voor deze knoop is 23, de afronding van 23 12 , en dit is gelijk aan de waade van de beste reeds gevonden oplossing. Subprobleem 2.2.2 heeft dan x2 = 1 en x1 = 1 en x3 = 1 en restcapaciteit van de knapzak 1. De LP-oplossing van dit probleem wordt x4 = 21 , x5 = 0, x2 = 1, x1 = 1, x3 = 1 met waarde Z LP = 24 21 . De afronding van de oplossing heeft een waarde van 18. Wederom kan deze knoop niet gesnoeid worden. Om Subprobleem 2.2.2 verder te onderzoeken branchen we nog op x4 . Subprobleem 2.2.2.1 heeft dan x4 = 0 en x2 = 1 en x1 = 1 en x3 = 1 en restcapaciteit van de knapzak 1. De LP-oplossing van dit probleem wordt x5 = 14 , x4 = 0, x2 = 1, x1 = 1, x3 = 1 met waarde Z LP = 23 43 . Dit kan weer gesnoeid worden op het 2de snoeicriterium. Subprobleem 2.2.2.2 heeft dan x4 = 1 en x2 = 1 en x1 = 1 en x3 = 1 en dit is niet toegelaten en kan dus gesnoeid worden op grond van snoeicriterium 3. Aangezien geen knopen meer open zijn, kunnen we concluderen dat we de optimale oplossing gevonden hebben en deze is dus x4 = 0, x2 = 1, x1 = 1, x3 = 0, x5 = 1 met waarde Z LP = 23. 11

0-1 Knapzak Opgaven K1: Los het volgende 0-1 Knapzak probleem op met behulp van de Branchand-Bound methode. max Z = 7x1 + 5x2 + 6x3 + 8x4 + 2x5 s.t. 4x1 + 3x2 + 4x3 + 5x4 + 2x5 ≤ 11 x1 , x2 , x3 , x4 , x5 ∈ {0, 1} K2: Los het volgende 0-1 Knapzak probleem op met behulp van de Branchand-Bound methode. max Z = 13x1 + 7x2 + 2x3 + 6x4 + 5x5 + 4x6 + 11x7 s.t. 5x1 + 2x2 + 4x3 + 3x4 + x5 + 2x6 + 3x7 ≤ 10 x1 , x2 , x3 , x4 , x5 , x6 , x7 ∈ {0, 1} K3: Los het volgende 0-1 Knapzak probleem op met behulp van de Branchand-Bound methode, waarbij de nutten en de gewichten van 6 items gegeven zijn door item 1 2 3 4 5 6 cj 26 30 25 20 16 15 aj 19 16 13 11 9 7 De capaciteit van de knapzak b = 33. Bij deze opgave wordt duidelijk dat de Branch-and-Bound soms heel veel knopen moet berekenen.

12