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

Electronic version of an article published as [Top. Revista de la Sociedad de Estadística e Investigación Operativa, 2004, Vol. 12, No. 1, p. 169-191.] © [copyright Springer-Verlag] 1 Branch and Win: OR tree search algorithms for solving combinatorial optimisation problems Rafael Pastor∗, Albert Corominas Department of Business Administration. Research Institute IOC. School of Industrial Engineering of Barcelona Technology University of Catalonia Avda. Diagonal, 647, 7ª planta 08028 Barcelona (Spain) E-mail address: {pastor/corominas}@ioc.upc.es Abstract Currently, most combinatorial optimisation problems have to be solved, if the optimum solution is sought, using general techniques to explore the space of feasible solutions and, more specifically, through exploratory enumerative procedures in trees and search graphs. We propose Branch and Win, a general formulation for understanding and synthesising the different tree search procedures that have been presented in the literature of operations research as well as in that of artificial intelligence. Several general ideas are also presented, whose application allows designing new hybrid search algorithms, in order to implement the procedure. Key Words: Combinatorial optimization, branch and bound, artificial intelligence. AMS subject classification: 90C27, 90C57, 68T20. 1. INTRODUCTION As it is known, it is very difficult to solve optimally most of the combinatorial optimisation problems due to their intrinsic complexity. At present, though specific procedures exist to solve some specific combinatorial optimisation problems, most of them have to be solved employing general techniques to explore the space of feasible solutions, and, more specifically, through exploratory enumerative procedures in trees and graphs of states (in the enumerative procedures, all solutions are generated and enumerated, explicitly or implicitly). We analyse the exploratory enumerative procedures in OR tree representations -which have been exposed both in the operations research and artificial intelligence (AI) literaturesand we propose a new meta-algorithm that we have called Branch and Win: a new general formulation that includes all of them. Branch and Win allows for a better understanding of tree search algorithms for combinatorial optimization problems, synthesizes the different tree search procedures that have been presented in the literature, assembles the different elements that are part of these search procedures and uses them dynamically in the tree and provides a means for developing new search strategies and procedures such as hybridizations of search algorithms with local search and metaheuristics. ∗ Corresponding author: Rafael Pastor E-mail address: [email protected] 2 The rest of the paper continues as follow. In Section 2 the resolution enumerative procedures and the existent general formulations are analysed. Branch and Win is formulated and described in Section 3. In Section 4 we claim the integrating character of Branch and Win. Several general ideas that allow designing new hybrid search strategies are enumerated in Section 5. Finally, some conclusions are discussed in Section 6. 2. ENUMERATIVE SOLUTION PROCEDURES A great number of enumerative search procedures for solving combinatorial optimisation problems have appeared in the operations research literature as well as in the AI literature over the last few decades. Most of these search approaches have been described by different authors and sometimes the definitions presented are not specific enough to know whether they refer to a selection strategy or to a particular algorithm and, in this case, what other characteristics are included in the search algorithm. For example, the depth first search, which always explores a child node of the node most recently separated, exists. But an approach like the previous one has also been given the name of depth first search which, moreover, incorporates a procedure for grouping equivalent states. With the aim of unifying these techniques, general formulations have also been presented. But sometimes there are aspects that have not been sufficiently taken into account from a practical point of view. Among others: completeness of the corresponding partial solution, the state of the exploration graph (total number of nodes generated, amount of memory used, etc.), the environment conditions in which the problem is solved (maximum allowed computing time, maximum available memory, access time to the medium -RAM, hard disk, etc.- on which a node can be stored, etc.). 2.1. Exploratory enumerative procedures We present a brief introduction to the relationships between diverse exploratory enumerative procedures for solving combinatorial optimisation problems. Most of the enumerative procedures have been increasingly employed both in operations research and in AI to solve real problems. Sometimes a procedure has been given different names being the same technique (for example, the depth first procedure has been called several different ways: depth first search, DFS, linear search, single branch search, LIFO search and vertical search). And some procedures present so many similarities that they could be considered redundant: in Barr and Feigenbaum (1981) and Kumar and Kanal (1983b), branch and bound procedures (B&B), dynamic programming techniques (DP) -in this work, DP is used to refer to finite-deterministic dynamic programming techniquesand the heuristic search procedure A* -introduced by Hart et al (1968)- are said to be very similar, although B&B and DP have been used in operations research and A* in AI (e.g., according to Barr and Feigenbaum (1981), A* is a best first search with an evaluation function formed by the sum of the minimal cost associated with reaching the node n from the root, plus a heuristic estimate of the 3 minimal cost of reaching an objective node from the node n). Furthermore the relationships between these classes of procedures have been rather controversial. For example, Nilsson (1980) defines the algorithm A as a procedure A* that cannot guarantee the optimality of the solution. While many other authors (Barr and Feigenbaum (1981), Korf (1990), Rich and Knight (1991)) consider that there only exists a procedure (A*) and it may or may not guarantee the optimality of the solution depending on the fulfillment or not of the admissibility property. In this case there also exist particular definitions of A*: Rich and Knight (1991) incorporate a procedure for grouping equivalent states and consider that the cost of a path is equal to its number of stages. Pearl (1984) considers A* as a particular Z* (a special best first search described in Pearl (1984)). As it is discussed by several authors (Pearl (1984) and Greenberg (1996) among others), if the selection strategy of the next node to be explored consists in minimising the depth of the node, the procedure A* is equivalent to that of the breadth first search; and, if it consists in minimising minus the depth of the node, the procedure A* is equivalent to that of the depth first search (Pearl (1984)). For Nilsson (1971), Barr and Feigenbaum (1981) and Pearl (1984) A* is the smallest cost first search procedure if there is not heuristic information. On the other hand, Rich and Knight (1991) discuss a larger number of possibilities. According to Greenberg (1996), branch and bound for integer programming is a particular case of A* in operations research, where the evaluation function takes the value of the objective function of the linear relaxation of the node (without commenting on the main characteristic of B&B: the pruning by a bounding test). Barr and Feigenbaum (1981) name ordered state space search to the best first search and specify that the breadth first, the uniform cost and the depth first are specific cases of this. On the other hand, Nilsson (1971) and Pearl (1984) specifically define the smallest cost first search (uniform cost search or cheapest first strategy), while most of the authors consider it a special case of the best first search. And Pearl (1984) differences between whether a feasible solution is only looked for (best first search strategy) and whether an optimal solution is looked for (algorithm that is named best first search* by Pearl). The relationships between B&B and DP have also been rather controversial. While some authors claim that DP is a more general technique than B&B, others consider that it is exactly the opposite. There are also those who claim that some DP techniques can be stated in a framework of B&B, although B&B approaches can also be presented as DP procedures with a bounding test -see, e.g., Marsten and Morin (1978), Kumar and Kanal (1983b) and Ibaraki (1988)-. It is also necessary to emphasise the existence of authors that seem to have the relationships between these classes of procedures clearer: “A class of algorithms similar to A* is used in operations research under the name of branch-and-bound algorithms”, Barr and Feigenbaum (1981), p. 64. The situation previously described shows that the scene of search procedures for solving combinatorial optimisation problems is rather unstructured, dispersed and insufficiently formalized. On the other hand, in the last years new search procedures have been 4 defined -branch & price (e.g., Savelsbergh (1997)), branch & cut (e.g., Hoffman and Padberg (1993)), branch & reduce (e.g., Ryoo and Sahinidis (1996)), branch & peg (Goldengorin et al (2004)), etc.- that can be integrated in well-known frameworks, as well as other search techniques as constraints propagation (see, e.g., Haralick and Elliott (1980) and Brailsford et al (1999)). This can speed up the development of new procedures, new names or new hybrid techniques, still complicating the current scene more. In Pastor (1999) and Pastor and Corominas (2000) a wide survey of enumerative search procedures for solving combinatorial optimisation problems is presented. In these works, the relationships, deficiencies and similarities between the enumerative procedures related in the operations research literature as well as in AI literature are studied and analysed; and the following conclusions are obtained: • There are important elements that have not been sufficiently taken into account from a practical point of view. For instance: total number of generated nodes, amount of memory used, maximum allowed computing time, maximum available memory. • Dispersion, confusion and even duplicity exist in the definitions of the procedures and in the terminology used. Partly this is due to the fact that these techniques have been used both in operations research and in AI. • The enumerative search procedures have got diverse common elements whose specification allows to obtain them. • As some authors present, some search procedures derive from others; but these derivations could be more general. • In the extreme case, an enumerative procedure would generate the whole statesearch, being very inefficient. To reduce the space of states three general reduction tactics exist: elimination of dominated states, pruning of nodes and detection of empty nodes. • The consistency techniques coming from AI can be embedded, as it is done in some procedures, in branch and bound frameworks -see, e.g., Bockmayr and Kasper (1998), who propose a common framework for constraint programming and integer programming called branch and infer. This connects the search procedures coming from both investigation areas. 2.2. Generalized search procedures A general formulation whereby all of these procedures can be viewed in a unified manner seems advisable. This necessity has already been detected and diverse general search schemas have already been presented. Among all of these, we consider that some schemas are more general and unifying than others, and even in some formalization, as in Corrêa (1995), some search procedures are shown as specific cases of the proposed general schema. We have studied and analysed the following references: Corominas and Companys (1977), Kumar and Kanal (1983a and 1983b), Nau et al (1984), Ibaraki (1988), Tuy and Horst (1988) –who present a general B&B scheme for global optimisation-, Helman (1989) and Corrêa (1995). As a result, the following deficiencies (which affect, in a greater or smaller degree, all of them) can be enumerated (Pastor (1999)): 5 • On some occasions the terminology that is used is not very common in operations research (especially in references coming from AI). This has a negative impact on its understanding and practical applicability. • The used elements are usually presented with scarce precision. • Many search procedures are not considered, particularly the most recent. • The selection strategy of the next node to explore is usually static. • The following exploration elements are not generally used: Reformulation and pre-processing, in the original problem as well as in the partial problems. Use of local optimisation techniques and local search procedures, in the partial problems and when a new feasible solution is obtained. Calculation of new superior bounds (if we are minimising) in the partial problems. Use of diverse bounding, reformulation and reduction procedures. The environment conditions in which the problem is solved (maximum allowed computing time, maximum available memory, etc.) and the state of the exploration graph. It is necessary to emphasise that these general schemas have represented an important advance at that moment, for structuring and unifying diverse particular search procedures. 3. BRANCH AND WIN: OR TREE SEARCH ALGORITHMS FOR SOLVING COMBINATORIAL OPTIMISATION PROBLEMS The conclusions shown in the previous Section, provide evidence of the necessity for designing a new general realistic procedure with the usual terminology in operations research in order to solve combinatorial optimisation problems. To meet this necessity we propose a new meta-algorithm that we have called Branch and Win. It is necessary to comment that the nearest antecedents of Branch and Win, which we have taken as starting point, are the general procedures presented in Companys (1975) and Corominas and Companys (1977). 3.1. Definitions * Problem to be solved: We propose a general definition of a combinatorial optimisation problem, in which, after defining the value of the integer variables, a procedure exists to find an optimal solution to the remaining problem: [ ] ( ) ,OPT Z f X T=  ( ) , X TS ∈ , where: S is the feasible space inside the total space of solutions; X is a vector of integer bounded variables; T is a vector of continuous variables; and given X´ is possible to obtain T´, which provides the optimal solution of the problem for X´. So one of the more important combinatorial optimisation problems is also included: mixed integer linear programming. 6 The original problem to be solved can be reduced immediately to the following mathematical program: [ ] ( ) M IN Z f X= X EF ∈ ⊆, where: F is the finite set of possible solutions (usually the Cartesian product of the domains of the variables); E is the finite set of feasible solutions; X is a solution; f: E → κ, with κ an ordered set (usually the integer or the continuous numbers). * Node: Let: ℘(F) the set of subsets of F; N the set of natural numbers; and Si a subset of solutions. We define a node Vi as follows: Vi ∈ ℘(F) x N, therefore, Vi = (Si, i). The natural number is necessary to identify the node, since the subsets of solutions belonging to two nodes may coincide. * Empty node and terminal node: Vi is an empty node ⇔ Si ∩ E = ∅. Vi is a terminal node ⇔ |Si| = 1. * Branching procedure: Let M0 be a primitive branching procedure. M0 makes the elements of ℘(F) with cardinality ≥ 2 correspond with two or more subsets of F. M0 separates the subsets of F without eliminating any element from ℘(F). And the following properties are true: (1) Y ∈ M0(S) ⇒ Y ≠ S; (2) () {} 0 YM S∀∈ ∪ Y = S; and (3) ∀ Y, Z ∈ M0(S) ⇒ Y ⊆ Z. Defined M0, let M be a branching procedure. M is a correspondence that associates a subset of (terminal or non-terminal) nodes to a non-terminal node: M consists in applying a M0 procedure to Si, and in assigning a natural number to the Sij generated from Si, so that a natural number is only assigned once. The branching procedure begins in the node V1 = (F, 1), the node root, and it continues in the other nodes providing an arborescence. The following properties are true: (1) M does not produce a loss of solutions, either feasible or not feasible (this result comes out of the second property of M0); and (2) the generated arborescence is finite: in a finite set, M carried out separations that generate subsets of non coincident solutions (this result immediately comes out of the definition of M0 and of its first property). Moreover, a terminal node is assumed to be recognisable and to be immediate to ascertain if it is empty or not. So, if Vi is a terminal node or has been detected to be empty, then this node does not have successors (term introduced in the following Section). * Successor or predecessor node and descendent or ancestor node: 7 Vj is a successor node of Vi and Vi is a predecessor node of Vj ⇔ Vj ∈ M(Vi). Vj is a descendent node of Vi ⇔ Vj ∈ M(Vi) ∪ M2(Vi) ∪ M3(Vi) ∪ ... . Vj is an ancestor node of Vi ⇔ Vj ∈ M-1(Vi) ∪ M-2(Vi) ∪ M-3(Vi) ∪ ... When M is applied and a successor node Vj is obtained, Vj is said to have been generated in the branching process. * Separated and completely separated node: Vi is separated ⇔ one or some of its successors have been generated. Vi is completely separated ⇔ all of its successors have been generated. * Bounding procedure: pe is a bounding procedure, if pe makes every node Vi correspond with Ce(Vi) ∈ κ, where Ce(Vi) ≤ f(X) ∀ X ∈ Si ∩ E and ∀ pe ∈ P (being P a finite set of procedures pe). Thus, Ce(Vi) is a lower bound of the value of the objective function of the feasible solutions contained in the node Vi, obtained through the bounding procedure pe. To work with several bounding procedures allows to have a succession of bounding procedures, which can be ordered in increasing order of calculation cost, which usually provides an increasing succession of the quality of the gap. pα ∈ P exists such that if Vi is a non-empty terminal node, Cα(Vi) = f(X), X ∈ Si (pα provides the value of the objective function for the only solution, which is feasible, in every non-empty terminal node). Let pe and pe’, pe’ is more powerful than pe (pe ≤ pe’) ⇔ Ce(Vi) ≤ Ce’(Vi) ∀ Vi. Let Pi be the set of bounding procedures that have been applied in Vi; let C be the best bound associated to Vi: () ( ) { } ei iei pP CV maxC V ∀∈ =; and let C (Vi) be a bound obtained when having information of the predecessor or of the successor nodes. The following properties are true: (1) Vj ∈ M(Vi) ⇒ C (Vj) = max{C(Vj), C(Vi)}; and (2) C () () () () {} { } ji ii j VMV VmaxCV,minCV ∀∈ = (provided that Vi be completely separated). * Reduction procedure: A reduction procedure e, re ∈ R (with R being a finite set of procedures re), consists in replacing a node Vi = (Si, i) by a new node Vi’ = (Sie’, i), with Sie’ ⊂ Si and, if Vi is also a non-empty node, ∃ X*Si ∈ Sie’ if only one optimal solution is looked for (where X*Si is an optimal solution in Si) or ∃ X*Si ∈ Si \ Sie’ if all optimal solutions are looked for. Let re and re’, re’ is more powerful than re (re ≤ re’) ⇔ Sie’’ ⊆ Sie’. Reduction can conclude in fixing variables or in decreasing its ranges of values, although an optimal solution of Si can also be detected. In this procedure the resulting 8 information can also be transmitted, from successor to predecessor nodes and vice versa: (1) Vj ∈ M(Vi) ⇒ Sj’ = Sj ∩ Si’; and (2) Si’ = () {} ji VMV∀∈ ∪ Sj’ (provided that Vi be completely separated). It is easy to check that constraint propagation approaches and consistency techniques (coming from AI) are reduction procedures. * Heuristic resolution procedure: Let H be a finite set of heuristic procedures. If he ∈ H finds a feasible solution X ∈ Si ∩ E, then Ue(Vi) = f(X) is an upper bound of the value of the objective function of an optimal solution contained in Si, obtained through the heuristic resolution procedure he. Let he and he’, he’ is more powerful than he (he ≤ he’) ⇔ Ue(Vi) ≥ Ue’(Vi) ∀ Vi (he’ always provides feasible solutions with a gap, relating to an optimal solution, equal to or less than that provided by he). Let Hi be the set of heuristic resolution procedures that have been applied to Vi; let U(Vi) be the value of the best obtained feasible solution associated to Vi: () ( ) { } ei iei hH UV min U V ∀∈ =; and let U(Vi) be the value of the objective function of a solution obtained when having information of their successor nodes. So: U () () () () {} { } ji ii j VMV V minUV, min UV ∀∈ =. It is worthwhile emphasizing that neighbourhood exploration procedures/metaheuristics ee (which will be introduced later) can be defined as a part of a more elaborated procedure he. * Examination procedure: To examine a node Vi consists in applying to it bounding and/or reduction and/or heuristic resolution procedures, with the objective of improving the information that we have about the node and, sometimes, also about others. To have several types of examination procedures allows applying them in an alternative and iterative way; and even these can be ordered in increasing order of difficulty or calculation cost, in the hope that the least expensive procedures allow drawing conclusions briefly: they are applied in increasing order of complexity. * Evaluation procedure: The evaluation procedure is a correspondence that associates a value ϕ(Vi) ∈ R to each node Vi, where ϕ is the evaluation and selection function of the next node to examine. In spite of the huge importance of the strategy for selecting the next node to branch, in many papers this is not stated explicitly or is described with few details. On the other hand, the generalization of an evaluation and selection function of nodes is an extremely 15 should emphasize that some of these ideas are already being used in enumerative search procedures: • To study the influence of investing time trying to find an initial solution of quality to initialize Branch and Win: try different heuristic resolution procedures and diverse neighbourhood exploration techniques that these heuristics can include. • To introduce the concept of dynamism in the different procedures that make up Branch and Win, and, especially, in the evaluation procedure -for more details, see Pastor and Corominas (2000)-. • To include elements that are not sufficiently taken into account, especially to solve industrial problems (allowed computing time, remaining computing time, amount of memory used, etc.). • To test to use in different orders the elements that are part of the examination procedures (bounding, reduction and heuristic resolution). • To work with several options in the bounding, reduction, heuristic resolution, neighbourhood exploration procedures and in the properties of the optimal solutions; the objective is to test their use in an increasing order of complexity. • To transmit properties from successor to predecessor nodes and vice versa, to improve the available information on the nodes. • To use reduction and heuristic resolution procedures in the intermediate nodes of the arborescence (in all the nodes or only in those that are more promising than the other ones). • To design heuristic resolution procedures that include neighbourhood exploration techniques. • To apply neighbourhood search procedures when the value of the incumbent solution is improved or whenever a new feasible solution is obtained. 6. CONCLUSIONS In this work we design Branch and Win: an OR tree search meta-algorithm for solving combinatorial optimisation problems. Branch and Win allows to specify, as particular cases of it, the different tree search procedures that have been presented in the literature of operations research as well as in that of artificial intelligence. The conclusions are the following: • Currently, in the field of search procedures for solving combinatorial optimisation problems, the scene is rather unstructured and somewhat confusing: some authors define and use elements or procedures in one way and others in another way which, although similar, is not equivalent. Moreover, the general formulations that have been presented in the literature have a set of deficiencies that affect, in a greater or smaller degree, all of them. • With respect to the selection functions and to the exploration strategies that are proposed in the usual procedures, there are aspects that have not been sufficiently taken into account from a practical point of view. • Branch and Win has been formulated, with the following features: a) It is general enough to include, as particular cases, all these enumerative techniques. 16 b) It takes aspects, which are important from an industrial point of view, into account: maximum allowed computing time, amount of memory used, remaining computing time. c) It uses a clear and unifying terminology. d) It combines and specifies the diverse common elements that have all these procedures to obtain them. e) It allows to use bounding, reduction, heuristic resolution and neighbourhood exploration procedures, in all the partial problems generated. f) The concept of dynamism is introduced in the different procedures that make up the meta-algorithm: bounding, reduction, heuristic resolution,... g) It uses a general evaluation and selection function of the next node to examine, including many new elements which had not been traditionally considered but are of great importance: the state of the exploration graph and the environment conditions in which the problem is solved. h) It allows to design new search procedures, according to how the elements of Branch and Win are combined. Thus, the new meta-algorithm that we have called Branch and Win allows for a better understanding of tree search algorithms for combinatorial optimization problems and it synthesizes the different tree search procedures that have been presented both in operations research and in artificial intelligence literatures. This meta-algorithm assembles the different elements that are part of these search procedures and uses them dynamically in the tree. And furthermore, Branch and Win provides a means for developing new search strategies and procedures. REFERENCES Barr A. and Feigenbaum E.A. (eds) (1981). The Handbook of Artificial Intelligence (Volume 1). Kaufmann. Bockmayr A. and Kasper T. (1998). Branch and infer: A unifying framework for integer and finite domain constraint programming. INFORMS Journal on Computing 10, 287-300. Brailsford S.C., Potts C.N. and Smith B.M. (1999). Constraint satisfaction problems: Algorithms and applications. European Journal of Operational Research 119, 557581. Companys R. (1975). Programación combinatoria: aplicación a la ordenación de trabajos en un ordenador con sistema operativo en discos. Symposia Mathematica XV, 83-107. Corominas A. and Companys R. (1977). Procedimiento generalizado de branch and bound. Qüestiió 1, 49-62. Corrêa R. (1995). A Parallel Formulation for General Branch-and-Bound Algorithms. Lecture Notes in Computer Science 980, 395-409. Goldengorin B., Ghosh D. and Sierksma G. (2004). Branch and peg algorithms for the simple plant location problem. Computers & Operations Research 31, 241-255. Greenberg H.J. (1996). Artificial intelligence. In: Gass S.I. and Harris C.M. (eds), The Encyclopedia of Operations Research and Management Science. Kluwer, 25-28. 17 Haralick R. and Elliott G. (1980). Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence 14, 263-313. Hart P.E., Nilsson N.J. and Raphael B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on System Science and Cybernetics SSC-4, 100-107. Helman P. (1989). A Common Schema for Dynamic Programming and Branch and Bound Algorithms. Journal of the Association for Computing Machinery 36, 97128. Hoffman K.L. and Padberg M. (1993). Solving Airline Crew Scheduling Problems by Branch-and-Cut. Management Science 39, 657-682. Ibaraki T. (1988). Enumerative approaches to combinatorial optimization, part I & II. Annals of Operations Research 10, 11 (1988). Korf R.E. (1990). Search. In: Shapiro S.C. (ed), Encyclopedia of Artificial Intelligence. John Wiley & Sons, 994-998. Kumar V. and Kanal L. (1983a). A General Branch and Bound Formulation for Understanding and Synthesising And/Or Tree Search Procedures. Artificial Intelligence 21, 179-198. Kumar V. and Kanal L. (1983b). The composite decision process: a unifying formulation for heuristic search, dynamic programming and branch and bound procedures. In Proceedings of the Third National Conference on Artificial Intelligence, 220-224. Washington. Marsten R.E. and Morin T.L. (1978). A hybrid approach to discrete mathematical programming. Mathematical Programming 14, 21-40. Nau D.S., Kumar V. and Kanal L. (1984). General Branch and Bound, and Its Relation to A* and AO*. Artificial Intelligence 23, 29-58. Nilsson N.J. (1971). Problem-solving methods in artificial intelligence. McGraw-Hill. Nilsson N.J. (1980). Principles of Artificial Intelligence. Kaufmann. Pastor R. (1999). Metalgoritmo de optimización combinatoria mediante la exploración de grafos. PhD thesis, Technology University of Catalonia. Pastor R. and Corominas A. (2000). Strategies of Node Selection in Search Procedures for Solving Combinatorial Optimization Problems: A Survey and a General Formalization programming. TOP: Journal of the Spanish Statistical and Operations Research Society 8, 111-134. Pearl J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley. Rich E. and Knight K. (1991). Artificial Intelligence. McGraw-Hill. Ryoo H.S. and Sahinidis N.V. (1996). A Branch-and-Reduce Approach to Global Optimization. Journal of Global Optimization 8, 107-139. Savelsbergh M. (1997). A Branch-and-Price Algorithm for the Generalized Assignment Problem. Operations Research 45, 831-841. Tuy H. and Horst R. (1988). Convergence and Restart in Branch-and-Bound Algorithms for Global Optimization. Application to Concave Minimization and D.C. Optimization Problems. Mathematical Programming 41, 161-183.