Coder Social home page Coder Social logo

mahdi-torabian / d-wave-knapsack Goto Github PK

View Code? Open in Web Editor NEW

This project forked from dwave-examples/knapsack

0.0 0.0 0.0 126 KB

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

License: Apache License 2.0

Python 100.00%

d-wave-knapsack's Introduction

Open in GitHub Codespaces Linux/Mac/Windows build status

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.

License

Released under the Apache License 2.0. See LICENSE file.

d-wave-knapsack's People

Contributors

joelgdwave avatar joelpasvolsky avatar randomir avatar hemantdwave avatar arcondello avatar m3ller avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.