3
$\begingroup$

I am trying to solve a problem that I believe is a variation of the multiple knapsacks.

Like the classical multiple knapsacks problem, I have a set of items, each one with a weight and a value and I am trying to divide them into multiple bins and find the combination with the best value.

But unlike the classical, I also need the following:

  • Some bins might not accept some items, e.g.: I have item x and bins A, B, and C. Item x can only be added to the bins A and B.

  • The item can be divided, an item with 100 could be divided into two so that it fits two bins of 50. Note: all numbers are integers.

  • Even if the item can be divided, I must also make sure that all parts of the item weight are assigned to bins. e.g.:

This has a valid solution:

items = [200, 100]
bins = [150, 150]

This doesn't:

items = [200]
bins = [150]

My questions are:

Is this a known problem?

It looks similar to the knapsack problem to me but does this variation have a name? If I knew the proper name for this problem I could search for solutions for it.

Is possible to solve with the solvers from OR-Tools?

I am using OR-Tools to explore this problem, but so far I haven't had any luck implementing this variation.

This is a not homework, my items are actually invoices that I am trying to assign to investment bins.

$\endgroup$
3
$\begingroup$

This is not too big of a leap from the basic Knapsack problem and can be handled with only 3 constraints for the bin size, all-or-nothing, and the prohibited placements. Below is an example that I think fits the design pattern. This is casted in pyomo. I think OR-Tools is pretty similar in structure. It should not be a major leap.

# multi-knapsack, integer divisible

import pyomo.environ as pyo

#           item:   value, weight
data = {    1:      (20, 10),
            2:      (30, 20),
            3:      (40, 5),
            4:      (5, 10),
            5:      (100, 10)}
#           bin:    capacity
bins = {    1:      8,
            2:      12,
            3:      14}

prohibited = {(5, 1), (3, 2)}   # (item:bin) that are prohibited.

mdl = pyo.ConcreteModel()

# sets
mdl.invs = pyo.Set(initialize=data.keys())
mdl.bins = pyo.Set(initialize=bins.keys())
mdl.prohibited = pyo.Set(within=mdl.invs*mdl.bins, initialize=prohibited)

# params
mdl.value   = pyo.Param(mdl.invs, initialize= {k:data[k][0] for k in data})
mdl.weight  = pyo.Param(mdl.invs, initialize= {k:data[k][1] for k in data})
mdl.bin_cap = pyo.Param(mdl.bins, initialize= bins)

# vars
mdl.X = pyo.Var(mdl.invs, mdl.bins, domain=pyo.NonNegativeIntegers)     # the amount from invoice i in bin j
mdl.X_used = pyo.Var(mdl.invs, domain=pyo.Binary)

### Objective ###

mdl.OBJ = pyo.Objective(expr=sum(mdl.X[i, b]*mdl.value[i] for 
                        i in mdl.invs for
                        b in mdl.bins), sense=pyo.maximize)

### constraints ###

# don't overstuff bin
def bin_limit(self, b):
    return sum(mdl.X[i, b] for i in mdl.invs) <= mdl.bin_cap[b]
mdl.c1 = pyo.Constraint(mdl.bins, rule=bin_limit)

# all-or-nothing
def use_all(self, i):
    return sum(mdl.X[i, b] for b in mdl.bins) == mdl.X_used[i]*mdl.weight[i]
mdl.c2 = pyo.Constraint(mdl.invs, rule=use_all)

# don't allow prohibited placements
def limit_prohib(self, i, b):
    return mdl.X[i, b] == 0
mdl.c3 = pyo.Constraint(mdl.prohibited, rule=limit_prohib)

# solve it...
solver = pyo.SolverFactory('cbc')
results = solver.solve(mdl)
mdl.X.display()

Yields:

X : Size=15, Index=X_index
    Key    : Lower : Value : Upper : Fixed : Stale : Domain
    (1, 1) :     0 :   0.0 :  None : False : False : NonNegativeIntegers
    (1, 2) :     0 :   0.0 :  None : False : False : NonNegativeIntegers
    (1, 3) :     0 :   0.0 :  None : False : False : NonNegativeIntegers
    (2, 1) :     0 :   8.0 :  None : False : False : NonNegativeIntegers
    (2, 2) :     0 :   8.0 :  None : False : False : NonNegativeIntegers
    (2, 3) :     0 :   4.0 :  None : False : False : NonNegativeIntegers
    (3, 1) :     0 :   0.0 :  None : False : False : NonNegativeIntegers
    (3, 2) :     0 :   0.0 :  None : False : False : NonNegativeIntegers
    (3, 3) :     0 :   0.0 :  None : False : False : NonNegativeIntegers
    (4, 1) :     0 :   0.0 :  None : False : False : NonNegativeIntegers
    (4, 2) :     0 :   0.0 :  None : False : False : NonNegativeIntegers
    (4, 3) :     0 :   0.0 :  None : False : False : NonNegativeIntegers
    (5, 1) :     0 :   0.0 :  None : False : False : NonNegativeIntegers
    (5, 2) :     0 :   0.0 :  None : False : False : NonNegativeIntegers
    (5, 3) :     0 :  10.0 :  None : False : False : NonNegativeIntegers
[Finished in 2.9s]
| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks so much! This is. an amazing answer! I have just one problem, I didn't state this clearly in my question, but I also have to make sure that the full weight of the item is assigned. It can be divided, but all parts must be assigned into bins. I updated my question $\endgroup$ – Cesar Canassa Jul 24 at 13:04
  • $\begingroup$ Nevermind, I just noticed that you did it with the all-or-nothing! Thanks! $\endgroup$ – Cesar Canassa Jul 24 at 14:02
  • $\begingroup$ Awesome. Glad it was helpful! $\endgroup$ – AirSquid Jul 24 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.