Hello,
I am trying to calculate the O’Neill prices for the individual atoms in a
combinatorial auction.
The method is:
1) Solve the IP to find the optimal allocation.
2) Remove the integer constraints and for each positively valued optimal
integer variable from the IP solution construct an equality constraint
to the optimal value. The LP of the new problem has the same optimal solution
as the initial IP.
3) Solve the dual of the new IP.
4) The dual variables corresponding to the integer variables are used in
another optimization for the prices vector.
Due to my lack of experience in linear programming, I believe I am making a
mistake in step 3. I have been using the example from chapter 3.2 of [1]Pricing
combinatorial auctions.
In the example there are 4 bids:
([1,1,0], 30)
([0,1,1], 30)
([1,0,1], 30)
([1,1,1], 39)
where w is the participation quantity vector for the 3 assets (i.e in the first
bid above the bid is for assets 1 and 2 and valuation 30).
The winner determination problem (WDP) is as follows:
Maximize: SUM(p_i*x_i) for all orders n
Subject to:
SUM(w1_i*x_i) <= 1 for all orders
SUM(w2_i*x_i) <= 1 for all orders
SUM(w3_i*x_i) <= 1 for all orders
x in {0,1}
i in {1…n}
(For each asset we have maximum supply of 1)
The IP solution of the above problem is 39 with x1=0, x2=0, x3=0, x4=1 (below
is the AMPL model I used to test that) which is in line with what was presented
in
3.2 of [1]Pricing combinatorial auctions. However, when it comes to solving the
dual I am probably making a mistake –
I remove the integer constraint and add the x[4]=1 solving the LP with GLPSOL:
glpsol -m wdpSingle.mod -d test.dat -o out.txt --ranges ranges.txt
My understanding was that the “Marginal” values for the x variables are the
dual values I am interested in, however what I get is x[1]=-30 x[2]=. x[3]=.
x[4]=.
This is different than what was presented in the example in 3.2 of Pricing
combinatorial auctions where thy used values 12, 0, 0, 0 in the next
optimization.
As a novice in linear programming I find the explanation and example in the
above mentioned paper difficult to follow due to the ambiguity for how they
obtained the “g” values in their example which were next used in calculating
the prices for the atoms.
I would greatly appreciate any hints and advices on this matter. Perhaps I am
misunderstanding the term “dual” in the context of that example.
Thanks for the help.
Kind regards
Kiril
Model:
param noOrds;
set assets;
param ords {1..noOrds, assets};
param prices {1..noOrds};
var x {1..noOrds} integer >= 0;
maximize T: sum{i in 1..noOrds} prices[i]*x[i];
subject to supply {a in assets}: sum{i in 1..noOrds} ords[i,a]*x[i] <= 1;
Data:
param noOrds := 4;
set assets := A, B, C;
param ords :
A B C :=
1 1 1 0
2 0 1 1
3 1 0 1
4 1 1 1;
param prices :=
1 30
2 30
3 30
4 39;
[1] Pricing combinatorial auctions
European Journal of Operational Research, Volume 154, Issue 1, Pages 251-270
Mu Xia, Gary J. Koehler, Andrew B. Whinston
http://www.sciencedirect.com/science/article/pii/S0377221702006781
(Unfortunately I can’t find a free link – it doesn’t have a paywall accessing
form university networks)
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
