Re: Optimisation in Reverse Auctions (Price combinations)

On Oct 21, 7:35 am, Merrows <tre...@xxxxxxxxxxxxx> wrote:
I accidently posted in sci.physics.

I have a rather simple problem but I am a bit out of practice with
handling this kind of optimisation problem. I wonder if anyone can
help.

I am setting up a website for reverse auctions, which means the buyer
gets the lowest price on a shopping cart of new items based on
reseller prices. The resellers in effect bid via sealed bids and
everything is handled electronically.

This is the problem:

Buyer (B) adds items I (i=1..n) into a shoppint cart. Each item is
sold by different resellers (R(j=1..m)), and each reseller has a
delivery charge D(Rj).
P - Reseller Price, R- reseller, I - Item, D- Fixed Charge PER ORDER
for a reseller
So in the simple case of several resellers reselling ALL the cart
items we have:
Optimal Cost = min SUM ij C(Rj,Ii) + D (Rj)

The issue arises when there are several resellers reselling goods at
different discounts within their lines and the charge D varies and
therefore a big price discount on one item is less important than
another.

if D is ignored
Optimal Cost = SUM i (min C(Rj,Ii))

But when the D(Rj) cost is included, I cannot see easily how the cost
is optimised. This is because the totals for the prices must first be
computed to find out the best price, but that calculation cannot
explicitly handle the delivery charge as there are combinations of
what is possible.

eg Items 1 2 3 are sold.

And R1 sells 1,2 and not 3. R2 sells 2,3, R3 sells 3, R4 sells 1,2,3

So we have a choice of R3 over R2 and therefore using R2 for Item 2
and R3 for Item 3 or other combinations.

It is gets complicated very quickly.

I am implementing this in a computer program.

Any help is welcome.

This is essentially a fixed-charge network flow problem. It can be
formulated as a mixed-integer programming problem as follows. The
binary variables y_j describe whether or not seller j is used at all
(1 if so, 0 if not); the continuous variable x_{i,j} is the amount of
item i sold by seller j. Of course, x_{i,j} must also be binary, but
this will automatically hold at the solution of the problem, because
for any given binaries y_j the resulting x-problem is a network flow
problem with integer supplies and demands; hence (by a fundamental
theorem) the optimal flow will also be integer, and the constraints
limit the values to 0 <= x <= 1, hence to x = 0 or 1 at the optimum.
We have a variable x_{i,j} defined only for certain allowed i,j pairs.
The objective to be minimized is sum_j D_j * y_j + sum_{i,j} c_{i,j} *
x_{i,j}, where D_j = fixed cost of using seller j and c_{i,j} =
additional cost of selling item i at seller j. The constraints are:
sum_j x_{i,j} = 1 for all i (sell 1 unit of item i) and x_{i,j} <= y_j
for all i,j (can sell i at j only if j is used). Alternatively, we can
use a single constraint for each seller j: sum_i x_{i,j} <= n_j * y_j
for all j; here n_j = number of items seller j can sell;
alternatively, wel can use n instead of individual n_j values.
Finally, we have y_j = 0 or 1 for all j and 0 <= x_{i,j} <= 1 for all
i,j. We can drop the constraint x <= 1 because it is implied by the
sum constraint sum_j x = 1, provided that we keep the x >= 0
constraint. We can often drop this, too, because many packages /
assume/ non-negative variables unless specifically told otherwise.

For your 2-item, 4-seller example above I have just invented some
fixed costs and variable selling costs and formulated the problem in
LINGO 11. Here is the LINGO input, the generated model and the
solution:

