Dynamic programming algorithms for the hi-objective integer knapsack problem

Aiying Rong

doi:10.1016/j.ejor.2013.11.032

Return

Dynamic programming algorithms for the hi-objective integer knapsack problem

2014-07-01

PRE

Aiying Rong *

José Rui Figueira

DOI：10.1016/j.ejor.2013.11.032

Original

Original request for help

Save

Abstract

En 中文

This paper presents two new dynamic programming (DP) algorithms to find the exact Pareto frontier for the bi-objective integer knapsack problem. First, a property of the traditional DP algorithm for the multi-objective integer knapsack problem is identified. The first algorithm is developed by directly using the property. The second algorithm is a hybrid DP approach using the concept of the bound sets. The property is used in conjunction with the bound sets. Next, the numerical experiments showed that a promising partial solution can be sometimes discarded if the solutions of the linear relaxation for the subproblem associated with the partial solution are directly used to estimate an upper bound set. It means that the upper bound set is underestimated. Then, an extended upper bound set is proposed on the basis of the set of linear relaxation solutions. The efficiency of the hybrid algorithm is improved by tightening the proposed upper bound set. The numerical results obtained from different types of bi-objective instances show the effectiveness of the proposed approach. (C) 2013 Elsevier B.V. All rights reserved.

Keywords:

Multi-objective optimization

Integer knapsack problems

Dynamic programming

Bound sets

AI Summary

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