A reduction dynamic programming algorithm for the bi-objective integer knapsack problem

Aiying Rong

doi:10.1016/j.ejor.2013.05.045

Return

A reduction dynamic programming algorithm for the bi-objective integer knapsack problem

2013-12-01

PRE

Aiying Rong *

José Rui Figueira

DOI：10.1016/j.ejor.2013.05.045

Original

Original request for help

Save

Abstract

En 中文

This paper presents a backward state reduction dynamic programming algorithm for generating the exact Pareto frontier for the hi-objective integer knapsack problem. The algorithm is developed addressing a reduced problem built after applying variable fixing techniques based on the core concept. First, an approximate core is obtained by eliminating dominated items. Second, the items included in the approximate core are subject to the reduction of the upper bounds by applying a set of weighted-sum functions associated with the efficient extreme solutions of the linear relaxation of the multi-objective integer knapsack problem. Third, the items are classified according to the values of their upper bounds; items with zero upper bounds can be eliminated. Finally, the remaining items are used to form a mixed network with different upper bounds. The numerical results obtained from different types of bi-objective instances show the effectiveness of the mixed network and associated dynamic programming algorithm. (C) 2013 Elsevier B.V. All rights reserved.

Keywords:

Multi-objective programming

Integer knapsack problem

Dynamic programming

Dominance relation

Core concept

State reduction

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.