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
orBinaryQuadraticModel
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'
Attributes¶
Constraints as a dictionary. |
|
Objective to be minimized. |
|
Variables in use over the objective and all constraints. |
Methods¶
|
A convenience wrapper for other methods that add constraints. |
|
Add a constraint from a comparison. |
|
Add a constraint from an iterable of tuples. |
|
Add a constraint from a quadratic model. |
|
A convenience wrapper for other methods that add one-hot constraints. |
|
Add a one-hot constraint from a comparison. |
|
Add a one-hot constraint from an iterable. |
|
Add a one-hot constraint from a model. |
|
Add a variable to the model. |
|
Return the feasibility of the given sample. |
|
Fix the value of a variable in the model. |
|
Fix the value of the variables and remove them. |
Flip the specified binary variable in the objective and constraints. |
|
|
Alias for |
|
Construct a constrained quadratic model from a discrete quadratic model. |
|
Construct a constrained quadratic model from a discrete quadratic model. |
|
Alias for |
Construct a constrained quadratic model from a quadratic model or binary quadratic model. |
|
|
Construct from a file-like object. |
|
Create a constrained quadratic model from an LP file. |
|
Yield information about the constraints for the given sample. |
|
Yield violations for all constraints. |
|
Test for near equality to a given constrained quadratic model. |
|
Test for equality to a given constrained quadratic model. |
|
Return the lower bound on the specified variable. |
|
Number of biases in the constrained quadratic model. |
|
Number of variables with at least one quadratic interaction in the constrained quadratic model. |
|
Relabel the constraints. |
|
Relabel the variables of the objective and constraints. |
|
Remove a constraint from the model. |
|
Set the lower bound for a variable. |
|
Set the objective of the constrained quadratic model. |
|
Set the upper bound for a variable. |
Replace any self-loops in the objective or constraints. |
|
|
Serialize to a file-like object. |
|
Return the upper bound on the specified variable. |
|
Vartype of the given variable. |
|
Return a dict of violations for all constraints. |
Functions¶
Converting constrained quadratic models to other model types:
|
Construct a binary quadratic model from a constrained quadratic model. |