Penalty Models¶
Penalty models represent constraints as small models such as Binary Quadratic Modelss that have higher values for infeasible states (values of variables that violate the constraint). By adding such models to the objective function that represents your problem, you make it less likely that solutions that violate the constraint are selected by solvers that seek low-energy states.
For example, consider that you are looking for solutions to a problem that is
represented by a binary quadratic model, bqm_p
, which has variables
\(v_1, v_2, v_3, v_4, v_5, ...\) etc. You wish to constrain the solutions to
ones where \(v_2 \Leftrightarrow \neg v_4\); that is, variables \(v_2\)
and \(v_4\) never have the same value in good solutions.
The relation \(v_2 \Leftrightarrow \neg v_4\) represents a NOT gate, where one variable, say \(v_2\) is the gate’s input and the other, say \(v_4\) its output.
You can represent such a constraint with the penalty function:
This penalty function represents the constraint in that for assignments of variables that
match valid states (\(v_2 \ne v_4\)), the function evaluates at a lower value
than assignments that violate the constraint. Therefore, when you minimize the
sum of your objective function (bqm_p
) and a BQM representing this
penalty function, those assignments of variables that meet the constraint have
lower values.
The table below shows that this function penalizes states that violate the constraint while no penalty is applied to assignments of variables that meet the constraint. In this table, columns \(\mathbf{v_2}\) and \(\mathbf{v_4}\) show all possible states of variables \(v_2\) and \(v4\); column Valid? shows whether the variables represent meet the constraint; column \(\mathbf{P}\) shows the value of the penalty for all possible assignments of variables.
\(\mathbf{v_2}\) |
\(\mathbf{v_4}\) |
Valid? |
\(\mathbf{P}\) |
---|---|---|---|
\(0\) |
\(1\) |
Yes |
\(0\) |
\(1\) |
\(0\) |
Yes |
\(0\) |
\(0\) |
\(0\) |
No |
\(1\) |
\(1\) |
\(1\) |
No |
\(1\) |
For example, the state \(v_2, v_4 = 0,1\) of the first row represents valid assignments, and the value of \(P\) is
not penalizing the valid assignment of variables. In contrast, the state \(v_2, v_4 = 0,0\) of the third row represents an infeasible assignment, and the value of \(P\) is
adding a value of \(1\) to the BQM being minimized, bqm_p
. By
penalizing both possible assignments of variables that violate the constraint,
the BQM based on this penalty function has minimal values (lowest energy states)
for variable values that meet the constraint.
See the D-Wave Problem-Solving Handbook for more information about penalty functions in general, and penalty functions for representing Boolean operations.