Automatic Determination of Penalty Coefficients#

1. Penalty Coefficients#

In QUBO-based modeling of real-world problems, constraints are commonly converted into penalty terms and added to the objective function. Determining suitable penalty coefficients for constraints can sometimes be time-consuming.

For traditional solvers, excessively large penalty coefficients may cause the optimizer to neglect the original objective, resulting in feasible solutions with poor objective values. For physical devices, overly large penalty coefficients may also lead to precision issues. In contrast, penalty coefficients that are too small may lead to constraints not being enforced. Therefore, estimating proper penalty coefficients is essential.

2. Estimation Method#

When the value of a discrete variable changes, if the resulting variation in the objective function is always less than the variation caused by the penalty terms, the constraints will be satisfied first. Thus, estimating the ratio of the variable’s impact on the objective and penalty terms allows us to derive penalty coefficients.

The maximum change in the objective function can be estimated using upper bounds.

$x^\top Q x = f(x_i) = \sum_j q_{ij}x_i x_j + \sum_{k\neq i,j} q_{kj} x_k x_j$

The terms related to $x_i$ can be separated from the QUBO expression.

When $x_i$ changes from 0 to 1:

$\Delta f(x_i) = \sum_j q_{ij} x_j < \sum_{q_{ij}>0} q_ij$

When $x_i$ changes from 1 to 0:

$\Delta f(x_i) = -\sum_j q_{ij} x_j < \sum_{q_{ij}<0} q_ij$

The penalty coefficient can be obtained by estimating the minimum non-zero change in penalty terms and taking the ratio.

3. Example#

import kaiwu as kw
x = kw.core.ndarray(4, 'x', kw.core.Binary)
cons = (x[0] + x[1] + 2*x[3] - 2)**2 + 2 * x[2]
obj = 3*(x[0] - x[1])**2 - 2 * x[2]

penalty = kw.core.get_min_penalty(obj, cons)
qubo_expr = obj + penalty * cons