Knapsack

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.

• Python
• 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.

• Python
• 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.

GitHub: Specific and general Pyomo binary knapsack models.

• Python
• Pyomo