Optimization Online


Network Models for Multiobjective Discrete Optimization

David Bergman (david.bergman***at***business.uconn.edu)
Merve Bodur (bodur***at***mie.utoronto.ca)
Carlos Cardonha (carloscardonha***at***br.ibm.com)
Andre Cire (acire***at***utsc.utoronto.ca)

Abstract: This paper provides a novel framework for solving multiobjective discrete optimization problems with an arbitrary number of objectives. Our framework formulates these problems as network models, in that enumerating the Pareto frontier amounts to solving a multicriteria shortest path problem in an auxiliary network. We design tools and techniques for exploiting the network model in order to accelerate the identification of the Pareto frontier, most notably a number of operations to simplify the network by removing nodes and arcs while preserving the set of nondominated solutions. We show that the proposed framework yields orders-of-magnitude performance improvements over existing state-of-the-art algorithms on four problem classes containing both linear and nonlinear objective functions.

Keywords: Multicriteria decision making; multiobjective discrete optimization; 0-1 programming; Pareto frontier; network models

Category 1: Other Topics (Multi-Criteria Optimization )

Category 2: Integer Programming (0-1 Programming )

Category 3: Other Topics (Dynamic Programming )


Download: [PDF]

Entry Submitted: 02/22/2018
Entry Accepted: 02/22/2018
Entry Last Modified: 08/29/2018

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