An improved algorithm for solving biobjective integer programs

Autor:	Matthew J. Saltzman, Margaret M. Wiecek, Ted K. Ralphs
Rok vydání:	2006
Předmět:	Set (abstract data type) Mathematical optimization Asymptotically optimal algorithm Knapsack problem Theory of computation Pareto principle General Decision Sciences Management Science and Operations Research Chebyshev filter Integer (computer science) Parametric statistics Mathematics
Zdroj:	Annals of Operations Research. 147:43-70
ISSN:	1572-9338 0254-5330
Popis:	A parametric algorithm for identifying the Pareto set of a biobjective integer program is proposed. The algorithm is based on the weighted Chebyshev (Tchebycheff) scalarization, and its running time is asymptotically optimal. A number of extensions are described, including: a technique for handling weakly dominated outcomes, a Pareto set approximation scheme, and an interactive version that provides access to all Pareto outcomes. Extensive computational tests on instances of the biobjective knapsack problem and a capacitated network routing problem are presented.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::a90b65a660309323d537e7e43306c271 https://doi.org/10.1007/s10479-006-0058-z Zobrazit plný text záznamu Plný text ve formátu PDF