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:

\[2v_2v_4 - v_2 - v_4 + 1.\]

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.

Boolean NOT Constraint Represented by a Penalty Function.

\(\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

\[2v_2v_4 - v_2 - v_4 + 1 = 2 \times 0 \times 1 - 0 - 1 + 1 = -1+1=0,\]

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

\[2v_2v_4 - v_2 - v_4 + 1 = 2 \times 0 \times 0 -0 -0 +1 =1,\]

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.