# Quadratic Models: Constrained¶

## CQM Class¶

A constrained quadratic model.

Constrained quadratic models are problems of the form:

\begin{split}\begin{align} \text{Minimize an objective:} & \\ & \sum_{i} a_i x_i + \sum_{i \le j} b_{ij} x_i x_j + c, \\ \text{Subject to constraints:} & \\ & \sum_i a_i^{(c)} x_i + \sum_{i \le 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 \le 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 binary1 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.

1

For binary variables, the range of the quadratic-term summation is $$i < j$$ because $$x^2 = x$$ for binary values $$\{0, 1\}$$ and $$s^2 = 1$$ for spin values $$\{-1, 1\}$$.

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

Example

This example solves the simple bin packing problem of packing a set of items of different weights into the smallest possible number of bins.

dimod provides a general random_bin_packing() function to generate bin packing problems, and this example follows the same naming conventions.

Consider four objects with weights between 0 and 1, and assume that each bin has a capacity to hold up to a total weight of 1.

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


Variable $$y_j$$ indicates that bin $$j$$ is used. Clearly, no more than four bins are needed.

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


Variable $$x_{i,j}$$ indicates that item $$i$$ is put 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 (“empty” meaning that no objective or constraints have set).

>>> cqm = dimod.ConstrainedQuadraticModel()


The problem is to minimize the number of bins used. Therefore the objective is to minimize the value of $$\sum_j y_j$$.

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


Any feasible solution must meet the constraint that each item can only go in one bin. You 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 you can access them in the future if desired.

>>> for i in range(len(weights)):
...     cqm.add_constraint(sum(x[i]) == 1, label=f'item_placing_{i}')
'item_placing_0'
'item_placing_1'
'item_placing_2'
'item_placing_3'


Finally, enforce the limits on each bin. You 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¶

 constraints Constraints as a dictionary. objective Objective to be minimized. variables Variables in use over the objective and all constraints.

### Methods¶

 add_constraint(data, *args, **kwargs) Add a constraint to the model. add_constraint_from_comparison(comp[, ...]) Add a constraint from a symbolic comparison. add_constraint_from_iterable(iterable, sense) Add a constraint from an iterable of tuples. add_constraint_from_model(qm, sense[, rhs, ...]) Add a constraint from a quadratic model. add_discrete(data, *args, **kwargs) A convenience wrapper for other methods that add one-hot constraints. add_discrete_from_comparison(comp[, label, copy]) Add a one-hot constraint from a comparison. add_discrete_from_iterable(variables[, label]) Add a one-hot constraint from an iterable. add_discrete_from_model(qm[, label, copy]) Add a one-hot constraint from a model. add_variable(vartype[, v, lower_bound, ...]) Add a variable to the model. check_feasible(sample_like[, rtol, atol]) Return the feasibility of the given sample. fix_variable(v, value, *[, cascade]) Fix the value of a variable in the model. fix_variables(fixed, *[, cascade]) Fix the value of the variables and remove them. Flip the specified binary variable in the objective and constraints. from_bqm(bqm) Alias for from_quadratic_model(). from_discrete_quadratic_model(dqm, *[, ...]) Construct a constrained quadratic model from a discrete quadratic model. from_dqm(dqm, *[, relabel_func]) 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. from_file(fp, *[, check_header]) Construct from a file-like object. from_lp_file(fp[, lower_bound_default, ...]) Create a constrained quadratic model from an LP file. iter_constraint_data(sample_like) Yield information about the constraints for the given sample. iter_violations(sample_like, *[, ...]) Yield violations for all constraints. is_almost_equal(other[, places]) Test for near equality to a given constrained quadratic model. is_equal(other) Test for equality to a given constrained quadratic model. Return True if the model has no quadratic interactions. Return the lower bound on the specified variable. num_biases([vartype, linear_only]) Number of biases in the constrained quadratic model. num_quadratic_variables([vartype, ...]) Number of variables with at least one quadratic interaction in the constrained quadratic model. relabel_constraints(mapping) Relabel the constraints. relabel_variables(mapping[, inplace]) Relabel the variables of the objective and constraints. remove_constraint(label, *[, cascade]) Remove a constraint from the model. set_lower_bound(v, lb) Set the lower bound for a variable. set_objective(objective) Set the objective of the constrained quadratic model. set_upper_bound(v, ub) Set the upper bound for a variable. spin_to_binary([inplace]) Convert any spin-valued variables to binary-valued. Replace any self-loops in the objective or constraints. to_file(*[, spool_size]) Serialize to a file-like object. Return the upper bound on the specified variable. Vartype of the given variable. violations(sample_like, *[, skip_satisfied, ...]) Return a dict of violations for all constraints.

## Sense Class¶

class Sense(value)[source]

Sense of a constraint.

Supported values are:

• Le: less or equal ($$\le$$)

• Ge: greater or equal ($$\ge$$)

• Eq: equal ($$=$$)

Example

>>> from dimod import ConstrainedQuadraticModel, Integer
>>> i = Integer("i")
>>> cqm = ConstrainedQuadraticModel()
>>> cqm.add_constraint(i <= 3, "i le 3")
'i le 3'


## 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.