IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v42y1996i11p1565-1575.html
   My bibliography  Save this article

Parametric Solution for Linear Bicriteria Knapsack Models

Author

Listed:
  • Moshe Eben-Chaime

    (Department of Industrial Engineering & Management, Ben-Gurion University of the Negev, 84105 Be'er Sheva, Israel)

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.

Suggested Citation

  • Moshe Eben-Chaime, 1996. "Parametric Solution for Linear Bicriteria Knapsack Models," Management Science, INFORMS, vol. 42(11), pages 1565-1575, November.
    • Handle: RePEc:inm:ormnsc:v:42:y:1996:i:11:p:1565-1575
    DOI: 10.1287/mnsc.42.11.1565
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.42.11.1565
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.42.11.1565?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Nir Halman & Mikhail Y. Kovalyov & Alain Quilliot, 2023. "Max–max, max–min, min–max and min–min knapsack problems with a parametric constraint," 4OR, Springer, vol. 21(2), pages 235-246, June.
    2. George Kozanidis, 2009. "Solving the linear multiple choice knapsack problem with two objectives: profit and equity," Computational Optimization and Applications, Springer, vol. 43(2), pages 261-294, June.
    3. Altannar Chinchuluun & Panos Pardalos, 2007. "A survey of recent developments in multiobjective optimization," Annals of Operations Research, Springer, vol. 154(1), pages 29-50, October.
    4. Yang, Ming-Hsien, 2001. "An efficient algorithm to allocate shelf space," European Journal of Operational Research, Elsevier, vol. 131(1), pages 107-118, May.
    5. Stephan Helfrich & Arne Herzel & Stefan Ruzika & Clemens Thielen, 2022. "An approximation algorithm for a general class of multi-parametric optimization problems," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 1459-1494, October.
    6. Jenkins, Larry, 2002. "A bicriteria knapsack program for planning remediation of contaminated lightstation sites," European Journal of Operational Research, Elsevier, vol. 140(2), pages 427-433, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:42:y:1996:i:11:p:1565-1575. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.