Question

A combinatorial auction allows participants to make bids on items in either individual or grouped quantities. Suppose an auctioneer has 4 items. There are 6 bidders who bid the following:

Bidder 1: $6 for item 1

Bidder 2: $3 for item 2

Bidder 3: $12 total for items 3 and 4

Bidder 4: $12 total for items 1 and 3

Bidder 5: $8 total for items 2 and 4

Bidder 6: $16 total for items 1, 2, and 4

Each item can only go to at most one participant. If a bidder won the bid on multiple items, they must receive all of them.

formula a linear Integer Program that helps the auctioneer maximize revenue. Clearly define all decision variables and constraints.

Answer 1

Linear Integer Programming:

Decision Variable: Let Xij be the units received by the bidder i for item j.

Decision Variables	Item 1	Item 2	Item 3	Item 4
Bidder 1	X11	X12	X13	X14
Bidder 2	X21	X22	X23	X24
Bidder 3	X31	X32	X33	X34
Bidder 4	X41	X42	X43	X44
Bidder 5	X51	X52	X53	X54
Bidder 6	X61	X62	X63	X64

Objective Function : Maximize the revenue for auctioneer.

Zmax = 6X11+3X22+12*(X33+X34)+12*(X41+X43)+8*(X52+X54)+16*(X61+X62+X64)

Constraints:

If a bidder wins bid for multiple products, all of to be delivered

X33 = X34

X41=X43

X52=X54

X61=X62

X62=X64

Item i can be received by at most one bidder:

Sum of X11 to X61<=1

Sum of X12 to X62<=1

Sum of X13 to X63<=1

Sum of X14 to X64<=1

Xij is an integer.

Solving the LP in solver:

Solver Parameters:

The objective function, changing variables cell references re given in the solver parameters.

The constraints are added.

In case of multiple wins the bidder has to receive all of the items, hence each of the item qty received should be same for one bidder. either 1 or 0.

Solving the LP, solutions:

Answer: Objective =48

Items received:

Decision Variables	Item 1	Item 2	Item 3	Item 4
Bidder 1	0	0	1	0
Bidder 2	0	0	0	0
Bidder 3	0	0	0	0
Bidder 4	0	0	0	0
Bidder 5	0	0	0	0
Bidder 6	1	1	0	1

All values showing 1 are the corresponding items received by the respective bidder 0 shows not received.