Optimization Online


A branch-and-bound algorithm for biobjective mixed-integer programs

Pietro Belotti(pbelott***at***clemson.edu)
Banu Soylu(bsoylu***at***erciyes.edu.tr)
Margaret Wiecek(wmalgor***at***clemson.edu)

Abstract: We propose a branch-and-bound (BB) algorithm for biobjective mixed-integer linear programs (BOMILPs). Our approach makes no assumption on the type of problem and we prove that it returns all Pareto points of a BOMILP. We discuss two techniques upon which the BB is based: fathoming rules to eliminate those subproblems that are guaranteed not to contain Pareto points and a procedure to explore a subproblem based on the parametric simplex method. The BB algorithm starts with an initial set of feasible points that evolves toward the Pareto set of the BOMILP. This set is gradually modified by including new points and eliminating dominated points, and, upon termination, it is identical to the Pareto set. We provide computational results on instances of various sizes to prove the effectiveness of our algorithm.

Keywords: Biobjective programming, mixed-integer linear programming, fathoming rules, branch and bound.

Category 1: Other Topics (Multi-Criteria Optimization )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 12/29/2012
Entry Accepted: 01/01/2013
Entry Last Modified: 12/29/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society