# This code is part of a Qiskit project.
#
# (C) Copyright IBM 2020, 2025.
#
# 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.
"""The inequality to equality converter."""
from __future__ import annotations
import copy
import math
import numpy as np
from ..exceptions import QiskitOptimizationError
from ..problems.constraint import Constraint
from ..problems.linear_constraint import LinearConstraint
from ..problems.quadratic_constraint import QuadraticConstraint
from ..problems.quadratic_objective import QuadraticObjective
from ..problems.quadratic_program import QuadraticProgram
from ..problems.variable import Variable
from .quadratic_program_converter import QuadraticProgramConverter
[docs]
class InequalityToEquality(QuadraticProgramConverter):
"""Convert inequality constraints into equality constraints by introducing slack variables.
Examples:
>>> from qiskit_optimization.problems import QuadraticProgram
>>> from qiskit_optimization.converters import InequalityToEquality
>>> problem = QuadraticProgram()
>>> # define a problem
>>> conv = InequalityToEquality()
>>> problem2 = conv.convert(problem)
"""
_delimiter = "@" # users are supposed not to use this character in variable names
def __init__(self, mode: str = "auto") -> None:
"""
Args:
mode: To choose the type of slack variables. There are 3 options for mode.
- 'integer': All slack variables will be integer variables.
- 'continuous': All slack variables will be continuous variables.
- 'auto': Use integer variables if possible, otherwise use continuous variables.
"""
self._src: QuadraticProgram | None = None
self._dst: QuadraticProgram | None = None
self._mode = mode
[docs]
def convert(self, problem: QuadraticProgram) -> QuadraticProgram:
"""Convert a problem with inequality constraints into one with only equality constraints.
Args:
problem: The problem to be solved, that may contain inequality constraints.
Returns:
The converted problem, that contain only equality constraints.
Raises:
QiskitOptimizationError: If a variable type is not supported.
QiskitOptimizationError: If an unsupported mode is selected.
QiskitOptimizationError: If an unsupported sense is specified.
"""
self._src = copy.deepcopy(problem)
self._dst = QuadraticProgram(name=problem.name)
# set a converting mode
mode = self._mode
if mode not in ["integer", "continuous", "auto"]:
raise QiskitOptimizationError(f"Unsupported mode is selected: {mode}")
# Copy variables
for x in self._src.variables:
if x.vartype == Variable.Type.BINARY:
self._dst.binary_var(name=x.name)
elif x.vartype == Variable.Type.INTEGER:
self._dst.integer_var(name=x.name, lowerbound=x.lowerbound, upperbound=x.upperbound)
elif x.vartype == Variable.Type.CONTINUOUS:
self._dst.continuous_var(
name=x.name, lowerbound=x.lowerbound, upperbound=x.upperbound
)
else:
raise QiskitOptimizationError(f"Unsupported variable type {x.vartype}")
# Note: QuadraticProgram needs to add all variables before adding any constraints.
# Add slack variables to linear constraints
new_linear_constraints = []
for lin_const in self._src.linear_constraints:
if lin_const.sense == Constraint.Sense.EQ:
new_linear_constraints.append(
(lin_const.linear.coefficients, lin_const.sense, lin_const.rhs, lin_const.name)
)
elif lin_const.sense in [Constraint.Sense.LE, Constraint.Sense.GE]:
new_linear_constraints.append(self._add_slack_var_linear_constraint(lin_const))
else:
raise QiskitOptimizationError(
f"Internal error: type of sense in {lin_const.name} is not supported: "
f"{lin_const.sense}"
)
# Add slack variables to quadratic constraints
new_quadratic_constraints = []
for quad_const in self._src.quadratic_constraints:
if quad_const.sense == Constraint.Sense.EQ:
new_quadratic_constraints.append(
(
quad_const.linear.coefficients,
quad_const.quadratic.coefficients,
quad_const.sense,
quad_const.rhs,
quad_const.name,
)
)
elif quad_const.sense in [Constraint.Sense.LE, Constraint.Sense.GE]:
new_quadratic_constraints.append(
self._add_slack_var_quadratic_constraint(quad_const)
)
else:
raise QiskitOptimizationError(
f"Internal error: type of sense in {quad_const.name} is not supported: "
f"{quad_const.sense}"
)
# Copy the objective function
constant = self._src.objective.constant
linear = self._src.objective.linear.to_dict(use_name=True)
quadratic = self._src.objective.quadratic.to_dict(use_name=True)
if self._src.objective.sense == QuadraticObjective.Sense.MINIMIZE:
self._dst.minimize(constant, linear, quadratic)
else:
self._dst.maximize(constant, linear, quadratic)
# Add linear constraints
for lin_const_args in new_linear_constraints:
self._dst.linear_constraint(*lin_const_args)
# Add quadratic constraints
for quad_const_args in new_quadratic_constraints:
self._dst.quadratic_constraint(*quad_const_args)
return self._dst
def _add_slack_var_linear_constraint(self, constraint: LinearConstraint):
linear = constraint.linear
sense = constraint.sense
name = constraint.name
any_float = self._any_float(linear.to_array())
mode = self._mode
if mode == "integer":
if any_float:
raise QiskitOptimizationError(
f'"{name}" contains float coefficients. '
'We can not use an integer slack variable for "{name}"'
)
elif mode == "auto":
mode = "continuous" if any_float else "integer"
new_rhs = constraint.rhs
if mode == "integer":
# If rhs is float number, round up/down to the nearest integer.
if sense == Constraint.Sense.LE:
new_rhs = math.floor(new_rhs)
if sense == Constraint.Sense.GE:
new_rhs = math.ceil(new_rhs)
lin_bounds = linear.bounds
lhs_lb = lin_bounds.lowerbound
lhs_ub = lin_bounds.upperbound
var_ub = 0.0
sign = 0
if sense == Constraint.Sense.LE:
var_ub = new_rhs - lhs_lb
if var_ub > 0:
sign = 1
elif sense == Constraint.Sense.GE:
var_ub = lhs_ub - new_rhs
if var_ub > 0:
sign = -1
new_linear = linear.to_dict(use_name=True)
if var_ub > 0:
# Add a slack variable.
mode_name = {"integer": "int", "continuous": "continuous"}
slack_name = f"{name}{self._delimiter}{mode_name[mode]}_slack"
if mode == "integer":
self._dst.integer_var(name=slack_name, lowerbound=0, upperbound=var_ub)
elif mode == "continuous":
self._dst.continuous_var(name=slack_name, lowerbound=0, upperbound=var_ub)
new_linear[slack_name] = sign
return new_linear, "==", new_rhs, name
def _add_slack_var_quadratic_constraint(self, constraint: QuadraticConstraint):
quadratic = constraint.quadratic
linear = constraint.linear
sense = constraint.sense
name = constraint.name
any_float = self._any_float(linear.to_array()) or self._any_float(quadratic.to_array())
mode = self._mode
if mode == "integer":
if any_float:
raise QiskitOptimizationError(
f'"{name}" contains float coefficients. '
'We can not use an integer slack variable for "{name}"'
)
elif mode == "auto":
mode = "continuous" if any_float else "integer"
new_rhs = constraint.rhs
if mode == "integer":
# If rhs is float number, round up/down to the nearest integer.
if sense == Constraint.Sense.LE:
new_rhs = math.floor(new_rhs)
if sense == Constraint.Sense.GE:
new_rhs = math.ceil(new_rhs)
lin_bounds = linear.bounds
quad_bounds = quadratic.bounds
lhs_lb = lin_bounds.lowerbound + quad_bounds.lowerbound
lhs_ub = lin_bounds.upperbound + quad_bounds.upperbound
var_ub = 0.0
sign = 0
if sense == Constraint.Sense.LE:
var_ub = new_rhs - lhs_lb
if var_ub > 0:
sign = 1
elif sense == Constraint.Sense.GE:
var_ub = lhs_ub - new_rhs
if var_ub > 0:
sign = -1
new_linear = linear.to_dict(use_name=True)
if var_ub > 0:
# Add a slack variable.
mode_name = {"integer": "int", "continuous": "continuous"}
slack_name = f"{name}{self._delimiter}{mode_name[mode]}_slack"
if mode == "integer":
self._dst.integer_var(name=slack_name, lowerbound=0, upperbound=var_ub)
elif mode == "continuous":
self._dst.continuous_var(name=slack_name, lowerbound=0, upperbound=var_ub)
new_linear[slack_name] = sign
return new_linear, quadratic.coefficients, "==", new_rhs, name
[docs]
def interpret(self, x: np.ndarray | list[float]) -> np.ndarray:
"""Convert a result of a converted problem into that of the original problem.
Args:
x: The result of the converted problem or the given result in case of FAILURE.
Returns:
The result of the original problem.
"""
# convert back the optimization result into that of the original problem
names = [var.name for var in self._dst.variables]
# interpret slack variables
sol = {name: x[i] for i, name in enumerate(names)}
new_x = np.zeros(self._src.get_num_vars())
for i, var in enumerate(self._src.variables):
new_x[i] = sol[var.name]
return new_x
@staticmethod
def _any_float(values: np.ndarray) -> bool:
"""Check whether the list contains float or not.
This method is used to check whether a constraint contain float coefficients or not.
Args:
values: Coefficients of the constraint
Returns:
bool: If the constraint contains float coefficients, this returns True, else False.
"""
return any(isinstance(v, float) and not v.is_integer() for v in values)
@property
def mode(self) -> str:
"""Returns the mode of the converter
Returns:
The mode of the converter used for additional slack variables
"""
return self._mode
@mode.setter
def mode(self, mode: str) -> None:
"""Set a new mode for the converter
Args:
mode: The new mode for the converter
"""
self._mode = mode