LinearInequalityToPenalty

class LinearInequalityToPenalty(penalty=None)

ベースクラス: QuadraticProgramConverter

Convert linear inequality constraints to penalty terms of the objective function.

There are some linear constraints which do not require slack variables to construct penalty terms [1]. This class supports the following inequality constraints.

\[\begin{split}\begin{array}{} \text { Inequality constraint } & & \text { Penalty term } \\ x \leq y & \rightarrow & P(x-x y) \\ x \geq y & \rightarrow & P(y-x y) \\ \sum_{i=1}^n x_i \leq 1, n \geq 2 & \rightarrow & P \sum_{i, j : i < j} x_i x_j\\ \sum_{i=1}^n x_i \geq n-1, n \geq 2 & \rightarrow & P \sum_{i, j : i < j} (1 - x_i) (1 - x_j) \end{array}\end{split}\]

Note that x, y, z and \(x_i\) are binary variables, and P is a penalty factor, where the value of P is automatically determined or supplied by users.

If constraints match with any of the patterns, they are converted into penalty terms and added to the objective function. Otherwise, constraints are kept as is.

参照

[1]: Fred Glover, et al. (2019),

A Tutorial on Formulating and Using QUBO Models, arXiv:1811.11538.

パラメータ:

penalty (float | None) – Penalty factor to scale equality constraints that are added to objective. If None is passed, a penalty factor will be automatically calculated on every conversion.

Attributes

penalty

Returns the penalty factor used in conversion.

戻り値:

The penalty factor used in conversion.

Methods

convert(problem)

Convert inequality constraints into penalty terms of the objective function.

This methods converts the following patterns where x, y, and \(x_i\) are binary variables and P is a penalty factor.

\[\begin{split}\begin{array}{} \text { Inequality constraint } & & \text { Penalty term } \\ x \leq y & \rightarrow & P(x-x y) \\ x \geq y & \rightarrow & P(y-x y) \\ \sum_{i=1}^n x_i \leq 1, n \geq 2 & \rightarrow & P \sum_{i, j : i < j} x_i x_j\\ \sum_{i=1}^n x_i \geq n-1, n \geq 2 & \rightarrow & P \sum_{i, j : i < j} (1 - x_i) (1 - x_j) \end{array}\end{split}\]

パラメータ:

problem (QuadraticProgram) – The problem to be solved.

戻り値:

The converted problem

例外:

QiskitOptimizationError – If an unsupported-type variable exists.

戻り値の型:

QuadraticProgram

interpret(x)

Convert the result of the converted problem back to that of the original problem

パラメータ:

x (ndarray | List[float]) – The result of the converted problem or the given result in case of FAILURE.

戻り値:

The result of the original problem.

例外:

QiskitOptimizationError – if the number of variables in the result differs from that of the original problem.

戻り値の型:

ndarray