LinearInequalityToPenalty

class LinearInequalityToPenalty(penalty=None)

Bases: 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.

References

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

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

Parameters:

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.

Returns:

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}\]

Parameters:

problem (QuadraticProgram) – The problem to be solved.

Returns:

The converted problem

Raises:

QiskitOptimizationError – If an unsupported-type variable exists.

Return type:

QuadraticProgram

interpret(x)

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

Parameters:

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

Returns:

The result of the original problem.

Raises:

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

Return type:

ndarray