# Multiple knapsack
#
# Packs items into several knapsacks of different capacities. Unlike bin
# packing, items may be left out entirely and the objective is the value
# packed rather than the number of bins — the constraint is `<= 1`, not `=
# 1`.
#
# Technique: Assignment binaries x_{i,k} with one capacity row per
# knapsack, and each item assigned at most once across all of
# them.
#
# On this instance the optimum is 26 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Martello, S. and Toth, P. (1990). Knapsack Problems: Algorithms
# and Computer Implementations. Wiley.
model m
set I = {1, 2, 3, 4}
set K = {1, 2}
const v = {6, 6, 7, 7}, forall i in I
const w = {4, 2, 3, 4}, forall i in I
const c = {7, 9}, forall k in K
bin x, forall i in I, forall k in K
max sum_{i in I}{sum_{k in K}{v_{i} * x_{i,k}}}
# an item goes into at most one knapsack — it may also be left out
constr sum_{k in K}{x_{i,k}} <= 1, forall i in I
constr sum_{i in I}{w_{i} * x_{i,k}} <= c_{k}, forall k in K
end
import elytica
Read this through MCP: read with path: "formulations/multiple-knapsack", or resource hlpl://formulations/multiple-knapsack.