A branch-and-bound algorithm for biobjective mixed-integer programs
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 )
Entry Submitted: 12/29/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|