Skip to content

Solution of the Bin-Packing problem using QAOA and Qiskit optimization library

License

Notifications You must be signed in to change notification settings

alejomonbar/Bin-Packing-Problem

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 
 
 

Repository files navigation

Bin-Packing-Problem

The bin packing problem is an optimization problem where given a number of items with a respective weight, we look at the best arrangement of the items to minimize the number of bins or containers needed. The restriction, in this case, is the capacity of the bins which cannot surpass a certain weight. This problem has many real applications in areas as loading trucks with a weight restriction, filling up containers, and FPGA semiconductors chip design.

In terms of complexity, the bin packing problem is an NP-hard problem. However, there are efficient algorithms that allow the arrangement of a large number of items. One of them is the first fit, which provides a fast but not optimal solution to the problem.

In this tutorial, we will explore the solution of the bin packing problem, using a quantum computing representation in terms of quadratic unconstraint binary optimization (QUBO) and using the quantum approximation optimization (QAOA) algorithm.

1. Problem statement

subject to:

  • n is the number of items
  • m is the number of bins
  • is the jth item weight
  • is ith bin
  • is the variable that represent if the item j is in the bin i.

About

Solution of the Bin-Packing problem using QAOA and Qiskit optimization library

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published