Knapsack

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:

• Objective: Maximize freight value (sum of values of the selected items).
• Constraint: Total freight weight (sum of weights of the selected items) must be less than or equal to the container's capacity.

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.

Usage

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.

Code Overview

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.

• Constraint: A quadratic model with the previously created binary variables, where the linear biases are set equal to the weight of each item, is created with the requirement that the total weight must not exceed the container's capacity.
• parse_inputs() is a utility function that reads data from the example files.
• parse_solution() parses and displays the results returned from the solver.

License

Released under the Apache License 2.0. See LICENSE file.

Issues

Improve readme

opened on 2022-05-28 00:39:54 by akoszegi

Reformat the ReadMe so it's consistent with the other code examples (add Problem Formulation section)

Simplify

opened on 2021-07-30 04:31:51 by hsadeghidw None

Use the proper function for the knapsack inequality constraint

opened on 2021-07-29 23:24:44 by hsadeghidw

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.