Optimization Online


Branch-and-bound for bi-objective integer programming

Sophie N. Parragh (sophie.parragh***at***univie.ac.at)
Fabien Tricoire (fabien.tricoire***at***univie.ac.at)

Abstract: In Pareto bi-objective integer optimization the optimal result corresponds to a set of non- dominated solutions. We propose a generic bi-objective branch-and-bound algorithm that uses a problem-independent branching rule exploiting available integer solutions, and cutting plane generation taking advantage of integer objective values. The developed algorithm is applied to the bi-objective team orienteering problem with time windows, considering two minimization objectives. Lower bound sets are computed by means of column generation, while initial upper bound sets are generated by means of multi-directional local search. Comparison to using the same ingredients in an ε-constraint scheme shows the effectiveness of the proposed branch-and-bound algorithm.

Keywords: bi-objective branch-and-bound, column generation, cutting planes, branch-and-price, orienteering

Category 1: Other Topics (Multi-Criteria Optimization )

Category 2: Combinatorial Optimization

Category 3: Integer Programming


Download: [PDF]

Entry Submitted: 07/15/2014
Entry Accepted: 07/15/2014
Entry Last Modified: 01/21/2015

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