Branch and Win: OR tree search algorithms for solving combinatorial optimisation problems

Elec onic e sion o an a icle published as [Top. Re is a de la Sociedad de Es adís ica e In es igación Ope a i a, 2004, Vol. 12, No. 1, p. 169-191.] © [copy igh Sp inge -Ve lag] 1 B anch and Win: OR ee sea ch algo i hms o sol ing combina o ial op imisa ion p oblems Ra ael Pas o ∗, Albe Co ominas Depa men o Business Adminis a ion. Resea ch Ins i u e IOC. School o Indus ial Enginee ing o Ba celona Technology Uni e si y o Ca alonia A da. Diagonal, 647, 7ª plan a 08028 Ba celona (Spain) E-mail add ess: {pas o /co ominas}@ioc.upc.es Abs ac Cu en ly, mos combina o ial op imisa ion p oblems ha e o be sol ed, i he op imum solu ion is sough , using gene al echniques o explo e he space o easible solu ions and, mo e speci ically, h ough explo a o y enume a i e p ocedu es in ees and sea ch g aphs. We p opose B anch and Win, a gene al o mula ion o unde s anding and syn hesising he di e en ee sea ch p ocedu es ha ha e been p esen ed in he li e a u e o ope a ions esea ch as well as in ha o a i icial in elligence. Se e al gene al ideas a e also p esen ed, whose applica ion allows designing new hyb id sea ch algo i hms, in o de o implemen he p ocedu e. Key Wo ds: Combina o ial op imiza ion, b anch and bound, a i icial in elligence. AMS subjec classi ica ion: 90C27, 90C57, 68T20. 1. INTRODUCTION As i is known, i is e y di icul o sol e op imally mos o he combina o ial op imisa ion p oblems due o hei in insic complexi y. A p esen , hough speci ic p ocedu es exis o sol e some speci ic combina o ial op imisa ion p oblems, mos o hem ha e o be sol ed employing gene al echniques o explo e he space o easible solu ions, and, mo e speci ically, h ough explo a o y enume a i e p ocedu es in ees and g aphs o s a es (in he enume a i e p ocedu es, all solu ions a e gene a ed and enume a ed, explici ly o implici ly). We analyse he explo a o y enume a i e p ocedu es in OR ee ep esen a ions -which ha e been exposed bo h in he ope a ions esea ch and a i icial in elligence (AI) li e a u es- and we p opose a new me a-algo i hm ha we ha e called B anch and Win: a new gene al o mula ion ha includes all o hem. B anch and Win allows o a be e unde s anding o ee sea ch algo i hms o combina o ial op imiza ion p oblems, syn hesizes he di e en ee sea ch p ocedu es ha ha e been p esen ed in he li e a u e, assembles he di e en elemen s ha a e pa o hese sea ch p ocedu es and uses hem dynamically in he ee and p o ides a means o de eloping new sea ch s a egies and p ocedu es such as hyb idiza ions o sea ch algo i hms wi h local sea ch and me aheu is ics. ∗ Co esponding au ho : Ra ael Pas o E-mail add ess: pas o @ioc.upc.es 2 The es o he pape con inues as ollow. In Sec ion 2 he esolu ion enume a i e p ocedu es and he exis en gene al o mula ions a e analysed. B anch and Win is o mula ed and desc ibed in Sec ion 3. In Sec ion 4 we claim he in eg a ing cha ac e o B anch and Win. Se e al gene al ideas ha allow designing new hyb id sea ch s a egies a e enume a ed in Sec ion 5. Finally, some conclusions a e discussed in Sec ion 6. 2. ENUMERATIVE SOLUTION PROCEDURES A g ea numbe o enume a i e sea ch p ocedu es o sol ing combina o ial op imisa ion p oblems ha e appea ed in he ope a ions esea ch li e a u e as well as in he AI li e a u e o e he las ew decades. Mos o hese sea ch app oaches ha e been desc ibed by di e en au ho s and some imes he de ini ions p esen ed a e no speci ic enough o know whe he hey e e o a selec ion s a egy o o a pa icula algo i hm and, in his case, wha o he cha ac e is ics a e included in he sea ch algo i hm. Fo example, he dep h i s sea ch, which always explo es a child node o he node mos ecen ly sepa a ed, exis s. Bu an app oach like he p e ious one has also been gi en he name o dep h i s sea ch which, mo eo e , inco po a es a p ocedu e o g ouping equi alen s a es. Wi h he aim o uni ying hese echniques, gene al o mula ions ha e also been p esen ed. Bu some imes he e a e aspec s ha ha e no been su icien ly aken in o accoun om a p ac ical poin o iew. Among o he s: comple eness o he co esponding pa ial solu ion, he s a e o he explo a ion g aph ( o al numbe o nodes gene a ed, amoun o memo y used, e c.), he en i onmen condi ions in which he p oblem is sol ed (maximum allowed compu ing ime, maximum a ailable memo y, access ime o he medium -RAM, ha d disk, e c.- on which a node can be s o ed, e c.). 2.1. Explo a o y enume a i e p ocedu es We p esen a b ie in oduc ion o he ela ionships be ween di e se explo a o y enume a i e p ocedu es o sol ing combina o ial op imisa ion p oblems. Mos o he enume a i e p ocedu es ha e been inc easingly employed bo h in ope a ions esea ch and in AI o sol e eal p oblems. Some imes a p ocedu e has been gi en di e en names being he same echnique ( o example, he dep h i s p ocedu e has been called se e al di e en ways: dep h i s sea ch, DFS, linea sea ch, single b anch sea ch, LIFO sea ch and e ical sea ch). And some p ocedu es p esen so many simila i ies ha hey could be conside ed edundan : in Ba and Feigenbaum (1981) and Kuma and Kanal (1983b), b anch and bound p ocedu es (B&B), dynamic p og amming echniques (DP) -in his wo k, DP is used o e e o ini e-de e minis ic dynamic p og amming echniques- and he heu is ic sea ch p ocedu e A* -in oduced by Ha e al (1968)- a e said o be e y simila , al hough B&B and DP ha e been used in ope a ions esea ch and A* in AI (e.g., acco ding o Ba and Feigenbaum (1981), A* is a bes i s sea ch wi h an e alua ion unc ion o med by he sum o he minimal cos associa ed wi h eaching he node n om he oo , plus a heu is ic es ima e o he 3 minimal cos o eaching an objec i e node om he node n). Fu he mo e he ela ionships be ween hese classes o p ocedu es ha e been a he con o e sial. Fo example, Nilsson (1980) de ines he algo i hm A as a p ocedu e A* ha canno gua an ee he op imali y o he solu ion. While many o he au ho s (Ba and Feigenbaum (1981), Ko (1990), Rich and Knigh (1991)) conside ha he e only exis s a p ocedu e (A*) and i may o may no gua an ee he op imali y o he solu ion depending on he ul illmen o no o he admissibili y p ope y. In his case he e also exis pa icula de ini ions o A*: Rich and Knigh (1991) inco po a e a p ocedu e o g ouping equi alen s a es and conside ha he cos o a pa h is equal o i s numbe o s ages. Pea l (1984) conside s A* as a pa icula Z* (a special bes i s sea ch desc ibed in Pea l (1984)). As i is discussed by se e al au ho s (Pea l (1984) and G eenbe g (1996) among o he s), i he selec ion s a egy o he nex node o be explo ed consis s in minimising he dep h o he node, he p ocedu e A* is equi alen o ha o he b ead h i s sea ch; and, i i consis s in minimising minus he dep h o he node, he p ocedu e A* is equi alen o ha o he dep h i s sea ch (Pea l (1984)). Fo Nilsson (1971), Ba and Feigenbaum (1981) and Pea l (1984) A* is he smalles cos i s sea ch p ocedu e i he e is no heu is ic in o ma ion. On he o he hand, Rich and Knigh (1991) discuss a la ge numbe o possibili ies. Acco ding o G eenbe g (1996), b anch and bound o in ege p og amming is a pa icula case o A* in ope a ions esea ch, whe e he e alua ion unc ion akes he alue o he objec i e unc ion o he linea elaxa ion o he node (wi hou commen ing on he main cha ac e is ic o B&B: he p uning by a bounding es ). Ba and Feigenbaum (1981) name o de ed s a e space sea ch o he bes i s sea ch and speci y ha he b ead h i s , he uni o m cos and he dep h i s a e speci ic cases o his. On he o he hand, Nilsson (1971) and Pea l (1984) speci ically de ine he smalles cos i s sea ch (uni o m cos sea ch o cheapes i s s a egy), while mos o he au ho s conside i a special case o he bes i s sea ch. And Pea l (1984) di e ences be ween whe he a easible solu ion is only looked o (bes i s sea ch s a egy) and whe he an op imal solu ion is looked o (algo i hm ha is named bes i s sea ch* by Pea l). The ela ionships be ween B&B and DP ha e also been a he con o e sial. While some au ho s claim ha DP is a mo e gene al echnique han B&B, o he s conside ha i is exac ly he opposi e. The e a e also hose who claim ha some DP echniques can be s a ed in a amewo k o B&B, al hough B&B app oaches can also be p esen ed as DP p ocedu es wi h a bounding es -see, e.g., Ma s en and Mo in (1978), Kuma and Kanal (1983b) and Iba aki (1988)-. I is also necessa y o emphasise he exis ence o au ho s ha seem o ha e he ela ionships be ween hese classes o p ocedu es clea e : “A class o algo i hms simila o A* is used in ope a ions esea ch unde he name o b anch-and-bound algo i hms”, Ba and Feigenbaum (1981), p. 64. The si ua ion p e iously desc ibed shows ha he scene o sea ch p ocedu es o sol ing combina o ial op imisa ion p oblems is a he uns uc u ed, dispe sed and insu icien ly o malized. On he o he hand, in he las yea s new sea ch p ocedu es ha e been 4 de ined -b anch & p ice (e.g., Sa elsbe gh (1997)), b anch & cu (e.g., Ho man and Padbe g (1993)), b anch & educe (e.g., Ryoo and Sahinidis (1996)), b anch & peg (Goldengo in e al (2004)), e c.- ha can be in eg a ed in well-known amewo ks, as well as o he sea ch echniques as cons ain s p opaga ion (see, e.g., Ha alick and Ellio (1980) and B ails o d e al (1999)). This can speed up he de elopmen o new p ocedu es, new names o new hyb id echniques, s ill complica ing he cu en scene mo e. In Pas o (1999) and Pas o and Co ominas (2000) a wide su ey o enume a i e sea ch p ocedu es o sol ing combina o ial op imisa ion p oblems is p esen ed. In hese wo ks, he ela ionships, de iciencies and simila i ies be ween he enume a i e p ocedu es ela ed in he ope a ions esea ch li e a u e as well as in AI li e a u e a e s udied and analysed; and he ollowing conclusions a e ob ained: • The e a e impo an elemen s ha ha e no been su icien ly aken in o accoun om a p ac ical poin o iew. Fo ins ance: o al numbe o gene a ed nodes, amoun o memo y used, maximum allowed compu ing ime, maximum a ailable memo y. • Dispe sion, con usion and e en duplici y exis in he de ini ions o he p ocedu es and in he e minology used. Pa ly his is due o he ac ha hese echniques ha e been used bo h in ope a ions esea ch and in AI. • The enume a i e sea ch p ocedu es ha e go di e se common elemen s whose speci ica ion allows o ob ain hem. • As some au ho s p esen , some sea ch p ocedu es de i e om o he s; bu hese de i a ions could be mo e gene al. • In he ex eme case, an enume a i e p ocedu e would gene a e he whole s a e- sea ch, being e y ine icien . To educe he space o s a es h ee gene al educ ion ac ics exis : elimina ion o domina ed s a es, p uning o nodes and de ec ion o emp y nodes. • The consis ency echniques coming om AI can be embedded, as i is done in some p ocedu es, in b anch and bound amewo ks -see, e.g., Bockmay and Kaspe (1998), who p opose a common amewo k o cons ain p og amming and in ege p og amming called b anch and in e . This connec s he sea ch p ocedu es coming om bo h in es iga ion a eas. 2.2. Gene alized sea ch p ocedu es A gene al o mula ion whe eby all o hese p ocedu es can be iewed in a uni ied manne seems ad isable. This necessi y has al eady been de ec ed and di e se gene al sea ch schemas ha e al eady been p esen ed. Among all o hese, we conside ha some schemas a e mo e gene al and uni ying han o he s, and e en in some o maliza ion, as in Co êa (1995), some sea ch p ocedu es a e shown as speci ic cases o he p oposed gene al schema. We ha e s udied and analysed he ollowing e e ences: Co ominas and Companys (1977), Kuma and Kanal (1983a and 1983b), Nau e al (1984), Iba aki (1988), Tuy and Ho s (1988) –who p esen a gene al B&B scheme o global op imisa ion-, Helman (1989) and Co êa (1995). As a esul , he ollowing de iciencies (which a ec , in a g ea e o smalle deg ee, all o hem) can be enume a ed (Pas o (1999)): 5 • On some occasions he e minology ha is used is no e y common in ope a ions esea ch (especially in e e ences coming om AI). This has a nega i e impac on i s unde s anding and p ac ical applicabili y. • The used elemen s a e usually p esen ed wi h sca ce p ecision. • Many sea ch p ocedu es a e no conside ed, pa icula ly he mos ecen . • The selec ion s a egy o he nex node o explo e is usually s a ic. • The ollowing explo a ion elemen s a e no gene ally used: Re o mula ion and p e-p ocessing, in he o iginal p oblem as well as in he pa ial p oblems. Use o local op imisa ion echniques and local sea ch p ocedu es, in he pa ial p oblems and when a new easible solu ion is ob ained. Calcula ion o new supe io bounds (i we a e minimising) in he pa ial p oblems. Use o di e se bounding, e o mula ion and educ ion p ocedu es. The en i onmen condi ions in which he p oblem is sol ed (maximum allowed compu ing ime, maximum a ailable memo y, e c.) and he s a e o he explo a ion g aph. I is necessa y o emphasise ha hese gene al schemas ha e ep esen ed an impo an ad ance a ha momen , o s uc u ing and uni ying di e se pa icula sea ch p ocedu es. 3. BRANCH AND WIN: OR TREE SEARCH ALGORITHMS FOR SOLVING COMBINATORIAL OPTIMISATION PROBLEMS The conclusions shown in he p e ious Sec ion, p o ide e idence o he necessi y o designing a new gene al ealis ic p ocedu e wi h he usual e minology in ope a ions esea ch in o de o sol e combina o ial op imisa ion p oblems. To mee his necessi y we p opose a new me a-algo i hm ha we ha e called B anch and Win. I is necessa y o commen ha he nea es an eceden s o B anch and Win, which we ha e aken as s a ing poin , a e he gene al p ocedu es p esen ed in Companys (1975) and Co ominas and Companys (1977). 3.1. De ini ions * P oblem o be sol ed: We p opose a gene al de ini ion o a combina o ial op imisa ion p oblem, in which, a e de ining he alue o he in ege a iables, a p ocedu e exis s o ind an op imal solu ion o he emaining p oblem: [ ] ( ) ,OPT Z X T=  ( ) , X TS ∈ , whe e: S is he easible space inside he o al space o solu ions; X is a ec o o in ege bounded a iables; T is a ec o o con inuous a iables; and gi en X´ is possible o ob ain T´, which p o ides he op imal solu ion o he p oblem o X´. So one o he mo e impo an combina o ial op imisa ion p oblems is also included: mixed in ege linea p og amming. 6 The o iginal p oblem o be sol ed can be educed immedia ely o he ollowing ma hema ical p og am: [ ] ( ) M IN Z X= X EF ∈ ⊆, whe e: F is he ini e se o possible solu ions (usually he Ca esian p oduc o he domains o he a iables); E is he ini e se o easible solu ions; X is a solu ion; : E → κ, wi h κ an o de ed se (usually he in ege o he con inuous numbe s). * Node: Le : ℘(F) he se o subse s o F; N he se o na u al numbe s; and Si a subse o solu ions. We de ine a node Vi as ollows: Vi ∈ ℘(F) x N, he e o e, Vi = (Si, i). The na u al numbe is necessa y o iden i y he node, since he subse s o solu ions belonging o wo nodes may coincide. * Emp y node and e minal node: Vi is an emp y node ⇔ Si ∩ E = ∅. Vi is a e minal node ⇔ |Si| = 1. * B anching p ocedu e: Le M0 be a p imi i e b anching p ocedu e. M0 makes he elemen s o ℘(F) wi h ca dinali y ≥ 2 co espond wi h wo o mo e subse s o F. M0 sepa a es he subse s o F wi hou elimina ing any elemen om ℘(F). And he ollowing p ope ies a e ue: (1) Y ∈ M0(S) ⇒ Y ≠ S; (2) () {} 0 YM S∀∈ ∪ Y = S; and (3) ∀ Y, Z ∈ M0(S) ⇒ Y ⊆ Z. De ined M0, le M be a b anching p ocedu e. M is a co espondence ha associa es a subse o ( e minal o non- e minal) nodes o a non- e minal node: M consis s in applying a M0 p ocedu e o Si, and in assigning a na u al numbe o he Sij gene a ed om Si, so ha a na u al numbe is only assigned once. The b anching p ocedu e begins in he node V1 = (F, 1), he node oo , and i con inues in he o he nodes p o iding an a bo escence. The ollowing p ope ies a e ue: (1) M does no p oduce a loss o solu ions, ei he easible o no easible ( his esul comes ou o he second p ope y o M0); and (2) he gene a ed a bo escence is ini e: in a ini e se , M ca ied ou sepa a ions ha gene a e subse s o non coinciden solu ions ( his esul immedia ely comes ou o he de ini ion o M0 and o i s i s p ope y). Mo eo e , a e minal node is assumed o be ecognisable and o be immedia e o asce ain i i is emp y o no . So, i Vi is a e minal node o has been de ec ed o be emp y, hen his node does no ha e successo s ( e m in oduced in he ollowing Sec ion). * Successo o p edecesso node and descenden o ances o node: 7 Vj is a successo node o Vi and Vi is a p edecesso node o Vj ⇔ Vj ∈ M(Vi). Vj is a descenden node o Vi ⇔ Vj ∈ M(Vi) ∪ M2(Vi) ∪ M3(Vi) ∪ ... . Vj is an ances o node o Vi ⇔ Vj ∈ M-1(Vi) ∪ M-2(Vi) ∪ M-3(Vi) ∪ ... When M is applied and a successo node Vj is ob ained, Vj is said o ha e been gene a ed in he b anching p ocess. * Sepa a ed and comple ely sepa a ed node: Vi is sepa a ed ⇔ one o some o i s successo s ha e been gene a ed. Vi is comple ely sepa a ed ⇔ all o i s successo s ha e been gene a ed. * Bounding p ocedu e: pe is a bounding p ocedu e, i pe makes e e y node Vi co espond wi h Ce(Vi) ∈ κ, whe e Ce(Vi) ≤ (X) ∀ X ∈ Si ∩ E and ∀ pe ∈ P (being P a ini e se o p ocedu es pe). Thus, Ce(Vi) is a lowe bound o he alue o he objec i e unc ion o he easible solu ions con ained in he node Vi, ob ained h ough he bounding p ocedu e pe. To wo k wi h se e al bounding p ocedu es allows o ha e a succession o bounding p ocedu es, which can be o de ed in inc easing o de o calcula ion cos , which usually p o ides an inc easing succession o he quali y o he gap. pα ∈ P exis s such ha i Vi is a non-emp y e minal node, Cα(Vi) = (X), X ∈ Si (pα p o ides he alue o he objec i e unc ion o he only solu ion, which is easible, in e e y non-emp y e minal node). Le pe and pe’, pe’ is mo e powe ul han pe (pe ≤ pe’) ⇔ Ce(Vi) ≤ Ce’(Vi) ∀ Vi. Le Pi be he se o bounding p ocedu es ha ha e been applied in Vi; le C be he bes bound associa ed o Vi: () ( ) { } ei iei pP CV maxC V ∀∈ =; and le C (Vi) be a bound ob ained when ha ing in o ma ion o he p edecesso o o he successo nodes. The ollowing p ope ies a e ue: (1) Vj ∈ M(Vi) ⇒ C (Vj) = max{C(Vj), C(Vi)}; and (2) C () () () () {} { } ji ii j VMV VmaxCV,minCV ∀∈ = (p o ided ha Vi be comple ely sepa a ed). * Reduc ion p ocedu e: A educ ion p ocedu e e, e ∈ R (wi h R being a ini e se o p ocedu es e), consis s in eplacing a node Vi = (Si, i) by a new node Vi’ = (Sie’, i), wi h Sie’ ⊂ Si and, i Vi is also a non-emp y node, ∃ X*Si ∈ Sie’ i only one op imal solu ion is looked o (whe e X*Si is an op imal solu ion in Si) o ∃ X*Si ∈ Si Sie’ i all op imal solu ions a e looked o . Le e and e’, e’ is mo e powe ul han e ( e ≤ e’) ⇔ Sie’’ ⊆ Sie’. Reduc ion can conclude in ixing a iables o in dec easing i s anges o alues, al hough an op imal solu ion o Si can also be de ec ed. In his p ocedu e he esul ing 8 in o ma ion can also be ansmi ed, om successo o p edecesso nodes and ice e sa: (1) Vj ∈ M(Vi) ⇒ Sj’ = Sj ∩ Si’; and (2) Si’ = () {} ji VMV∀∈ ∪ Sj’ (p o ided ha Vi be comple ely sepa a ed). I is easy o check ha cons ain p opaga ion app oaches and consis ency echniques (coming om AI) a e educ ion p ocedu es. * Heu is ic esolu ion p ocedu e: Le H be a ini e se o heu is ic p ocedu es. I he ∈ H inds a easible solu ion X ∈ Si ∩ E, hen Ue(Vi) = (X) is an uppe bound o he alue o he objec i e unc ion o an op imal solu ion con ained in Si, ob ained h ough he heu is ic esolu ion p ocedu e he. Le he and he’, he’ is mo e powe ul han he (he ≤ he’) ⇔ Ue(Vi) ≥ Ue’(Vi) ∀ Vi (he’ always p o ides easible solu ions wi h a gap, ela ing o an op imal solu ion, equal o o less han ha p o ided by he). Le Hi be he se o heu is ic esolu ion p ocedu es ha ha e been applied o Vi; le U(Vi) be he alue o he bes ob ained easible solu ion associa ed o Vi: () ( ) { } ei iei hH UV min U V ∀∈ =; and le U(Vi) be he alue o he objec i e unc ion o a solu ion ob ained when ha ing in o ma ion o hei successo nodes. So: U () () () () {} { } ji ii j VMV V minUV, min UV ∀∈ =. I is wo hwhile emphasizing ha neighbou hood explo a ion p ocedu es/me aheu is ics ee (which will be in oduced la e ) can be de ined as a pa o a mo e elabo a ed p ocedu e he. * Examina ion p ocedu e: To examine a node Vi consis s in applying o i bounding and/o educ ion and/o heu is ic esolu ion p ocedu es, wi h he objec i e o imp o ing he in o ma ion ha we ha e abou he node and, some imes, also abou o he s. To ha e se e al ypes o examina ion p ocedu es allows applying hem in an al e na i e and i e a i e way; and e en hese can be o de ed in inc easing o de o di icul y o calcula ion cos , in he hope ha he leas expensi e p ocedu es allow d awing conclusions b ie ly: hey a e applied in inc easing o de o complexi y. * E alua ion p ocedu e: The e alua ion p ocedu e is a co espondence ha associa es a alue ϕ(Vi) ∈ R o each node Vi, whe e ϕ is he e alua ion and selec ion unc ion o he nex node o examine. In spi e o he huge impo ance o he s a egy o selec ing he nex node o b anch, in many pape s his is no s a ed explici ly o is desc ibed wi h ew de ails. On he o he hand, he gene aliza ion o an e alua ion and selec ion unc ion o nodes is an ex emely 15 should emphasize ha some o hese ideas a e al eady being used in enume a i e sea ch p ocedu es: • To s udy he in luence o in es ing ime ying o ind an ini ial solu ion o quali y o ini ialize B anch and Win: y di e en heu is ic esolu ion p ocedu es and di e se neighbou hood explo a ion echniques ha hese heu is ics can include. • To in oduce he concep o dynamism in he di e en p ocedu es ha make up B anch and Win, and, especially, in he e alua ion p ocedu e - o mo e de ails, see Pas o and Co ominas (2000)-. • To include elemen s ha a e no su icien ly aken in o accoun , especially o sol e indus ial p oblems (allowed compu ing ime, emaining compu ing ime, amoun o memo y used, e c.). • To es o use in di e en o de s he elemen s ha a e pa o he examina ion p ocedu es (bounding, educ ion and heu is ic esolu ion). • To wo k wi h se e al op ions in he bounding, educ ion, heu is ic esolu ion, neighbou hood explo a ion p ocedu es and in he p ope ies o he op imal solu ions; he objec i e is o es hei use in an inc easing o de o complexi y. • To ansmi p ope ies om successo o p edecesso nodes and ice e sa, o imp o e he a ailable in o ma ion on he nodes. • To use educ ion and heu is ic esolu ion p ocedu es in he in e media e nodes o he a bo escence (in all he nodes o only in hose ha a e mo e p omising han he o he ones). • To design heu is ic esolu ion p ocedu es ha include neighbou hood explo a ion echniques. • To apply neighbou hood sea ch p ocedu es when he alue o he incumben solu ion is imp o ed o whene e a new easible solu ion is ob ained. 6. CONCLUSIONS In his wo k we design B anch and Win: an OR ee sea ch me a-algo i hm o sol ing combina o ial op imisa ion p oblems. B anch and Win allows o speci y, as pa icula cases o i , he di e en ee sea ch p ocedu es ha ha e been p esen ed in he li e a u e o ope a ions esea ch as well as in ha o a i icial in elligence. The conclusions a e he ollowing: • Cu en ly, in he ield o sea ch p ocedu es o sol ing combina o ial op imisa ion p oblems, he scene is a he uns uc u ed and somewha con using: some au ho s de ine and use elemen s o p ocedu es in one way and o he s in ano he way which, al hough simila , is no equi alen . Mo eo e , he gene al o mula ions ha ha e been p esen ed in he li e a u e ha e a se o de iciencies ha a ec , in a g ea e o smalle deg ee, all o hem. • Wi h espec o he selec ion unc ions and o he explo a ion s a egies ha a e p oposed in he usual p ocedu es, he e a e aspec s ha ha e no been su icien ly aken in o accoun om a p ac ical poin o iew. • B anch and Win has been o mula ed, wi h he ollowing ea u es: a) I is gene al enough o include, as pa icula cases, all hese enume a i e echniques. 16 b) I akes aspec s, which a e impo an om an indus ial poin o iew, in o accoun : maximum allowed compu ing ime, amoun o memo y used, emaining compu ing ime. c) I uses a clea and uni ying e minology. d) I combines and speci ies he di e se common elemen s ha ha e all hese p ocedu es o ob ain hem. e) I allows o use bounding, educ ion, heu is ic esolu ion and neighbou hood explo a ion p ocedu es, in all he pa ial p oblems gene a ed. ) The concep o dynamism is in oduced in he di e en p ocedu es ha make up he me a-algo i hm: bounding, educ ion, heu is ic esolu ion,... g) I uses a gene al e alua ion and selec ion unc ion o he nex node o examine, including many new elemen s which had no been adi ionally conside ed bu a e o g ea impo ance: he s a e o he explo a ion g aph and he en i onmen condi ions in which he p oblem is sol ed. h) I allows o design new sea ch p ocedu es, acco ding o how he elemen s o B anch and Win a e combined. Thus, he new me a-algo i hm ha we ha e called B anch and Win allows o a be e unde s anding o ee sea ch algo i hms o combina o ial op imiza ion p oblems and i syn hesizes he di e en ee sea ch p ocedu es ha ha e been p esen ed bo h in ope a ions esea ch and in a i icial in elligence li e a u es. This me a-algo i hm assembles he di e en elemen s ha a e pa o hese sea ch p ocedu es and uses hem dynamically in he ee. And u he mo e, B anch and Win p o ides a means o de eloping new sea ch s a egies and p ocedu es. REFERENCES Ba A. and Feigenbaum E.A. (eds) (1981). The Handbook o A i icial In elligence (Volume 1). Kau mann. Bockmay A. and Kaspe T. (1998). B anch and in e : A uni ying amewo k o in ege and ini e domain cons ain p og amming. INFORMS Jou nal on Compu ing 10, 287-300. B ails o d S.C., Po s C.N. and Smi h B.M. (1999). Cons ain sa is ac ion p oblems: Algo i hms and applica ions. Eu opean Jou nal o Ope a ional Resea ch 119, 557- 581. Companys R. (1975). P og amación combina o ia: aplicación a la o denación de abajos en un o denado con sis ema ope a i o en discos. Symposia Ma hema ica XV, 83-107. Co ominas A. and Companys R. (1977). P ocedimien o gene alizado de b anch and bound. Qües iió 1, 49-62. Co êa R. (1995). A Pa allel Fo mula ion o Gene al B anch-and-Bound Algo i hms. Lec u e No es in Compu e Science 980, 395-409. Goldengo in B., Ghosh D. and Sie ksma G. (2004). B anch and peg algo i hms o he simple plan loca ion p oblem. Compu e s & Ope a ions Resea ch 31, 241-255. G eenbe g H.J. (1996). A i icial in elligence. In: Gass S.I. and Ha is C.M. (eds), The Encyclopedia o Ope a ions Resea ch and Managemen Science. Kluwe , 25-28. 17 Ha alick R. and Ellio G. (1980). Inc easing ee sea ch e iciency o cons ain sa is ac ion p oblems. A i icial In elligence 14, 263-313. Ha P.E., Nilsson N.J. and Raphael B. (1968). A o mal basis o he heu is ic de e mina ion o minimum cos pa hs. IEEE T ansac ions on Sys em Science and Cybe ne ics SSC-4, 100-107. Helman P. (1989). A Common Schema o Dynamic P og amming and B anch and Bound Algo i hms. Jou nal o he Associa ion o Compu ing Machine y 36, 97- 128. Ho man K.L. and Padbe g M. (1993). Sol ing Ai line C ew Scheduling P oblems by B anch-and-Cu . Managemen Science 39, 657-682. Iba aki T. (1988). Enume a i e app oaches o combina o ial op imiza ion, pa I & II. Annals o Ope a ions Resea ch 10, 11 (1988). Ko R.E. (1990). Sea ch. In: Shapi o S.C. (ed), Encyclopedia o A i icial In elligence. John Wiley & Sons, 994-998. Kuma V. and Kanal L. (1983a). A Gene al B anch and Bound Fo mula ion o Unde s anding and Syn hesising And/O T ee Sea ch P ocedu es. A i icial In elligence 21, 179-198. Kuma V. and Kanal L. (1983b). The composi e decision p ocess: a uni ying o mula ion o heu is ic sea ch, dynamic p og amming and b anch and bound p ocedu es. In P oceedings o he Thi d Na ional Con e ence on A i icial In elligence, 220-224. Washing on. Ma s en R.E. and Mo in T.L. (1978). A hyb id app oach o disc e e ma hema ical p og amming. Ma hema ical P og amming 14, 21-40. Nau D.S., Kuma V. and Kanal L. (1984). Gene al B anch and Bound, and I s Rela ion o A* and AO*. A i icial In elligence 23, 29-58. Nilsson N.J. (1971). P oblem-sol ing me hods in a i icial in elligence. McG aw-Hill. Nilsson N.J. (1980). P inciples o A i icial In elligence. Kau mann. Pas o R. (1999). Me algo i mo de op imización combina o ia median e la explo ación de g a os. PhD hesis, Technology Uni e si y o Ca alonia. Pas o R. and Co ominas A. (2000). S a egies o Node Selec ion in Sea ch P ocedu es o Sol ing Combina o ial Op imiza ion P oblems: A Su ey and a Gene al Fo maliza ion p og amming. TOP: Jou nal o he Spanish S a is ical and Ope a ions Resea ch Socie y 8, 111-134. Pea l J. (1984). Heu is ics: In elligen Sea ch S a egies o Compu e P oblem Sol ing. Addison-Wesley. Rich E. and Knigh K. (1991). A i icial In elligence. McG aw-Hill. Ryoo H.S. and Sahinidis N.V. (1996). A B anch-and-Reduce App oach o Global Op imiza ion. Jou nal o Global Op imiza ion 8, 107-139. Sa elsbe gh M. (1997). A B anch-and-P ice Algo i hm o he Gene alized Assignmen P oblem. Ope a ions Resea ch 45, 831-841. Tuy H. and Ho s R. (1988). Con e gence and Res a in B anch-and-Bound Algo i hms o Global Op imiza ion. Applica ion o Conca e Minimiza ion and D.C. Op imiza ion P oblems. Ma hema ical P og amming 41, 161-183.