# Multidimensional knapsack
#
# Extends the knapsack to several simultaneous resource limits, so an item
# consumes a vector rather than a scalar. Adding rows does not change the
# variable structure, only the feasible region.
#
# Technique: Several independent capacity rows over the same binaries.
#
# On this instance the optimum is 47 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Fréville, A. (2004). The multidimensional 0-1 knapsack problem:
# an overview. European Journal of Operational Research 155(1), 1–21.
# doi:10.1016/S0377-2217(03)00274-1
model m
set I = {1, 2, 3, 4, 5, 6}
set D = {1, 2, 3}
const v = {16, 4, 1, 20, 17, 10}, forall i in I
const w = {{9, 4, 4, 7, 1, 3},
{6, 6, 3, 7, 6, 3},
{4, 7, 9, 3, 1, 1}}, forall d in D, forall i in I
const c = {13, 17, 12}, forall d in D
bin x, forall i in I
max sum_{i in I}{v_{i} * x_{i}}
# one capacity row per resource dimension
constr sum_{i in I}{w_{d,i} * x_{i}} <= c_{d}, forall d in D
end
import elytica
Read this through MCP: read with path: "formulations/knapsack-multidim", or resource hlpl://formulations/knapsack-multidim.