Search code examples
linear-programmingknapsack-problemamplglpk

Combinatorial optimization with multiple constraints

I have a problem which involves gear optimization in a game, but i'll simplify it with this example:

  • Let's say i have 4 bags.
  • I have a set of different items, of 4 types.
  • Each item has its weight and price.
  • Each bag is for one type of item, 4 bags - 4 types.


I want to maximize the price i carry in all bags, but i have the following constraints:

  1. Each bag can hold at most 6 items. It can be empty too.
  2. Total weight of all 4 bags must not exceed 700kg.
  3. Each bag has a min weight value, even if it's empty it will count as 50kg (a bag with 1 item of 25kg will still count as 50kg, a bag with 1 item of 51kg will count as 51kg).

The range of the number of items it's 200~300, and with 6*4=24 max items that can be choosen, it's impossible to brute force.

There are other factors, but those are outside of the combinatorial problem and can be solved by simple programming


What kind of problem is this? Is it a subset of linear programming?
Do you know what kind of algorithm i can reasearch to solve this?

I began reading about linear programming but i have a problem understanding some symbols. I have experiencie in programming but not involving math.

Update

I looked into it, and now i know that this is a multidimensional or multiple-choice knapsack problem. Having solved the simple knapsack problem, now i only 1 constraint left, the 6 items limit.

Anyone knows a good aproach to this?

Update 2

I'm now using GLPK to model this problem and solve it, i'm so close to finish it, but i'm stuck with a simple constraint.

# Size of knapsack
param s;
# Total of items
param t;
# Type of items
set Z;
# Min bag
param m;

# Items: index, size, profit, count, type
set I, dimen 5;

# Indices
set J := setof{(i,s,p,o,z) in I} i;

# Assignment
var a{J}, binary;

#maximize profit
maximize obj :
  sum{(i,s,p,o,z) in I} p*a[i];

/*s.t. size :
  sum{(i,s,p,o,z) in I} s*a[i] <= c;*/

#constraint of total weight, but with the min value for each bag
#the min function doesn't work, it says argument for min has invalid type
#something about it not being a linear function
s.t. size :
  sum{zz in Z} ( 
    min(m, sum{(i,s,p,o,z) in I: zz=z} (s*a[i]) )
  ) <= c;

#constraint of number of items in each bag, i put an extra count number
#in the set so i could sum it and make it a constraint
s.t. count{zz in Z}:
  sum{(i,s,p,o,z) in I: zz=z} o*a[i] <= t;

solve;

printf "The bag contains:\n";
printf {(i,s,p,o,z) in I: a[i] == 1} " %i", i;
printf "\n";

data;

#set of type of items
set Z := 1 2 3 4;

# Total weight limit
param c := 100;
# Only 2 items per bag
param t := 2;
# Min bag value, if the bag weights less than it, then it counts as this value
param M := 10;

# Items: index, size, profit, count, type
set I :=
  1 10 10 1 1 
  2 10 10 1 1
  3 15 45 1 2
  4 20 20 1 2
  5 20 20 1 3
  6 24 24 1 3
  7 24 25 1 4
  8 50 50 1 4;

end;

Note: i used different values here to keep it small.

That's my model, it works without the min weight constraint, i just need for it to sum the minimum value of 50kg or the bag total, but the min function doesn't work there. I tried this formula

(can't post images)

min(a,b) = (a+b- abs(a-b))/2

but i can't use the abs function either.

Can somebody point me in the right direction about this.

Solution

  • You can formulate your problem as a 0-1 integer program and solve it with GLPK or other linear programming solver (glpk is free). The only question: are you taking empty bags? Let 

    i = {1,2,3,4} -- set of item types
j -- set of items
x_ij = {0,1} -- decision variable for jth item of ith type
w_ij and p_ij -- weights and profits

max sum_ij p_ij*x_ij

subject to:
sum_j x_ij <= 6 for all i  // at most 6 items in a bag
// if you need empty bags:
sum_ij w_ij*x_ij + 4*50 <= 700 kg  // total weight

x_ij = {0,1} for all i and j.

    if you don't need empty bags then the formulation becomes more complicated

    max sum_ij p_ij*x_ij

subject to:
sum_j x_ij <= 6    for all i  // at most 6 items in a bag
sum_ij w_ij*x_ij + 50*(sum_i y_i) <= 700 kg  // total weight
y_i <= sum_j x_ij    for all i  
N*y_i >= sum_j x_ij    for all i  // N -- total number of items of ith type, 
                                  // fixed value, not a variable; e.g., 
                                  // you have 10 items of each kind then N=10

y_i = {0,1} for all i
x_ij = {0,1} for all i and j.

    If you need to solve the program once then I would suggest to write a cplex .lp file http://www-01.ibm.com/support/knowledgecenter/SS9UKU_12.4.0/com.ibm.cplex.zos.help/FileFormats/topics/LP.html and solve it with glpsolve; otherwise use c++ or python glpk callable libraries.

    Update 1:

    One can linearize the constraint min{50, sum_i x_i*w_i} in two steps. For simplicity, consider one knapsack. Let

    M -- the total possible weight (sum up all input items' weights)
y={0,1} -- when sum_i x_i*w_i >= 50 y=1, otherwise y=0

min{50, sum_i x_i*w_i} <= 100    is equivalent to
(0): (1-y)*50 + y*(sum_i x_i*w_i) <= 100
(1): My >= sum_i x_i*w_i - 50
(2): M(1-y) >= 50 - sum_i x_i*w_i

    it's a bit unusual but it's correct. Indeed, when sum_i x_i*w_i >= 50 the solver have to set y to 1 by constraint (1) in the mean time (2) is just 0 >= 50-sum_i x_i*w_i <= 0, i.e., is redundant; when sum_i x_i*w_i < 50, y=0 by (2) and now (1) is redundant.

    The next step is to linearize the second term in (0). Let z_i = {0,1}, it will represent y*x_i term. Note that y*x_i is 1 only when both terms are 1, otherwise it's 0. Hence,

    y*(sum_i x_i*w_i)  is equivalent to

sum_i z_i*w_i
2*z_i <= x_i + y,  for all i
z_i >= x_i + y - 1,  for all i

    like before, it's easy to check that z_i = 1 only if x_i=y=1, otherwise it's 0.

    After the linearization your constraint looks like the following:

    (0): (1-y)*50 + (sum_i z_i*w_i) <= 100

(1): My >= sum_i x_i*w_i - 50
(2): M(1-y) >= 50 - sum_i x_i*w_i

(3): 2*z_i <= x_i + y,  for all i
(4): z_i >= x_i + y - 1,  for all i

 y = {0,1}, z_i = {0,1}