Note

# Application Classes for Optimization Problems¶

## Introduction¶

We introduce application classes for the following optimization problems so that users can easily try various optimization problems on quantum computers.

1. Exact cover problem

• Given a collection of subsets of items, find a subcollection such that each item is covered exactly once.

1. Knapsack problem

• Given a set of items, find a subset of items such that the total weight is within the capacity and the total value is maximized.

1. Number partition problem

• Given a multiset of positive integers, find a partition of the multiset into two subsets such that the sums of the subsets are equal.

1. Set packing problem

• Given a collection of subsets of items, find a subcollection such that all subsets of the subcollection are pairwise disjoint and the number of items in the subcollection is maximized.

Graph problems

1. Clique problem

• Given an undirected graph, find a subset of nodes with a specified number or the maximum number such that the induced subgraph is complete.

1. Graph partition problem

• Given an undirected graph, find a partition into two components whose sizes are equal such that the total capacity of the edges between the two components is minimized.

1. Max-cut problem

• Given an undirected graph, find a partition of nodes into two subsets such that the total weight of the edges between the two subsets is maximized.

1. Stable set problem

• Given an undirected graph, find a subset of nodes such that no edge connects the nodes in the subset and the number of nodes is maximized.

1. Traveling salesman problem

• Given a graph, find a route with the minimum distance such that the route visits each city exactly once.

1. Vehicle routing problem

• Given a graph, a depot node, and the number of vehicles (routes), find a set of routes such that each node is covered exactly once except the depot and the total distance of the routes is minimized.

1. Vertex cover problem

• Given an undirected graph, find a subset of nodes with the minimum size such that each edge has at least one endpoint in the subsets.

The application classes for graph problems (GraphOptimizationApplication) provide a functionality to draw graphs of an instance and a result. Note that you need to install matplotlib beforehand to utilize the functionality.

We introduce examples of the vertex cover problem and the knapsack problem in this page.

Examples of the max-cut problem and the traveling salesman problem are available in Max-Cut and Traveling Salesman Problem.

We first import packages necessary for application classes.

[1]:

from qiskit_optimization.algorithms import MinimumEigenOptimizer
from qiskit import Aer
from qiskit.utils import algorithm_globals, QuantumInstance
from qiskit.algorithms import QAOA, NumPyMinimumEigensolver


## Vertex cover problem¶

We introduce the application class for the vertex cover problem as an example of graph problems. Given an undirected graph, the vertex cover problem asks us to find a subset of nodes with the minimum size such that all edges are covered by any node selected.

We import the application class VertexCover for the vertex cover problem and networkx to generate a random graph.

[2]:

from qiskit_optimization.applications.vertex_cover import VertexCover
import networkx as nx

seed = 123
algorithm_globals.random_seed = seed
qins = QuantumInstance(
backend=Aer.get_backend("qasm_simulator"), shots=1000, seed_simulator=seed, seed_transpiler=seed
)

[3]:

graph = nx.random_regular_graph(d=3, n=6, seed=seed)
pos = nx.spring_layout(graph, seed=seed)

[4]:

prob = VertexCover(graph)
prob.draw(pos=pos)


VertexCover takes a graph as an instance and to_quadratic_program generates a corresponding QuadraticProgram of the instance of the vertex cover problem.

[5]:

qp = prob.to_quadratic_program()
print(qp.prettyprint())

Problem name: Vertex cover

Minimize
x_0 + x_1 + x_2 + x_3 + x_4 + x_5

Subject to
Linear constraints (9)
x_1 + x_2 >= 1  'c0'
x_1 + x_4 >= 1  'c1'
x_1 + x_3 >= 1  'c2'
x_2 + x_3 >= 1  'c3'
x_0 + x_2 >= 1  'c4'
x_0 + x_4 >= 1  'c5'
x_0 + x_5 >= 1  'c6'
x_4 + x_5 >= 1  'c7'
x_3 + x_5 >= 1  'c8'

Binary variables (6)
x_0 x_1 x_2 x_3 x_4 x_5



You can solve the problem as follows. NumPyMinimumEigensolver finds the minimum eigen vector. You can also apply QAOA. Note that the solution by QAOA is not always optimal.

[6]:

# Numpy Eigensolver
meo = MinimumEigenOptimizer(min_eigen_solver=NumPyMinimumEigensolver())
result = meo.solve(qp)
print(result.prettyprint())
print("\nsolution:", prob.interpret(result))
prob.draw(result, pos=pos)

