Optimization Online


Branch-and-bound for biobjective mixed-integer programming

Nathan Adelgren(nadelgren***at***edinboro.edu)
Akshay Gupte(agupte***at***clemson.edu)

Abstract: We present a generic branch-and-bound method for finding all the Pareto solutions of a biobjective mixed integer program. Our main contribution is new algorithms for obtaining dual bounds at a node, for checking node fathoming, presolve and duality gap measurement. Our various procedures are implemented and empirically validated on instances from literature and a new set of hard instances. We also perform comparisons against the triangle splitting method of Boland, Charkhgard, and Savelsbergh [INFORMS Journal on Computing, 27 (4), 2015], which is a objective space search algorithm as opposed to our variable space search algorithm. On each of the literature instances, our branch-and-bound is able to compute the entire Pareto set in significantly lesser time. Most of the instances of the harder problem set were not solved by either algorithm in a reasonable time limit, but our algorithm performs better on average on the instances that were solved.

Keywords: Branch-and-bound, Mixed-integer, Multiobjective, Pareto solutions

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

Category 2: Other Topics (Multi-Criteria Optimization )

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: submitted for publication

Download: [PDF]

Entry Submitted: 10/20/2016
Entry Accepted: 10/20/2016
Entry Last Modified: 10/20/2016

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