Converters for Quadratic Programs¶
Introduction¶
Qiskit Optimization provides with QuadraticProgram a very generic and powerful representation for optimization problems. However, usually, optimization algorithms cannot handle all possible types of problems that can be modelled, but only a sub-class. Many available quantum optimization algorithms can handle Quadratic Unconstrained Binary Optimization (QUBO) problems. To do so, first, it is necessary to convert a given optimization problem into a QUBO.
Qiskit Optimization provides converters to achieve this conversion whenever possible. More precisely, Qiskit Optimization provides the following converters: - InequalityToEquality: converts inequality constraints into equality constraints with additional slack variables. - IntegerToBinary: converts integer variables into binary variables and corresponding coefficients. - LinearEqualityToPenalty: convert equality constraints into additional terms of the object function. -
QuadraticProgramToQubo: a wrapper for IntegerToBinary and LinearEqualityToPenalty for convenience.
Qiskit Optimization provides algorithms that convert a QUBO to an Ising Hamiltonian (in Qiskit called Operator) and then try to approximate its ground state, such as the MinimumEigenOptimizer (which generalizes algorithms such as VQE and QAOA). The QUBO to Operator converter is introduced in the corresponding tutorial.
Qiskit Optimization also provides algorithms and converters that are not based on Ising Hamiltonians, e.g., the GroverOptimizer, which is introduced in a separate tutorial.
InequalityToEquality¶
InequalityToEqualityConverter converts inequality constraints into equality constraints with additional slack variables to remove inequality constraints from QuadraticProgram. The upper bounds and the lower bounds of slack variables will be calculated from the difference between the left sides and the right sides of constraints. Signs of slack variables depend on symbols in constraints such as \(\leq\) and \(\geq\).
The following is an example of a maximization problem with two inequality constraints. Variable \(x\) and \(y\) are binary variables and variable \(z\) is an integer variable.
With QuadraticProgram, an optimization model of the problem is written as follows.
[1]:
from qiskit.optimization import QuadraticProgram
[2]:
qp = QuadraticProgram()
qp.binary_var('x')
qp.binary_var('y')
qp.integer_var(lowerbound=0, upperbound=7, name='z')
qp.maximize(linear={'x': 2, 'y': 1, 'z': 1})
qp.linear_constraint(linear={'x': 1, 'y': 1, 'z': 1}, sense='LE', rhs=5.5,name='xyz_leq')
qp.linear_constraint(linear={'x': 1, 'y': 1, 'z': 1}, sense='GE', rhs=2.5,name='xyz_geq')
print(qp.export_as_lp_string())
\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: CPLEX
Maximize
obj: 2 x + y + z
Subject To
xyz_leq: x + y + z <= 5.500000000000
xyz_geq: x + y + z >= 2.500000000000
Bounds
0 <= x <= 1
0 <= y <= 1
z <= 7
Binaries
x y
Generals
z
End
Call encode method of InequalityToEqualityConverter to convert.
[3]:
from qiskit.optimization.converters import InequalityToEquality
[4]:
ineq2eq = InequalityToEquality()
qp_eq = ineq2eq.encode(qp)
print(qp_eq.export_as_lp_string())
\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: CPLEX
Maximize
obj: 2 x + y + z
Subject To
xyz_leq: x + y + z + xyz_leq@int_slack = 5
xyz_geq: x + y + z - xyz_geq@int_slack = 3
Bounds
0 <= x <= 1
0 <= y <= 1
z <= 7
xyz_leq@int_slack <= 5
xyz_geq@int_slack <= 6
Binaries
x y
Generals
z xyz_leq@int_slack xyz_geq@int_slack
End
After converting, the inequality constraints are replaced with equality constraints with additional slack variables.
IntegerToBinary¶
IntegerToBinary converts integer variables into binary variables and coefficients to remove integer variables from QuadraticProgram. For converting, bounded-coefficient encoding proposed in arxiv:1706.01945 (Eq. (5)) is used. For more detail of the encoding method, please see the paper.
We use the output of InequalityToEquality as starting point. Variable \(x\) and \(y\) are binary variables, while the variable \(z\) and the slack variables \(xyz\_leq\text{@}int\_slack\) and \(xyz\_geq\text{@}int\_slack\) are integer variables. We print the problem again for reference.
[5]:
print(qp_eq.export_as_lp_string())
\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: CPLEX
Maximize
obj: 2 x + y + z
Subject To
xyz_leq: x + y + z + xyz_leq@int_slack = 5
xyz_geq: x + y + z - xyz_geq@int_slack = 3
Bounds
0 <= x <= 1
0 <= y <= 1
z <= 7
xyz_leq@int_slack <= 5
xyz_geq@int_slack <= 6
Binaries
x y
Generals
z xyz_leq@int_slack xyz_geq@int_slack
End
Call encode method of IntegerToBinary to convert.
[6]:
from qiskit.optimization.converters import IntegerToBinary
[7]:
int2bin = IntegerToBinary()
qp_eq_bin = int2bin.encode(qp_eq)
print(qp_eq_bin.export_as_lp_string())
\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: CPLEX
Maximize
obj: 2 x + y + z@0 + 2 z@1 + 4 z@2
Subject To
xyz_leq: x + y + z@0 + 2 z@1 + 4 z@2 + xyz_leq@int_slack@0
+ 2 xyz_leq@int_slack@1 + 2 xyz_leq@int_slack@2 = 5
xyz_geq: x + y + z@0 + 2 z@1 + 4 z@2 - xyz_geq@int_slack@0
- 2 xyz_geq@int_slack@1 - 3 xyz_geq@int_slack@2 = 3
Bounds
0 <= x <= 1
0 <= y <= 1
0 <= z@0 <= 1
0 <= z@1 <= 1
0 <= z@2 <= 1
0 <= xyz_leq@int_slack@0 <= 1
0 <= xyz_leq@int_slack@1 <= 1
0 <= xyz_leq@int_slack@2 <= 1
0 <= xyz_geq@int_slack@0 <= 1
0 <= xyz_geq@int_slack@1 <= 1
0 <= xyz_geq@int_slack@2 <= 1
Binaries
x y z@0 z@1 z@2 xyz_leq@int_slack@0 xyz_leq@int_slack@1 xyz_leq@int_slack@2
xyz_geq@int_slack@0 xyz_geq@int_slack@1 xyz_geq@int_slack@2
End
After converting, integer variables \(z\) is replaced with three binary variables \(z\text{@}0\), \(z\text{@}1\) and \(z\text{@}2\) with coefficients 1, 2 and 4, respectively as the above. The slack variables \(xyz\_leq\text{@}int\_slack\) and \(xyz\_geq\text{@}int\_slack\) that were introduced by InequalityToEquality are also both replaced with three binary variables with coefficients 1, 2, 2, and 1, 2, 3, respectively.
Note: Essentially the coefficients mean that the sum of these binary variables with coefficients can be the sum of a subset of \(\{1, 2, 4\}\), \(\{1, 2, 2\}\), and \(\{1, 2, 3\}\) to represent that acceptable values \(\{0, \ldots, 7\}\), \(\{0, \ldots, 5\}\), and \(\{0, \ldots, 6\}\), which respects the lower bound and the upper bound of original integer variables correctly.
IntegerToBinary also provides functionality to translate a given binary result back to the original integer representation. This is illustrated later in this tutorial when we solve the different problem representations and compare the results.
LinearEqualityToPenalty¶
LinearEqualityToPenalty converts linear equality constraints into additional quadratic penalty terms of the objective function to map QuadraticProgram to an unconstrained form. An input to the converter has to be a QuadraticProgram with only linear equality constraints. Those equality constraints, e.g. \(\sum_i a_i x_i = b\) where \(a_i\) and \(b\) are numbers and \(x_i\) is a variable, will be added to the objective function in the form of
\(M(b - \sum_i a_i x_i)^2\) where \(M\) is a large number as penalty factor. By default \(M= 1e5\). A sign of the term will depends on the problem type is maximization or minimization.
We use the output of IntegerToBinary as starting point, where all variables are binary variables and all inequality constraints have been mapped to equality constraints. We print the problem again for reference.
[8]:
print(qp_eq_bin.export_as_lp_string())
\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: CPLEX
Maximize
obj: 2 x + y + z@0 + 2 z@1 + 4 z@2
Subject To
xyz_leq: x + y + z@0 + 2 z@1 + 4 z@2 + xyz_leq@int_slack@0
+ 2 xyz_leq@int_slack@1 + 2 xyz_leq@int_slack@2 = 5
xyz_geq: x + y + z@0 + 2 z@1 + 4 z@2 - xyz_geq@int_slack@0
- 2 xyz_geq@int_slack@1 - 3 xyz_geq@int_slack@2 = 3
Bounds
0 <= x <= 1
0 <= y <= 1
0 <= z@0 <= 1
0 <= z@1 <= 1
0 <= z@2 <= 1
0 <= xyz_leq@int_slack@0 <= 1
0 <= xyz_leq@int_slack@1 <= 1
0 <= xyz_leq@int_slack@2 <= 1
0 <= xyz_geq@int_slack@0 <= 1
0 <= xyz_geq@int_slack@1 <= 1
0 <= xyz_geq@int_slack@2 <= 1
Binaries
x y z@0 z@1 z@2 xyz_leq@int_slack@0 xyz_leq@int_slack@1 xyz_leq@int_slack@2
xyz_geq@int_slack@0 xyz_geq@int_slack@1 xyz_geq@int_slack@2
End
Call encode method of LinearEqualityToPenalty to convert.
[9]:
from qiskit.optimization.converters import LinearEqualityToPenalty
[10]:
lineq2penalty = LinearEqualityToPenalty()
qubo = lineq2penalty.encode(qp_eq_bin)
print(qubo.export_as_lp_string())
\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: CPLEX
Maximize
obj: 1600002 x + 1600001 y + 1600001 z@0 + 3200002 z@1 + 6400004 z@2
+ 1000000 xyz_leq@int_slack@0 + 2000000 xyz_leq@int_slack@1
+ 2000000 xyz_leq@int_slack@2 - 600000 xyz_geq@int_slack@0
- 1200000 xyz_geq@int_slack@1 - 1800000 xyz_geq@int_slack@2 + [
- 400000 x^2 - 800000 x*y - 800000 x*z@0 - 1600000 x*z@1 - 3200000 x*z@2
- 400000 x*xyz_leq@int_slack@0 - 800000 x*xyz_leq@int_slack@1
- 800000 x*xyz_leq@int_slack@2 + 400000 x*xyz_geq@int_slack@0
+ 800000 x*xyz_geq@int_slack@1 + 1200000 x*xyz_geq@int_slack@2
- 400000 y^2 - 800000 y*z@0 - 1600000 y*z@1 - 3200000 y*z@2
- 400000 y*xyz_leq@int_slack@0 - 800000 y*xyz_leq@int_slack@1
- 800000 y*xyz_leq@int_slack@2 + 400000 y*xyz_geq@int_slack@0
+ 800000 y*xyz_geq@int_slack@1 + 1200000 y*xyz_geq@int_slack@2
- 400000 z@0^2 - 1600000 z@0*z@1 - 3200000 z@0*z@2
- 400000 z@0*xyz_leq@int_slack@0 - 800000 z@0*xyz_leq@int_slack@1
- 800000 z@0*xyz_leq@int_slack@2 + 400000 z@0*xyz_geq@int_slack@0
+ 800000 z@0*xyz_geq@int_slack@1 + 1200000 z@0*xyz_geq@int_slack@2
- 1600000 z@1^2 - 6400000 z@1*z@2 - 800000 z@1*xyz_leq@int_slack@0
- 1600000 z@1*xyz_leq@int_slack@1 - 1600000 z@1*xyz_leq@int_slack@2
+ 800000 z@1*xyz_geq@int_slack@0 + 1600000 z@1*xyz_geq@int_slack@1
+ 2400000 z@1*xyz_geq@int_slack@2 - 6400000 z@2^2
- 1600000 z@2*xyz_leq@int_slack@0 - 3200000 z@2*xyz_leq@int_slack@1
- 3200000 z@2*xyz_leq@int_slack@2 + 1600000 z@2*xyz_geq@int_slack@0
+ 3200000 z@2*xyz_geq@int_slack@1 + 4800000 z@2*xyz_geq@int_slack@2
- 200000 xyz_leq@int_slack@0^2
- 800000 xyz_leq@int_slack@0*xyz_leq@int_slack@1
- 800000 xyz_leq@int_slack@0*xyz_leq@int_slack@2
- 800000 xyz_leq@int_slack@1^2
- 1600000 xyz_leq@int_slack@1*xyz_leq@int_slack@2
- 800000 xyz_leq@int_slack@2^2 - 200000 xyz_geq@int_slack@0^2
- 800000 xyz_geq@int_slack@0*xyz_geq@int_slack@1
- 1200000 xyz_geq@int_slack@0*xyz_geq@int_slack@2
- 800000 xyz_geq@int_slack@1^2
- 2400000 xyz_geq@int_slack@1*xyz_geq@int_slack@2
- 1800000 xyz_geq@int_slack@2^2 ]/2 -3400000
Subject To
Bounds
0 <= x <= 1
0 <= y <= 1
0 <= z@0 <= 1
0 <= z@1 <= 1
0 <= z@2 <= 1
0 <= xyz_leq@int_slack@0 <= 1
0 <= xyz_leq@int_slack@1 <= 1
0 <= xyz_leq@int_slack@2 <= 1
0 <= xyz_geq@int_slack@0 <= 1
0 <= xyz_geq@int_slack@1 <= 1
0 <= xyz_geq@int_slack@2 <= 1
Binaries
x y z@0 z@1 z@2 xyz_leq@int_slack@0 xyz_leq@int_slack@1 xyz_leq@int_slack@2
xyz_geq@int_slack@0 xyz_geq@int_slack@1 xyz_geq@int_slack@2
End
After converting the equality constraints are added to the objective function as additional terms with the default penalty factor \(M=1e5\). The resulting problem is now a QUBO and compatible with many quantum optimization algorithms.
This gives the same result as before.
[11]:
import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright
Version Information
| Qiskit Software | Version |
|---|---|
| Qiskit | 0.19.6 |
| Terra | 0.14.2 |
| Aer | 0.5.2 |
| Ignis | 0.3.3 |
| Aqua | 0.7.3 |
| IBM Q Provider | 0.7.2 |
| System information | |
| Python | 3.7.7 (default, May 6 2020, 04:59:01) [Clang 4.0.1 (tags/RELEASE_401/final)] |
| OS | Darwin |
| CPUs | 4 |
| Memory (Gb) | 16.0 |
| Fri Jul 10 15:15:34 2020 EDT | |
This code is a part of Qiskit
© Copyright IBM 2017, 2020.
This code is licensed under the Apache License, Version 2.0. You may
obtain a copy of this license in the LICENSE.txt file in the root directory
of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.
Any modifications or derivative works of this code must retain this
copyright notice, and modified files need to carry a notice indicating
that they have been altered from the originals.
[ ]: