The knapsack problem is a well-known optimization problem. It is encountered, for example, in packing shipping containers. A shipping container has a weight capacity which it can hold. Given a collection of items to be shipped, where each item has a value and a weight, the problem is to select the optimal items to pack in the shipping container. This optimization problem can be defined as an objective with a constraint:
This example solves such a knapsack problem by reformulating it as a constrained quadratic model (CQM) and submitting it to a Leap hybrid CQM solver.
To run the default demo, enter the command:
bash
python knapsack.py
To view available options, enter the command:
bash
python knapsack.py --help
Command-line arguments let you select one of several data sets (under the /data
folder) and set the freight capacity. The data files are formulated as rows of
items, each defined as a pair of weight and value.
The code in knapsack.py
includes three main functions:
build_knapsack_cqm()
creates a CQM by setting an objective and constraint as
follows:
Objective: Binary variables are created for each item, and assigned a linear bias equal to the negative value of the item's value. To minimize this objective, by selecting an optimal set of items, is equivalent to maximizing the total value of the freight. Solutions set a value of 1 to selected items and 0 to unselected items.
parse_inputs()
is a utility function that reads data from the example files.parse_solution()
parses and displays the results returned from the solver.Released under the Apache License 2.0. See LICENSE file.
Reformat the ReadMe so it's consistent with the other code examples (add Problem Formulation section)
currently, the way the inequality constraint is built is very involved. The code can be simplified significantly by using .add_linear_inequality_constraint
.
If the goal is to teach users how to work with slack variables, using a higher-level function is not needed. However, more users can expand this example to an application, if it's simplified.
hybrid-solution constraint-satisfaction-problem cqm beginner