Input:
1]MODEL:
2]
3]! This is a comment. A comment can occupy several lines.
4] It starts with an exclamation mark and ends with
5] a semi-colon;
6]
7]SETS:
8] Item/I1..I3/;
9] Seller/S1..S4/: Y, D ;
10]! Y = 0,1 variable for using the seller or not and
11] D = fixed cost of that seller;
12] Allowed(Item,Seller)/I1 S1, I2 S1,
13] I2 S2, I3 S2,
14] I3 S3,
15] I1 S4, I2 S4, I3 S4/: X, C;
16]!X(i,j) = amount of item i sold by seller j and
17]c(i,j) = unit cost of
18]item-seller combination;
19]
20]ENDSETS
21]
22]DATA:
23]! fixed seller costs in order are as follows;
24] D = 2 1 2 4;
25]! unit costs in order of Allowed definition above
26] are as follows;
27] C = 2 3 4 1 1 3 2 1;
28]ENDDATA
29]! Total cost objective is the following;
30]
31]MIN = @SUM(Seller(J):
32] D(J)*Y(J)) + @SUM(allowed(I,J): C(I,J)*X(I,J)
33] );
34]! j can sell i only if j is "open";
35]@FOR(allowed(I,J):
36] X(I,J) <= Y(J)
37] );
38]
39]! exactly one unit of item i is sold;
40]@FOR(Item(I):
41] @SUM(allowed(I,J): X(I,J)) = 1
42] );
43]
44]! binary variables y(j);
45]@FOR(Seller(J):
46] @BIN(Y(J))
47] );
48]
49]END

The generated model is:

MODEL:
[_1] MIN= 2 * X_I1_S1 + 3 * X_I2_S1 + 4 * X_I2_S2 + X_I3_S2 +
X_I3_S3 +
3 * X_I1_S4 + 2 * X_I2_S4 + X_I3_S4 + 2 * Y_S1 + Y_S2 + 2 * Y_S3 +
4 *
Y_S4 ;
[_2] X_I1_S1 - Y_S1 <= 0 ;
[_3] X_I2_S1 - Y_S1 <= 0 ;
[_4] X_I2_S2 - Y_S2 <= 0 ;
[_5] X_I3_S2 - Y_S2 <= 0 ;
[_6] X_I3_S3 - Y_S3 <= 0 ;
[_7] X_I1_S4 - Y_S4 <= 0 ;
[_8] X_I2_S4 - Y_S4 <= 0 ;
[_9] X_I3_S4 - Y_S4 <= 0 ;
[_10] X_I1_S1 + X_I1_S4 = 1 ;
[_11] X_I2_S1 + X_I2_S2 + X_I2_S4 = 1 ;
[_12] X_I3_S2 + X_I3_S3 + X_I3_S4 = 1 ;
@BIN( Y_S1); @BIN( Y_S2); @BIN( Y_S3); @BIN( Y_S4);
END

The (edited) solution report is:

Global optimal solution found.
Objective value: 9.000000
Objective bound: 9.000000
Infeasibilities: 0.000000
Extended solver steps: 0
Total solver iterations: 8


Variable Value Reduced Cost
Y( S1) 1.000000 2.000000
Y( S2) 1.000000 1.000000
Y( S3) 0.000000 2.000000
Y( S4) 0.000000 3.000000
X( I1, S1) 1.000000 0.000000
X( I2, S1) 1.000000 0.000000
X( I2, S2) 0.000000 1.000000
X( I3, S2) 1.000000 0.000000
X( I3, S3) 0.000000 0.000000
X( I1, S4) 0.000000 1.000000
X( I2, S4) 0.000000 0.000000
X( I3, S4) 0.000000 0.000000

So, use sellers 1 and 2; use seller 1 for items 1 and 2 and seller 2
for item 3.

Note: we entered the data directly, but we could have imported it from
a spread*** or some other type of file.

You can also formulate and solve the problem using the EXCEL Solver,
but sometimes (rarely) the Solver is found to be unreliable on integer-
programming problems. You can download a free "demonstration" version
of LINGO from the LINDO Corp. website. I think it can handle up to
about 20-30 sellers and a few hundred seller-item combinations.
Similarly sized problems, perhaps even a bit larger, can be solved
using the default version of the Solver that comes bundled with EXCEL;
however, it may need to be 'installed' first.

R.G. Vickson
.

Quantcast