Obtaining the efficient set of nonlinear biobjective optimization problems via interval branch-and-bound methods

Fernández, José; Tóth, Boglárka
April 2009
Computational Optimization & Applications;Apr2009, Vol. 42 Issue 3, p393
Academic Journal
Obtaining a complete description of the efficient set of multiobjective optimization problems can be of invaluable help to the decision-maker when the objectives conflict and a solution has to be chosen. In this paper we present an interval branch-and-bound algorithm which aims at obtaining a tight outer approximation of the whole efficient set of nonlinear biobjective problems. The method enhances the performance of a previous rudimentary algorithm thanks to the use of new accelerating devices, namely, three new discarding tests. Some computational studies on a set of competitive location problems demonstrate the efficiency of the discarding tests, as well as the superiority of the new algorithm, both in time and in quality of the outer approximations of the efficient set, as compared to another method, an interval constraint-like algorithm, with the same aim. Furthermore, we also give some theoretical results of the method, which show its good properties, both in the limit (when the tolerances are set equal to zero and the algorithm does not stop) and when the algorithm stops after a finite number of steps (when we use positive tolerances). A key point in the approach is that, thanks to the use of interval analysis tools, it can be applied to nearly any biobjective problem.


Related Articles

  • BRANCH-AND-BOUND AS A HIGHER-ORDER FUNCTION. Mckeown, G. P.; Rayward-Smith, V. J.; Turpin, H. J. // Annals of Operations Research;1991, Vol. 33 Issue 1-4, p379 

    The branch-and-bound paradigm is presented as a higher-order function and illustrated by instantiations, providing two well-known branch-and-bound algorithms for the Steiner tree problem in graphs and one for the travelling salesman problem. We discuss the advantages of such a specification and...

  • Towards a closer integration of finite domain propagation and simplex-based algorithms. Hajian, Mozafar T.; El-Sakkout, Hani; Wallace, Mark; Lever, Jonathan M.; Richards, Barry // Annals of Operations Research;1998, Vol. 81 Issue 1-4, p421 

    This paper describes our experience in implementing an industrial application using the finite domain solver of the ECLiPSe constraint logic programming (CLP) system, in conjunction with the mathematical programming (MP) system, FortMP. In this technique, the ECLiPSe system generates a feasible...

  • MINIMIZING THE SUM OF THE JOB COMPLETION TIMES IN THE TWO-MACHINE FLOW SHOP BY LAGRANGIAN RELAXATION. van de Velde, S. L. // Annals of Operations Research;1990, Vol. 26 Issue 1-4, p257 

    A branch-and-bound algorithm is presented for the two-machine flow shop problem with the objective of minimizing the sum of the job completion times. Lower bounds and precedence constraints result from a Lagrangian relaxation of this problem. The Lagrangian subproblem turns out to be a linear...

  • Setup and Open-Stacks Minimization in One-Dimensional Stock Cutting. Belov, Gleb; Scheithauer, Guntram // INFORMS Journal on Computing;Winter2007, Vol. 19 Issue 1, p27 

    The primary objective in cutting and packing problems is trim loss or material input minimization (in stock cutting) or value maximization (in knapsack-type problems). However, in real-life production we usually have many other objectives (costs) and constraints. Probably the most complex...

  • Parallel branch-and-branch algorithms: Survey and synthesis. Gendron, Bernard; Crainic, Teodor Gabriel // Operations Research;Nov/Dec94, Vol. 42 Issue 6, p1042 

    We present a detailed and up-to-date survey of the literature on parallel branch-and-bound algorithms. We synthesize previous work in this area and propose a new classification of parallel branch-and-bound algorithms. This classification is used to analyze the methods proposed in the literature....

  • FINDING THE K SHORTEST LOOPLESS PATHS IN A NETWORK. Yen, Jin Y. // Management Science;Jul1971, Vol. 17 Issue 11, p712 

    This paper presents an algorithm for finding the K loopless paths that have the shortest lengths from one node to another node in a network. The significance of the new algorithm is that its computational upper bound increases only linearly with the value of K. Consequently, in general, the new...

  • AN ALGORITHM FOR SEPARABLE NONCONVEX PROGRAMMING PROBLEMS II: NONCONVEX CONSTRAINTS. Soland, Richard M. // Management Science;Jul1971, Vol. 17 Issue 11, p759 

    We extend a previous algorithm in order to solve mathematical programming problems of the form: Find x = (x[sub 1], ..., x[sub n]) to minimize Σ φ[sub i0] (x[sub I]) subject to and . Each φ[sub ij] is assumed to be lower semicontinuous, possibly nonconvex, and G is assumed to be...

  • AN OPTIMAL SOLUTION METHOD FOR LARGE-SCALE MULTIPLE TRAVELING SALESMEN PROBLEMS. Gavish, Bezalel; Srikanth, Kizhanathan // Operations Research;Sep/Oct86, Vol. 34 Issue 5, p698 

    We develop an efficient branch-and-bound based method for solving the Multiple Traveling Salesman Problem, and develop lower bounds through a Lagrangean relaxation that requires computing a degree-constrained minimal spanning tree. A subgradient optimization procedure updates the Lagrange...

  • Optimal periodic scheduling of multipurpose batch plants. Shah, N.; Pantelides, C. C.; Sargent, R. W. H. // Annals of Operations Research;1993, Vol. 42 Issue 1-4, p193 

    A rigorous mathematical programming framework for the scheduling of multipurpose batch plants operated in a cyclic mode is presented. The proposed formulation can deal with batch operations described by complex processing networks, involving shared intermediates, material recycles, and multiple...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics