# Multiple Knapsacks with splitting

Operations Research Asked by Cesar Canassa on December 20, 2021

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.

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]


Answered by AirSquid on December 20, 2021

## Related Questions

### Conditions required for strong duality to hold for SDPs

1  Asked on August 19, 2021

### Relationship between extreme points and optimal solutions of SDPs

1  Asked on August 19, 2021

### How to parallelize metaheuristics algorithms (Island Model)?

1  Asked on August 19, 2021 by antarctica

### Can we get closed form solution for such a problem?

1  Asked on August 19, 2021

### Can we use reinforcement learning and convex optimization to solve an optimization problem?

2  Asked on August 19, 2021 by qinqinxiaoguai

### Nonlinear integer (0/1) programming solver

6  Asked on March 1, 2021 by rajya

### How can I find the shortest path for all nodes in a graph from a source $s$?

1  Asked on March 1, 2021 by windbreeze

### Free solver for MINP problems

1  Asked on February 18, 2021 by dspinfinity

### Where I can study some job shop scheduling by course (video )?

0  Asked on February 18, 2021 by yue-chao

### Linear objective function with power term in constraint

1  Asked on February 15, 2021 by user152503

### Formulating these logical constraint in an ILP

1  Asked on January 18, 2021

### Modeling the multiplication of two binary decision variables in undirected graph in python

0  Asked on January 18, 2021 by amedeo

### Flexible Job Shop with Preemption

0  Asked on January 15, 2021 by robert-hildebrand

### How to handle an equality constraint in metaheuristic algorithms (like GA, PSO)?

3  Asked on January 11, 2021 by stevgates

### What is the difference between min- cut formulation and (bi) partitioning formulation?

1  Asked on January 8, 2021 by fathese

### Logical constraint in ILP

1  Asked on December 22, 2020 by che

### Quasi-convex function must be “partially monotonic”?

1  Asked on December 13, 2020 by high-gpa

### Constraint programming resources

3  Asked on November 28, 2020 by joffrey-l

### Pyomo variable creation dilemma

1  Asked on October 31, 2020 by ethan-deakins

### Convexity of the variance of a mixture distribution

1  Asked on September 25, 2020 by independentvariable