Quadratic Models: Constrained¶

CQM 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 \le j} b_{ij} x_i x_j + c, \\ \text{Subject to constraints:} & \\ & \sum_i a_i^{(m)} x_i + \sum_{i \le j} b_{ij}^{(m)} x_i x_j+ c^{(m)} \circ 0, \quad m=1, \dots, M, \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, \(\circ \in \{ \ge, \le, = \}\) and \(M\) is the total number of constraints.

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\}\).

Constraints are often categorized as either “hard” or “soft”. Any hard constraint must be satisfied for a solution of the model to qualify as feasible. Soft constraints may be violated to achieve an overall good solution. By setting appropriate weights to soft constraints in comparison to the objective and to other soft constraints, you can express the relative importance of such constraints.

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)):
...     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.constrained.ConstrainedQuadraticModel

Attributes¶

`constraints`	Constraints as a mapping.
`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_variable`(v)	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.
`from_qm`(qm)	Alias for `from_quadratic_model()`.
`from_quadratic_model`(qm)	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.
`is_linear`()	Return True if the model has no quadratic interactions.
`lower_bound`	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`	Set the lower bound for a variable.
`set_objective`	Set the objective of the constrained quadratic model.
`set_upper_bound`	Set the upper bound for a variable.
`spin_to_binary`([inplace])	Convert any spin-valued variables to binary-valued.
`substitute_self_loops`()	Replace any self-loops in the objective or constraints.
`to_file`(*[, spool_size])	Serialize to a file-like object.
`upper_bound`	Return the upper bound on the specified variable.
`vartype`	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.