/ knapsack Public

Implementation of knapsack problem, set up for scaling to large problem size

# dwave-examples/knapsack

Switch branches/tags
Nothing to show

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

## Files

Failed to load latest commit information.
Type
Name
Commit time
Mar 19, 2021
Nov 17, 2020
Aug 25, 2021
Feb 8, 2020
Sep 14, 2021

# 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:

`python knapsack.py`

To view available options, enter the command:

`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.

Implementation of knapsack problem, set up for scaling to large problem size

## Releases

No releases published

## Packages 0

No packages published