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.