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()
qp

[5]:

\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: Vertex cover

Minimize
obj: x_0 + x_1 + x_2 + x_3 + x_4 + x_5
Subject To
c0: x_1 + x_2 >= 1
c1: x_1 + x_4 >= 1
c2: x_1 + x_3 >= 1
c3: x_2 + x_3 >= 1
c4: x_0 + x_2 >= 1
c5: x_0 + x_4 >= 1
c6: x_0 + x_5 >= 1
c7: x_4 + x_5 >= 1
c8: x_3 + x_5 >= 1

Bounds
0 <= x_0 <= 1
0 <= x_1 <= 1
0 <= x_2 <= 1
0 <= x_3 <= 1
0 <= x_4 <= 1
0 <= x_5 <= 1

Binaries
x_0 x_1 x_2 x_3 x_4 x_5
End


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:\n', result)
print('\nsolution:\n', prob.interpret(result))
prob.draw(result, pos=pos)

result:
optimal function value: 4.0
optimal value: [0. 0. 1. 1. 1. 1.]
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:\n', result)
print('\nsolution:\n', prob.interpret(result))
print('\ntime:', result.min_eigen_solver_result.optimizer_time)
prob.draw(result, pos=pos)

result:
optimal function value: 4.0
optimal value: [1. 1. 0. 1. 1. 0.]
status: SUCCESS

solution:
[0, 1, 3, 4]

time: 0.0981144905090332


## 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)
qp

[9]:

\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: Knapsack

Maximize
obj: 3 x_0 + 4 x_1 + 5 x_2 + 6 x_3 + 7 x_4
Subject To
c0: 2 x_0 + 3 x_1 + 4 x_2 + 5 x_3 + 6 x_4 <= 10

Bounds
0 <= x_0 <= 1
0 <= x_1 <= 1
0 <= x_2 <= 1
0 <= x_3 <= 1
0 <= x_4 <= 1

Binaries
x_0 x_1 x_2 x_3 x_4
End

[10]:

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

result:
optimal function value: 13.0
optimal value: [1. 1. 0. 1. 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:\n', result)
print('\nsolution:\n', prob.interpret(result))
print('\ntime:', result.min_eigen_solver_result.optimizer_time)

result:
optimal function value: 13.0
optimal value: [1. 1. 0. 1. 0.]
status: SUCCESS

solution:
[0, 1, 3]

time: 0.7561511993408203


## 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)
qp

[13]:

\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: Knapsack

Maximize
obj: 3 x_0 + 4 x_1 + 5 x_2 + 6 x_3 + 7 x_4
Subject To
c0: 2 x_0 + 3 x_1 + 4 x_2 + 5 x_3 + 6 x_4 <= 10

Bounds
0 <= x_0 <= 1
0 <= x_1 <= 1
0 <= x_2 <= 1
0 <= x_3 <= 1
0 <= x_4 <= 1

Binaries
x_0 x_1 x_2 x_3 x_4
End

[14]:

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

[14]:

\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: Knapsack

Minimize
obj: - 1043 x_0 - 1564 x_1 - 2085 x_2 - 2606 x_3 - 3127 x_4
- 520 [email protected][email protected] - 1040 [email protected][email protected] - 2080 [email protected][email protected]
- 1560 [email protected][email protected] + [ 208 x_0^2 + 624 x_0*x_1 + 832 x_0*x_2
+ 1040 x_0*x_3 + 1248 x_0*x_4 + 208 x_0*[email protected][email protected]
+ 416 x_0*[email protected][email protected] + 832 x_0*[email protected][email protected] + 624 x_0*[email protected][email protected]
+ 468 x_1^2 + 1248 x_1*x_2 + 1560 x_1*x_3 + 1872 x_1*x_4
+ 312 x_1*[email protected][email protected] + 624 x_1*[email protected][email protected]
+ 1248 x_1*[email protected][email protected] + 936 x_1*[email protected][email protected] + 832 x_2^2
+ 2080 x_2*x_3 + 2496 x_2*x_4 + 416 x_2*[email protected][email protected]
+ 832 x_2*[email protected][email protected] + 1664 x_2*[email protected][email protected]
+ 1248 x_2*[email protected][email protected] + 1300 x_3^2 + 3120 x_3*x_4
+ 520 x_3*[email protected][email protected] + 1040 x_3*[email protected][email protected]
+ 2080 x_3*[email protected][email protected] + 1560 x_3*[email protected][email protected] + 1872 x_4^2
+ 624 x_4*[email protected][email protected] + 1248 x_4*[email protected][email protected]
+ 2496 x_4*[email protected][email protected] + 1872 x_4*[email protected][email protected] + 52 [email protected][email protected]^2
+ 208 [email protected][email protected]*[email protected][email protected] + 416 [email protected][email protected]*[email protected][email protected]
+ 312 [email protected][email protected]*[email protected][email protected] + 208 [email protected][email protected]^2
+ 832 [email protected][email protected]*[email protected][email protected] + 624 [email protected][email protected]*[email protected][email protected]
+ 832 [email protected][email protected]^2 + 1248 [email protected][email protected]*[email protected][email protected]
+ 468 [email protected][email protected]^2 ]/2 + 2600
Subject To

Bounds
0 <= x_0 <= 1
0 <= x_1 <= 1
0 <= x_2 <= 1
0 <= x_3 <= 1
0 <= x_4 <= 1
0 <= [email protected][email protected] <= 1
0 <= [email protected][email protected] <= 1
0 <= [email protected][email protected] <= 1
0 <= [email protected][email protected] <= 1

Binaries
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]
End

[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

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

[16]:

import qiskit.tools.jupyter
%qiskit_version_table


### Version Information

Qiskit SoftwareVersion
qiskit-terra0.18.3
qiskit-aer0.9.0
qiskit-optimization0.2.3
System information
Python3.8.12 (default, Sep 13 2021, 08:28:12) [GCC 9.3.0]
OSLinux
CPUs2
Memory (Gb)6.790924072265625
Wed Oct 06 16:50:35 2021 UTC

### This code is a part of Qiskit

[ ]: