Pricing the multiple-choice nested knapsack problem

Andreas Drexl and Kurt Jörnsten

No 626, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre

Abstract: The multiple-choice nested knapsack problem (MCKP) is a generalization of the ordinary knapsack problem, where the set of items is partitioned into classes. The binary choice of selecting an item is replaced by taking exactly one item out of each class of items. Due to the fact that the MCKP is an NP-hard integer program dual prices are not readily available. In this paper we propose a family of linear programming models the optimal solution of which is integral for many instances. The models are evaluated experimentally using a well-defined testbed consisting of 9,000 instances. Overall our methodology produces an integral solution for 75% of the instances considered. In particular, for two out of five distribution types studied at least one of the models produces "almost always" an integral solution. Hence, in most of the cases there exists a linear price function that supports the optimal allocation.

Keywords: Knapsack problem; multiple-choice constraints; integer programming; duality; linear programming; pricing (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.econstor.eu/bitstream/10419/147679/1/manuskript_626.pdf (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:zbw:cauman:626

Access Statistics for this paper

More papers in Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre Contact information at EDIRC.
Bibliographic data for series maintained by ZBW - Leibniz Information Centre for Economics ().