Quadratic Models: Constrained

CQM Class

class ConstrainedQuadraticModel

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

alias of dimod.constrained.ConstrainedQuadraticModel

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)	A convenience wrapper for other methods that add constraints.
add_constraint_from_comparison(comp[, ...])	Add a constraint from a 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.
lower_bound(v)	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.
substitute_self_loops()	Replace any self-loops in the objective or constraints.
to_file(*[, spool_size])	Serialize to a file-like object.
upper_bound(v)	Return the upper bound on the specified variable.
vartype(v)	Vartype of the given variable.
violations(sample_like, *[, skip_satisfied, ...])	Return a dict of violations for all constraints.

Sense Class

class Sense(value)

An enumeration.

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.