Optimization Online


Bi-objective branch--and--cut algorithms: Applications to the single source capacitated facility location problem

S.L. Gadegaard (sgadegaard***at***econ.au.dk)
M. Ehrgott (m.ehrgott***at***lancaster.ac.uk)
L.R. Nielsen (larsrn***at***econ.au.dk)

Abstract: Most real--world optimization problems are of a multi--objective nature, involving objectives which are conflicting and incomparable. Solving a multi--objective optimization problem requires a method which can generate the set of rational compromises between the objectives. In this paper, we propose two distinct bound set based branch--and--cut algorithms for bi--objective combinatorial optimization problems, based on implicitly and explicitly stated lower bound sets, respectively. The algorithm based on explicitly given lower bound sets computes for each branching node a lower bound set and compares it to an upper bound set. The implicit bound set based algorithm, on the other hand, fathoms branching nodes by generating a single point on the lower bound set for each local nadir point. We outline several approaches for fathoming branching nodes and we propose an updating scheme for the lower bound sets that prevents us from solving the bi-objective LP-relaxation of each branching node. To strengthen the lower bound sets, we propose a bi-objective cutting plane algorithm that dynamically adjusts the weights of the objective functions such that different parts of the feasible set are strengthened by cutting planes. In addition, we suggest an extension of the branching strategy ``Pareto branching''. Extensive computational results obtained for the bi--objective single source capacitated facility location problem prove the effectiveness of the algorithms.

Keywords: bi--objective branch--and--cut, bi--objective optimization, combinatorial optimization, branch--and--cut

Category 1: Other Topics (Multi-Criteria Optimization )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 04/11/2016
Entry Accepted: 04/11/2016
Entry Last Modified: 04/12/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