objective function value: 4.0
variable values: x_0=0.0, x_1=0.0, x_2=1.0, x_3=1.0, x_4=1.0, x_5=1.0
status: SUCCESS

solution: [2, 3, 4, 5]

[7]:

# QAOA
meo = MinimumEigenOptimizer(min_eigen_solver=QAOA(reps=1, quantum_instance=qins))
result = meo.solve(qp)
print(result.prettyprint())
print("\nsolution:", prob.interpret(result))
print("\ntime:", result.min_eigen_solver_result.optimizer_time)
prob.draw(result, pos=pos)

objective function value: 4.0
variable values: x_0=1.0, x_1=1.0, x_2=0.0, x_3=1.0, x_4=1.0, x_5=0.0
status: SUCCESS

solution: [0, 1, 3, 4]

time: 0.09063601493835449


## Knapsack problem¶

The knapsack problem asks us to find a combination of items such that the total weight is within the capacity of the knapsack and maximize the total value of the items. The following examples solve an instance of the knapsack problem with 5 items by Numpy eigensolver and QAOA.

[8]:

from qiskit_optimization.applications import Knapsack

[9]:

prob = Knapsack(values=[3, 4, 5, 6, 7], weights=[2, 3, 4, 5, 6], max_weight=10)
print(qp.prettyprint())

Problem name: Knapsack

Maximize
3*x_0 + 4*x_1 + 5*x_2 + 6*x_3 + 7*x_4

Subject to
Linear constraints (1)
2*x_0 + 3*x_1 + 4*x_2 + 5*x_3 + 6*x_4 <= 10  'c0'

Binary variables (5)
x_0 x_1 x_2 x_3 x_4


[10]:

# Numpy Eigensolver
meo = MinimumEigenOptimizer(min_eigen_solver=NumPyMinimumEigensolver())
result = meo.solve(qp)
print(result.prettyprint())
print("\nsolution:", prob.interpret(result))

objective function value: 13.0
variable values: x_0=1.0, x_1=1.0, x_2=0.0, x_3=1.0, x_4=0.0
status: SUCCESS

solution: [0, 1, 3]

[11]:

# QAOA
meo = MinimumEigenOptimizer(min_eigen_solver=QAOA(reps=1, quantum_instance=qins))
result = meo.solve(qp)
print(result.prettyprint())
print("\nsolution:", prob.interpret(result))
print("\ntime:", result.min_eigen_solver_result.optimizer_time)

objective function value: 13.0
variable values: x_0=1.0, x_1=1.0, x_2=0.0, x_3=1.0, x_4=0.0
status: SUCCESS

solution: [0, 1, 3]

time: 2.748866081237793


## How to check the Hamiltonian¶

If you want to check the actual Hamiltonian generated from your problem instance, you need to apply a converter as follows.

[12]:

from qiskit_optimization.converters import QuadraticProgramToQubo

[13]:

# the same knapsack problem instance as in the previous section
prob = Knapsack(values=[3, 4, 5, 6, 7], weights=[2, 3, 4, 5, 6], max_weight=10)
print(qp.prettyprint())

Problem name: Knapsack

Maximize
3*x_0 + 4*x_1 + 5*x_2 + 6*x_3 + 7*x_4

Subject to
Linear constraints (1)
2*x_0 + 3*x_1 + 4*x_2 + 5*x_3 + 6*x_4 <= 10  'c0'

Binary variables (5)
x_0 x_1 x_2 x_3 x_4


[14]:

# intermediate QUBO form of the optimization problem
qubo = conv.convert(qp)
print(qubo.prettyprint())

Problem name: Knapsack

