$
$ Combinatorial auction problem in Essence'.
$
$
$ http://en.wikipedia.org/wiki/Combinatorial_auction
$ """
$ A combinatorial auction is an auction in which bidders can place
$ bids on combinations of items, or "packages," rather than
$ just individual items. Simple combinatorial auctions have been
$ used for many years in estate auctions, where a common procedure
$ is to auction the individual items and then at the end to accept
$ bids for packages of items.
$ """
$
$
$ This simple example is from the lecture slides
$ Constraint Satisfaction Problems, Constraint Optimization
$ by Bernhard Nebel and Stefan Wölfl
$ http://www.informatik.uni-freiburg.de/~ki/teaching/ws0910/csp/csp10-handout4.pdf
$ """
$ In combinatorial auctions, bidders can give bids for set of items.
$ The auctioneer [then] has to generate an optimial selection, e.g.
$ one that maximizes revenue.
$
$ Definition
$ The combinatorial auction problem is specified as follows:
$ Given: A set of items Q = {q1,...,qn} and a set of bids
$ B = {b1,...,bm} such that each bid is bi = (Qi, ri),
$ where Qi (= Q and ri is a strictly positive real number.
$ Task: Find a subset of bids B'(= B such that any two bids in B'
$ do not share an item maximizing Sum(Qi,ri) (= Biri.
$
$ ...
$
$ Example Auction
$
$ Consider the following auction:
$ b1 = {1,2,3,4}, r1 = 8
$ b2 = {2,3,6}, r2 = 6
$ b3 = {1,4,5}, r3 = 5
$ b4 = {2,8}, r4 = 2
$ b5 = {5,6}, r5 = 2
$
$ What is the optimal assignment?
$ """
$
$ Model created by Hakan Kjellerstrand, hakank@gmail.com
$ See also my Essence'/Savile Row page: http://www.hakank.org/savile_row/
$
language ESSENCE' 1.0
letting num_items be 7
letting num_bids be 5
letting max_item be 7
letting packages =
[
$ {1,2,3,4},
[1,1,1,1,0,0,0],
$ {2,3,6},
[0,1,1,0,0,1,0],
$ {1,4,5},
[1,0,0,1,1,0,0],
$ {2,7},
[0,1,0,0,0,0,1],
$ {5,6},
[0,0,0,0,1,1,0]
]
letting bids be [8,6,5,2,2]
find x: matrix indexed by [int(1..num_bids)] of int(0..1)
find total: int(0..1000)
maximising total
such that
total = sum i: int(1..num_bids) . x[i]*bids[i],
$ ensure that each items is selected atmost once
forAll j: int(1..num_items) .
(sum i: int(1..num_bids) . x[i]*packages[i,j]) <= 1