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^{(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[source]

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)[source]

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.