Minimize
26*[email protected][email protected]^2 + 104*[email protected][email protected]*[email protected][email protected]
+ 208*[email protected][email protected]*[email protected][email protected] + 156*[email protected][email protected]*[email protected][email protected]
+ 104*[email protected][email protected]^2 + 416*[email protected][email protected]*[email protected][email protected]
+ 312*[email protected][email protected]*[email protected][email protected] + 416*[email protected][email protected]^2
+ 624*[email protected][email protected]*[email protected][email protected] + 234*[email protected][email protected]^2
+ 104*x_0*[email protected][email protected] + 208*x_0*[email protected][email protected] + 416*x_0*[email protected][email protected]
+ 312*x_0*[email protected][email protected] + 104*x_0^2 + 312*x_0*x_1 + 416*x_0*x_2 + 520*x_0*x_3
+ 624*x_0*x_4 + 156*x_1*[email protected][email protected] + 312*x_1*[email protected][email protected]
+ 624*x_1*[email protected][email protected] + 468*x_1*[email protected][email protected] + 234*x_1^2 + 624*x_1*x_2
+ 780*x_1*x_3 + 936*x_1*x_4 + 208*x_2*[email protected][email protected] + 416*x_2*[email protected][email protected]
+ 832*x_2*[email protected][email protected] + 624*x_2*[email protected][email protected] + 416*x_2^2 + 1040*x_2*x_3
+ 1248*x_2*x_4 + 260*x_3*[email protected][email protected] + 520*x_3*[email protected][email protected]
+ 1040*x_3*[email protected][email protected] + 780*x_3*[email protected][email protected] + 650*x_3^2 + 1560*x_3*x_4
+ 312*x_4*[email protected][email protected] + 624*x_4*[email protected][email protected] + 1248*x_4*[email protected][email protected]
+ 936*x_4*[email protected][email protected] + 936*x_4^2 - 520*[email protected][email protected]
- 1040*[email protected][email protected] - 2080*[email protected][email protected] - 1560*[email protected][email protected] - 1043*x_0
- 1564*x_1 - 2085*x_2 - 2606*x_3 - 3127*x_4 + 2600

Subject to
No constraints

Binary variables (9)
x_0 x_1 x_2 x_3 x_4 [email protected][email protected] [email protected][email protected] [email protected][email protected]
[email protected][email protected]


[15]:

# qubit Hamiltonian and offset
op, offset = qubo.to_ising()
print(f"num qubits: {op.num_qubits}, offset: {offset}\n")
print(op)

num qubits: 9, offset: 1417.5

-258.5 * IIIIIIIIZ
- 388.0 * IIIIIIIZI
- 517.5 * IIIIIIZII
- 647.0 * IIIIIZIII
- 776.5 * IIIIZIIII
- 130.0 * IIIZIIIII
- 260.0 * IIZIIIIII
- 520.0 * IZIIIIIII
- 390.0 * ZIIIIIIII
+ 78.0 * IIIIIIIZZ
+ 104.0 * IIIIIIZIZ
+ 156.0 * IIIIIIZZI
+ 130.0 * IIIIIZIIZ
+ 195.0 * IIIIIZIZI
+ 260.0 * IIIIIZZII
+ 156.0 * IIIIZIIIZ
+ 234.0 * IIIIZIIZI
+ 312.0 * IIIIZIZII
+ 390.0 * IIIIZZIII
+ 26.0 * IIIZIIIIZ
+ 39.0 * IIIZIIIZI
+ 52.0 * IIIZIIZII
+ 65.0 * IIIZIZIII
+ 78.0 * IIIZZIIII
+ 52.0 * IIZIIIIIZ
+ 78.0 * IIZIIIIZI
+ 104.0 * IIZIIIZII
+ 130.0 * IIZIIZIII
+ 156.0 * IIZIZIIII
+ 26.0 * IIZZIIIII
+ 104.0 * IZIIIIIIZ
+ 156.0 * IZIIIIIZI
+ 208.0 * IZIIIIZII
+ 260.0 * IZIIIZIII
+ 312.0 * IZIIZIIII
+ 52.0 * IZIZIIIII
+ 104.0 * IZZIIIIII
+ 78.0 * ZIIIIIIIZ
+ 117.0 * ZIIIIIIZI
+ 156.0 * ZIIIIIZII
+ 195.0 * ZIIIIZIII
+ 234.0 * ZIIIZIIII
+ 39.0 * ZIIZIIIII
+ 78.0 * ZIZIIIIII
+ 156.0 * ZZIIIIIII

[16]:

import qiskit.tools.jupyter

%qiskit_version_table


### Version Information

Qiskit SoftwareVersion
qiskit-terra0.21.1
qiskit-aer0.10.4
qiskit-optimization0.4.0
System information
Python version3.8.13
Python compilerGCC 9.4.0
Python builddefault, Jul 22 2022 10:44:13
OSLinux
CPUs2
Memory (Gb)6.780967712402344
Thu Aug 11 21:12:37 2022 UTC

### This code is a part of Qiskit

[ ]: