Network Models for Multiobjective Discrete Optimization

David Bergman (), Merve Bodur (), Carlos Cardonha () and Andre A. Cire ()
Additional contact information
David Bergman: Department of Operations and Information Management, University of Connecticut, Stamford, Connecticut 06901
Merve Bodur: Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada
Carlos Cardonha: Department of Operations and Information Management, University of Connecticut, Storrs, Connecticut 06269
Andre A. Cire: Department of Management, Scarborough & Rotman School of Management, University of Toronto, Toronto, Ontario M1C 1A4, Canada

INFORMS Journal on Computing, 2022, vol. 34, issue 2, 990-1005

Abstract: This paper provides a novel framework for solving multiobjective discrete optimization problems with an arbitrary number of objectives. Our framework represents 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 techniques for exploiting network models 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 five problem classes containing both linear and nonlinear objective functions. Summary of Contribution: Multiobjective optimization has a long history of research with applications in several domains. Our paper provides an alternative modeling and solution approach for multiobjective discrete optimization problems by leveraging graphical structures. Specifically, we encode the decision space of a problem as a layered network and propose graph reduction operators to preserve only solutions whose image are part of the Pareto frontier. The nondominated solutions can then be extracted through shortest-path algorithms on such a network. Numerical results comparing our method with state-of-the-art approaches on several problem classes, including the knapsack, set covering, and the traveling salesperson problem (TSP), suggest orders-of-magnitude runtime speed-ups for exactly enumerating the Pareto frontier, especially when the number of objective functions grows.

Keywords: decision analysis; multiple criteria; dynamic programming; generalized networks; integer programming (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1066 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:2:p:990-1005

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().