Greedy Heuristics and Weight-Coded EAs for Multidimensional Knapsack Problems and Multi-Unit Combinatorial Auctions

Jella Pfeiffer () and Franz Rothlauf ()
Additional contact information
Jella Pfeiffer: University Mainz
Franz Rothlauf: University Mainz

A chapter in Operations Research Proceedings 2007, 2008, pp 153-158 from Springer

Abstract: Abstract The multidimensional knapsack problem (MDKP) is a generalized variant of the $$ \mathcal{N}\mathcal{P} $$ -complete knapsack problem (KP). The MDKP assumes one knapsack being packed with a number of items x j so that the total profit Σpj of the selected items is maximized. In contrast to the standard KP, each item has m different properties (dimensions) r ij (i = 1, ...,m; j = 1, ..., n) consuming c i of the knapsack: 1 $$ maximize{\text{ }}\sum\limits_{j{\text{ = 1}}}^n {p_j x_j } $$ 2 $$ \begin{gathered} subject\ to \sum\limits_{j = 1}^n {r_{ij} x_j} \leqslant c_i ,i = 1,...,m \\ with\; x_j \in \{0,1\} ,j = 1,...,n, p_j ,c_i \in \mathbb{N}, r_{ij} \in \mathbb{N}_0 \end{gathered} $$ A number of relevant real-world problems can be modelled as MDKPs such as allocation problems, logistics problems, or cutting stock problems [6]. Recently [4], it has been noticed that also the winner determination problem (WDP) in the context of multi-unit combinatorial auctions (MUCA) can be modelled as MDKP. MUCAs are combinatorial auctions (CA) where multiple copies of each good are available. In CAs, bidding is allowed on bundles of goods, which allows bidders to express synergies between those goods they want to obtain. First, the agents submit their bids and then, the auctioneer allocates the goods to the agents so that his revenue is maximized. The revenue is the sum of all submitted bids which are accepted by the auctioneer. This allocation problem is called the WDP1.

Keywords: Knapsack Problem; Greedy Heuristic; Combinatorial Auction; Heuristic Optimization; Stochastic Local Search (search for similar items in EconPapers)
Date: 2008
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:oprchp:978-3-540-77903-2_24

Ordering information: This item can be ordered from
http://www.springer.com/9783540779032

DOI: 10.1007/978-3-540-77903-2_24

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().