Combinatorial Optimization - Variation on Knapsack

Here is a real-world combinatorial optimization problem.

We are given a large set of value propositions for a certain product. The value propositions are of different types but each type is independent and adds equal benefit to the overall product. In building the product, we can include any non-negative integer number of "units" of eac开发者_C百科h type. However, after adding the first unit of a certain type, the marginal benefit of additional units of that type continually decreases. In fact, the marginal benefit of a new unit is the inverse of the number of units of that type, after adding the new unit. Our product must have a least one unit of some type, and there is a small correction that we must make to the overall value because of this requirement.

Let T[] be an array representing the number of each type in a certain production run of the product. Then the overall value V is given by (pseudo code):

V = 1
For Each t in T
    V = V * (t + 1)
Next t
V = V - 1 // correction

On cost side, units of the same type have the same cost. But units of different types each have unique, irrational costs. The number of types is large, but we are given an array of type costs C[] that is sorted from smallest to largest. Let's further assume that the type quantity array T[] is also sorted by cost from smallest to largest. Then the overall cost U is simply the sum of each unit cost:

U = 0
For i = 0, i < NumOfValueTypes
    U = U + T[i] * C[i]
Next i

So far so good. So here is the problem: Given product P with value V and cost U, find the product Q with the cost U' and value V', having the minimal U' such that U' > U, V'/U' > V/U.

The problem you've described is nonlinear integer programming problem because it contains a product of integer variables t. Its feasibility set is not closed because of strict inequalities which can be worked around by using non-strict inequalities and adding a small positive number (epsilon) to the right hand sides. Then the problem can be formulated in AMPL as follows:

set Types;
param Costs{Types};      # C
param GivenProductValue; # V
param GivenProductCost;  # U
param Epsilon;

var units{Types} integer >= 0; # T
var productCost = sum {t in Types} units[t] * Costs[t];

minimize cost: productCost;
s.t. greaterCost: productCost >= GivenProductCost + Epsilon;
s.t. greaterValuePerCost:
  prod {t in Types} (units[t] + 1) - 1 >=
    productCost * GivenProductValue / GivenProductCost + Epsilon;

This problem can be solved using a nonlinear integer programming solver such as Couenne.

Honestly I don't think there is an easy way to solve this. The best thing would be to write the system and solve it with a solver ( Excel solver will do the tricks, but you can use Ampl to solve this non lienar program.)

The Program:

Define: U;
        V;
        C=[c1,...cn];

Variables: T=[t1,t2,...tn];

Objective Function: SUM(ti.ci)

Constraints:

For all i: ti integer
SUM(ti.ci) > U 
(PROD(ti+1)-1).U > V.SUM(ti.ci)

It works well with excel, (you just replace >U by >=U+d where d is the significative number of the costs- (i.e if C=[1.1, 1.8, 3.0, 9.3] d =0.1) since excel doesn't allow stric inequalities in the solver.)

I guess with a real solver like Ampl it will work perfectly.

Hope it helps,