Note

This page was generated from tutorials/optimization/2_converters_for_quadratic_programs.ipynb.

Run interactively in the IBM Quantum lab.

Converters for Quadratic Programs¶

Optimization problems in Qiskit’s optimization module are represented with the QuadraticProgram class, which is generic and powerful representation for optimization problems. In general, optimization algorithms are defined for a certain formulation of a quadratic program and we need to convert our problem to the right type.

For instance, Qiskit provides several optimization algorithms that can handle Quadratic Unconstrained Binary Optimization (QUBO) problems. These are mapped to Ising Hamiltonians, for which Qiskit uses the qiskit.aqua.operators module, and then their ground state is approximated. For this optimization commonly known algorithms such as VQE or QAOA can be used as underlying routine. See the following tutorial about the Minimum Eigen Optimizer for more detail. Note that also other algorithms exist that work differently, such as the GroverOptimizer.

To map a problem to the correct input format, the optimization module of Qiskit offers a variety of converters. In this tutorial we’re providing an overview on this functionality. Currently, Qiskit contains 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 InequalityToEquality, IntegerToBinary, and LinearEqualityToPenalty for convenience.

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 convert method of InequalityToEquality to convert.

[3]:

from qiskit.optimization.converters import InequalityToEquality

[4]:

ineq2eq = InequalityToEquality()
qp_eq = ineq2eq.convert(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 formulation of the problem looks like as the follows. As we can see, the inequality constraints are replaced with equality constraints with additional integer slack variables, \(xyz\_leg\text{@}int\_slack\) and \(xyz\_geq\text{@}int\_slack\).

Let us explain how the conversion works. For example, the lower bound of the left side of the first constraint is \(0\) which is the case of \(x=0\), \(y=0\), and \(z=0\). Thus, the upperbound of the additional integer variable must be \(5\) to be able to satisfy even the case of \(x=0\), \(y=0\), and \(z=0\). Note that we cut off the part after the decimla point in the converted formulation since the left side of the first constraint in the original formulation can be only integer values. For the second constraint, basically we apply the same approach. However, the symol in the second constraint is \(\geq\), so we add minus before \(xyz\_geq\text{@}int\_slack\) to be able to satisfy even the case of \(x=1, y=1\), and \(z=7\).

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 convert method of IntegerToBinary to convert.

[6]:

from qiskit.optimization.converters import IntegerToBinary

[7]:

int2bin = IntegerToBinary()
qp_eq_bin = int2bin.convert(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 interpret method that is the functionality to translate a given binary result back to the original integer representation.

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\). The sign of the term depends on whether the problem type is a 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 convert method of LinearEqualityToPenalty to convert.

[9]:

from qiskit.optimization.converters import LinearEqualityToPenalty

[10]:

lineq2penalty = LinearEqualityToPenalty()
qubo = lineq2penalty.convert(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: 178 x + 177 y + 177 z@0 + 354 z@1 + 708 z@2 + 110 xyz_leq@int_slack@0
      + 220 xyz_leq@int_slack@1 + 220 xyz_leq@int_slack@2
      - 66 xyz_geq@int_slack@0 - 132 xyz_geq@int_slack@1
      - 198 xyz_geq@int_slack@2 + [ - 44 x^2 - 88 x*y - 88 x*z@0 - 176 x*z@1
      - 352 x*z@2 - 44 x*xyz_leq@int_slack@0 - 88 x*xyz_leq@int_slack@1
      - 88 x*xyz_leq@int_slack@2 + 44 x*xyz_geq@int_slack@0
      + 88 x*xyz_geq@int_slack@1 + 132 x*xyz_geq@int_slack@2 - 44 y^2 - 88 y*z@0
      - 176 y*z@1 - 352 y*z@2 - 44 y*xyz_leq@int_slack@0
      - 88 y*xyz_leq@int_slack@1 - 88 y*xyz_leq@int_slack@2
      + 44 y*xyz_geq@int_slack@0 + 88 y*xyz_geq@int_slack@1
      + 132 y*xyz_geq@int_slack@2 - 44 z@0^2 - 176 z@0*z@1 - 352 z@0*z@2
      - 44 z@0*xyz_leq@int_slack@0 - 88 z@0*xyz_leq@int_slack@1
      - 88 z@0*xyz_leq@int_slack@2 + 44 z@0*xyz_geq@int_slack@0
      + 88 z@0*xyz_geq@int_slack@1 + 132 z@0*xyz_geq@int_slack@2 - 176 z@1^2
      - 704 z@1*z@2 - 88 z@1*xyz_leq@int_slack@0 - 176 z@1*xyz_leq@int_slack@1
      - 176 z@1*xyz_leq@int_slack@2 + 88 z@1*xyz_geq@int_slack@0
      + 176 z@1*xyz_geq@int_slack@1 + 264 z@1*xyz_geq@int_slack@2 - 704 z@2^2
      - 176 z@2*xyz_leq@int_slack@0 - 352 z@2*xyz_leq@int_slack@1
      - 352 z@2*xyz_leq@int_slack@2 + 176 z@2*xyz_geq@int_slack@0
      + 352 z@2*xyz_geq@int_slack@1 + 528 z@2*xyz_geq@int_slack@2
      - 22 xyz_leq@int_slack@0^2 - 88 xyz_leq@int_slack@0*xyz_leq@int_slack@1
      - 88 xyz_leq@int_slack@0*xyz_leq@int_slack@2 - 88 xyz_leq@int_slack@1^2
      - 176 xyz_leq@int_slack@1*xyz_leq@int_slack@2 - 88 xyz_leq@int_slack@2^2
      - 22 xyz_geq@int_slack@0^2 - 88 xyz_geq@int_slack@0*xyz_geq@int_slack@1
      - 132 xyz_geq@int_slack@0*xyz_geq@int_slack@2 - 88 xyz_geq@int_slack@1^2
      - 264 xyz_geq@int_slack@1*xyz_geq@int_slack@2 - 198 xyz_geq@int_slack@2^2
      ]/2 -374
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 such as VQE, QAOA and so on.

This gives the same result as before.

[11]:

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
Qiskit	0.24.1
Terra	0.16.4
Aer	0.7.6
Ignis	0.5.2
Aqua	0.8.2
IBM Q Provider	0.12.2
System information
Python	3.7.7 (default, Apr 22 2020, 19:15:10) [GCC 9.3.0]
OS	Linux
CPUs	32
Memory (Gb)	125.71903228759766
Tue May 25 15:30:31 2021 EDT

This code is a part of Qiskit

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.

[ ]: