Optimization Online


Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems

Audrey Cerqueus(audrey.cerqueus***at***univ-nantes.fr)
Anthony Przybylski(anthony.przybylski***at***univ-nantes.fr)
Xavier Gandibleux(xavier.gandibleux***at***univ-nantes.fr)

Abstract: The paper deals with the definition and the computation of surrogate upper bound sets for the bi-objective bi-dimensional binary knapsack problem. It introduces the Optimal Convex Surrogate Upper Bound set, which is the tightest possible definition based on the convex relaxation of the surrogate relaxation. Two exact algorithms are proposed: an enumerative algorithm and its improved version. This second algorithm results from an accurate analysis of the surrogate multipliers and the dominance relations between bound sets. Based on the improved exact algorithm, an approximated version is derived. The proposed algorithms are benchmarked using a dataset composed of three groups of numerical instances. The performances are assessed thanks to a comparative analysis where exact algorithms are compared between them, the approximated algorithm is confronted to an algorithm introduced in a recent research work.

Keywords: combinatorial optimization, multiple objective programming, bi-dimensional binary knapsack problem, surrogate relaxation, bound sets

Category 1: Other Topics (Multi-Criteria Optimization )

Category 2: Combinatorial Optimization (Other )

Citation: Mars 2014 Université de Nantes LINA UMR CNRS 6241 UFR sciences – 2 Rue de la Houssinière BP 92208 F-44322 Nantes Cedex 03 – France

Download: [PDF]

Entry Submitted: 04/08/2014
Entry Accepted: 04/08/2014
Entry Last Modified: 04/08/2014

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