# Knapsack

The "Knapsack Problem" is a very common application of optimization modelling. That is, given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. There are numerous variations of the knapsack problem.

Key features of this model:

- Description: Select items to include in a knapsack, given weight and volume constraints.
- Category: Knapsack.
- Type: MILP.
- Library: PuLP.
- Solver: CBC.

Note that the notebook includes a common error:

- The model implementation has a common error that becomes apparent when we print the model using
`print(prob)`

. - That is, each of the constraints is added multiple times via the
`for i in S:`

loop, in addition to having the sum`for i in S`

in each constraint. - The error can be corrected by removing the
`for i in S:`

loop. - The model still finds the correct solution because the extra constraints are redundant. But in a larger model this type of error may make the model more difficult to solve.
- We have retained the error to illustrate how easy it is to make this type of error, and to show how printing the model can help with debugging a model.

GitHub: Knapsack with weight and volume constraints in PuLP.

Key features of this model:

- Description: Select items to include in multiple knapsacks, given multiple attributes of each item.
- Category: Knapsack.
- Type: MILP.
- Library: OR-Tools.
- Solver: SCIP.

This notebook is based on an example by Google. Key differences are:

- The number of attributes is expanded from one to three.
- The variables are defined as integer (0, 1) rather than Boolean, though the result is the same.
- Google's example solves the model using two methods: SCIP MIP solver and CP-SAT solver.

GitHub: Multi-constrained, multi-knapsack problem in OR-Tools.

Key features of this model:

- Description: Select items to include in a knapsack, where inclusion is a binary choice.
- Category: Knapsack.
- Type: MILP.
- Library: Pyomo.
- Solver: GLPK.

Notes:

- Specific model: hard-codes coefficients in the expressions.
- General model: specifies coefficients using data structures.