## Class¶

Constrained quadratic models are problems of the form:

\begin{split}\begin{align} \text{Minimize an objective:} & \\ & \sum_{i} a_i x_i + \sum_{i<j} b_{ij} x_i x_j + c, \\ \text{Subject to constraints:} & \\ & \sum_i a_i^{(c)} x_i + \sum_{i<j} b_{ij}^{(c)} x_i x_j+ c^{(c)} \le 0, \quad c=1, \dots, C_{\rm ineq.}, \\ & \sum_i a_i^{(d)} x_i + \sum_{i<j} b_{ij}^{(d)} x_i x_j + c^{(d)} = 0, \quad d=1, \dots, C_{\rm eq.}, \end{align}\end{split}

where $$\{ x_i\}_{i=1, \dots, N}$$ can be binary or integer variables, $$a_{i}, b_{ij}, c$$ are real values and $$C_{\rm ineq.}, C_{\rm eq,}$$ are the number of inequality and equality constraints respectively.

The objective and constraints are encoded as either QuadraticModel or BinaryQuadraticModel depending on the variable types used.

Example

Solve a simple bin packing problem. In this problem we wish to pack a set of items of different weights into the smallest number of bins possible.

See bin_packing() for a general function to generate bin packing problems. We follow the same naming conventions in this example.

Let’s start with four object weights and assume that each bin has a capacity of 1.

>>> weights = [.9, .7, .2, .1]
>>> capacity = 1


Let $$y_j$$ indicate that we used bin $$j$$. We know that we will use four or fewer total bins.

>>> y = [dimod.Binary(f'y_{j}') for j in range(len(weights))]


Let $$x_{i,j}$$ indicate that we put item $$i$$ in bin $$j$$.

>>> x = [[dimod.Binary(f'x_{i}_{j}') for j in range(len(weights))]
...      for i in range(len(weights))]


Create an empty constrained quadratic model with no objective or constraints.

>>> cqm = dimod.ConstrainedQuadraticModel()


We wish to minimize the number of bins used. Therefore our objective is to minimize the value of $$\sum_j y_j$$.

>>> cqm.set_objective(sum(y))


We also need to enforce the constraint that each item can only go in one bin. We can express this constraint, for a given item $$i$$, with $$\sum_j x_{i, j} == 1$$. Note that the label of each constraint is returned so that we can access them in the future if desired.

>>> for i in range(len(weights)):
'item_placing_0'
'item_placing_1'
'item_placing_2'
'item_placing_3'


Finally, we need to enforce the limits on each bin. We can express this constraint, for a given bin $$j$$, with $$\sum_i x_{i, j} * w_i <= c$$ where $$w_i$$ is the weight of item $$i$$ and $$c$$ is the capacity.

>>> for j in range(len(weights)):
...         sum(weights[i] * x[i][j] for i in range(len(weights))) - y[j] * capacity <= 0,
...         label=f'capacity_bin_{j}')
'capacity_bin_0'
'capacity_bin_1'
'capacity_bin_2'
'capacity_bin_3'

CQM[source]

### Attributes¶

 ConstrainedQuadraticModel.constraints The constraints as a dictionary. ConstrainedQuadraticModel.objective The objective to be minimized. ConstrainedQuadraticModel.variables The variables in use over the objective and all constraints.

### Methods¶

 A convenience wrapper for other methods that add constraints. Add a constraint from a comparison. Add a constraint from an iterable of tuples. Add a constraint from a quadratic model. Add an iterable of binary variables as a disjoint one-hot constraint. Add a variable to the model. Return the feasibility of the given sample. Alias for from_quadratic_model(). Construct a constrained quadratic model from a discrete quadratic model. ConstrainedQuadraticModel.from_dqm(dqm, *[, ...]) Construct a constrained quadratic model from a discrete quadratic model. Alias for from_quadratic_model(). Construct a constrained quadratic model from a quadratic model or binary quadratic model. Construct from a file-like object. Yield information about the constraints for the given sample. Yield violations for all constraints. Return True if the given model's objective and constraints are almost equal. Return True if the given model has the same objective and constraints. The number of biases accross the objective and constraints. Return the total number of variables with at least one quadratic interaction accross all constraints. Set the objective of the constrained quadratic model. Replace any integer self-loops in the objective or constraints. Serialize to a file-like object. The vartype of the given variable. ConstrainedQuadraticModel.violations(...[, ...]) Return a dictionary mapping constraint labels to the amount the constraints are violated.

## Functions¶

Converting constrained quadratic models to other model types:

 cqm_to_bqm(cqm[, lagrange_multiplier]) Construct a binary quadratic model from a constrained quadratic model.