Parametric Solution for Linear Bicriteria Knapsack Models

Moshe Eben-Chaime
Additional contact information
Moshe Eben-Chaime: Department of Industrial Engineering & Management, Ben-Gurion University of the Negev, 84105 Be'er Sheva, Israel

Management Science, 1996, vol. 42, issue 11, 1565-1575

Abstract: Linear weighing is a common approach to handle multiple criteria and the "knapsack" is a well-known combinatorial optimization problem. A knapsack problem with two linearly weighted, objective criteria is considered in this paper. For better support, it is important to provide the decision maker with information that covers the whole range of alternatives. Toward this goal, an algorithm for the construction of a parametric solution to the problem, i.e., for any combination of weights, is developed, which is based on finding a longest path in a network which compactly represents all feasible solutions to the knapsack problem. Exploiting the special structure of the knapsack model, the algorithm efficiently constructs the parametric solution in time that is linear in the product of the number of variables, the resource limit (right-hand side of the constraint), and the (finite) number of vectors which constitute the solution. The amount of memory required is linear in the product of the number of variables and the resource limit. Results of computational study are reported. The results are used to assess the efficiency of the algorithm and characterize its behavior with respect to the parameter values.

Keywords: programming-multiple criteria; solution for linear-bicriteria knapsack problems; network/graphs-applications; of the shortest path model (search for similar items in EconPapers)
Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.42.11.1565 (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:ormnsc:v:42:y:1996:i:11:p:1565-1575

Access Statistics for this article

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