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.