Multiple Knapsacks with splitting

Question

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.

AirSquid · Answer

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]

Multiple Knapsacks with splitting

Is this a known problem?

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

One Answer

Yields:

Add your own answers!

Ask a Question