Quadratic Models: Constrained¶

Class¶

class ConstrainedQuadraticModel[source]¶

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<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)):
...     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, 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)):
...     cqm.add_constraint(
...         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]¶: alias of dimod.constrained.ConstrainedQuadraticModel

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¶

`ConstrainedQuadraticModel.add_constraint`(...)	A convenience wrapper for other methods that add constraints.
`ConstrainedQuadraticModel.add_constraint_from_comparison`(comp)	Add a constraint from a comparison.
`ConstrainedQuadraticModel.add_constraint_from_iterable`(...)	Add a constraint from an iterable of tuples.
`ConstrainedQuadraticModel.add_constraint_from_model`(qm, ...)	Add a constraint from a quadratic model.
`ConstrainedQuadraticModel.add_discrete`(variables)	Add an iterable of binary variables as a disjoint one-hot constraint.
`ConstrainedQuadraticModel.add_variable`(v, ...)	Add a variable to the model.
`ConstrainedQuadraticModel.check_feasible`(...)	Return the feasibility of the given sample.
`ConstrainedQuadraticModel.from_bqm`(bqm)	Alias for `from_quadratic_model()`.
`ConstrainedQuadraticModel.from_discrete_quadratic_model`(dqm, *)	Construct a constrained quadratic model from a discrete quadratic model.
`ConstrainedQuadraticModel.from_dqm`(dqm, *[, ...])	Construct a constrained quadratic model from a discrete quadratic model.
`ConstrainedQuadraticModel.from_qm`(qm)	Alias for `from_quadratic_model()`.
`ConstrainedQuadraticModel.from_quadratic_model`(qm)	Construct a constrained quadratic model from a quadratic model or binary quadratic model.
`ConstrainedQuadraticModel.from_file`(fp)	Construct from a file-like object.
`ConstrainedQuadraticModel.iter_constraint_data`(...)	Yield information about the constraints for the given sample.
`ConstrainedQuadraticModel.iter_violations`(...)	Yield violations for all constraints.
`ConstrainedQuadraticModel.is_almost_equal`(other)	Return True if the given model's objective and constraints are almost equal.
`ConstrainedQuadraticModel.is_equal`(other)	Return True if the given model has the same objective and constraints.
`ConstrainedQuadraticModel.num_biases`()	The number of biases accross the objective and constraints.
`ConstrainedQuadraticModel.num_quadratic_variables`()	Return the total number of variables with at least one quadratic interaction accross all constraints.
`ConstrainedQuadraticModel.set_objective`(...)	Set the objective of the constrained quadratic model.
`ConstrainedQuadraticModel.substitute_self_loops`()	Replace any integer self-loops in the objective or constraints.
`ConstrainedQuadraticModel.to_file`(*[, ...])	Serialize to a file-like object.
`ConstrainedQuadraticModel.vartype`(v)	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.