Nonlinear Models

This page describes the dwave-optimization package’s nonlinear model: classes, attributes, and methods.

For examples, see Ocean’s Getting Started examples.

Nonlinear models are especially suited for use with decision variables that represent a common logic, such as subsets of choices or permutations of ordering. For example, in a traveling salesperson problem permutations of the variables representing cities can signify the order of the route being optimized and in a knapsack problem the variables representing items can be divided into subsets of packed and not packed.

Model Class

class Model

Nonlinear model.

The nonlinear model represents a general optimization problem with an objective function and/or constraints over variables of various types.

The Model class can contain this model and its methods provide convenient utilities for working with representations of a problem.

Examples

This example creates a model for a flow-shop-scheduling problem with two jobs on three machines.

>>> from dwave.optimization.generators import flow_shop_scheduling
...
>>> processing_times = [[10, 5, 7], [20, 10, 15]]
>>> model = flow_shop_scheduling(processing_times=processing_times)

objective: ArraySymbol | None

Objective to be minimized.

Examples

This example prints the value of the objective of a model representing the simple polynomial, \(y = i^2 - 4i\), for a state with value \(i=2.0\).

>>> from dwave.optimization import Model
...
>>> model = Model()
>>> i = model.integer(lower_bound=-5, upper_bound=5)
>>> c = model.constant(4)
>>> y = i**2 - c*i
>>> model.minimize(y)
>>> with model.lock():
...     model.states.resize(1)
...     i.set_state(0, 2.0)
...     print(f"Objective = {model.objective.state(0)}")
Objective = -4.0

states: States

States of the model.

States represent assignments of values to a symbol.

See also

States methods such as size() and resize().

binary(shape: Optional[_ShapeLike] = None) → BinaryVariable

Create a binary symbol as a decision variable.

Parameters:

shape – Shape of the binary array to create.

Returns:

A binary symbol.

Examples

This example creates a \(1 \times 20\)-sized binary symbol.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> x = model.binary((1,20))

constant(array_like: numpy.typing.ArrayLike) → Constant

Create a constant symbol.

Parameters:

array_like – An array-like representing a constant. Can be a scalar or a NumPy array. If the array’s dtype is np.double, the array is not copied.

Returns:

A constant symbol.

Examples

This example creates a \(1 \times 4\)-sized constant symbol with the specified values.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> time_limits = model.constant([10, 15, 5, 8.5])

disjoint_bit_sets(primary_set_size: int, num_disjoint_sets: int) → tuple[DisjointBitSets, tuple[DisjointBitSet, ...]]

Create a disjoint-sets symbol as a decision variable.

Divides a set of the elements of range(primary_set_size) into num_disjoint_sets ordered partitions, stored as bit sets (arrays of length primary_set_size, with ones at the indices of elements currently in the set, and zeros elsewhere). The ordering of a set is not semantically meaningful.

Also creates from the symbol num_disjoint_sets extra successors that output the disjoint sets as arrays.

Parameters:

• primary_set_size – Number of elements in the primary set that are partitioned into disjoint sets. Must be non-negative.

• num_disjoint_sets – Number of disjoint sets. Must be positive.

Returns:

A tuple where the first element is the disjoint-sets symbol and the second is a set of its newly added successors.

Examples

This example creates a symbol of 10 elements that is divided into 4 sets.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> parts_set, parts_subsets = model.disjoint_bit_sets(10, 4)

disjoint_lists(primary_set_size: int, num_disjoint_lists: int) → tuple[DisjointLists, tuple[DisjointList, ...]]

Create a disjoint-lists symbol as a decision variable.

Divides a set of the elements of range(primary_set_size) into num_disjoint_lists ordered partitions.

Also creates num_disjoint_lists extra successors from the symbol that output the disjoint lists as arrays.

Parameters:

• primary_set_size – Number of elements in the primary set to be partitioned into disjoint lists.

• num_disjoint_lists – Number of disjoint lists.

Returns:

A tuple where the first element is the disjoint-lists symbol and the second is a list of its newly added successor nodes.

Examples

This example creates a symbol of 10 elements that is divided into 4 lists.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> destinations, routes = model.disjoint_lists(10, 4)

feasible(index: int = 0) → bool

Check the feasibility of the state at the input index.

Parameters:

index – index of the state to check for feasibility.

Returns:

Feasibility of the state.

Examples

This example demonstrates checking the feasibility of a simple model with feasible and infeasible states.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> b = model.binary()
>>> model.add_constraint(b) 
<dwave.optimization.symbols.BinaryVariable at ...>
>>> model.states.resize(2)
>>> b.set_state(0, 1) # Feasible
>>> b.set_state(1, 0) # Infeasible
>>> with model.lock():
...     model.feasible(0)
True
>>> with model.lock():
...     model.feasible(1)
False

integer(shape: Optional[_ShapeLike] = None, lower_bound: Optional[int] = None, upper_bound: Optional[int] = None) → IntegerVariable

Create an integer symbol as a decision variable.

Parameters:

• shape – Shape of the integer array to create.

• lower_bound – Lower bound for the symbol, which is the smallest allowed integer value. If None, the default value is used.

• upper_bound – Upper bound for the symbol, which is the largest allowed integer value. If None, the default value is used.

Returns:

An integer symbol.

Examples

This example creates a \(20 \times 20\)-sized integer symbol.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> i = model.integer((20,20), lower_bound=-100, upper_bound=100)

list(n: int) → ListVariable

Create a list symbol as a decision variable.

Parameters:

n – Values in the list are permutations of range(n).

Returns:

A list symbol.

Examples

This example creates a list symbol of 200 elements.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> routes = model.list(200)

lock() → AbstractContextManager

Lock the model.

No new symbols can be added to a locked model.

Returns:

A context manager. If the context is subsequently exited then the unlock() will be called.

See also

is_locked(), unlock()

Examples

This example checks the status of a model after locking it and subsequently unlocking it.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> i = model.integer(20, upper_bound=100)
>>> cntx = model.lock()
>>> model.is_locked()
True
>>> model.unlock()
>>> model.is_locked()
False

This example locks a model temporarily with a context manager.

>>> model = Model()
>>> with model.lock():
...     # no nodes can be added within the context
...     print(model.is_locked())
True
>>> model.is_locked()
False

minimize(value: ArraySymbol)

Set the objective value to minimize.

Optimization problems have an objective and/or constraints. The objective expresses one or more aspects of the problem that should be minimized (equivalent to maximization when multiplied by a minus sign). For example, an optimized itinerary might minimize the value of distance traveled or cost of transportation or travel time.

Parameters:

value – Value for which to minimize the cost function.

Examples

This example minimizes a simple polynomial, \(y = i^2 - 4i\), within bounds.

>>> from dwave.optimization import Model
>>> model = Model()
>>> i = model.integer(lower_bound=-5, upper_bound=5)
>>> c = model.constant(4)
>>> y = i*i - c*i
>>> model.minimize(y)

quadratic_model(x: ArraySymbol, quadratic, linear=None) → QuadraticModel

Create a quadratic model from an array and a quadratic model.

Parameters:

• x – An array.

• quadratic – Quadratic values for the quadratic model.

• linear – Linear values for the quadratic model.

Returns:

A quadratic model.

Examples

This example creates a quadratic model.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> x = model.binary(3)
>>> Q = {(0, 0): 0, (0, 1): 1, (0, 2): 2, (1, 1): 1, (1, 2): 3, (2, 2): 2}
>>> qm = model.quadratic_model(x, Q)

add_constraint(value)

Add a constraint to the model.

Parameters:

value – Value that must evaluate to True for the state of the model to be feasible.

Returns:

The constraint symbol.

Examples

This example adds a single constraint to a model.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> i = model.integer()
>>> c = model.constant(5)
>>> constraint_sym = model.add_constraint(i <= c)

The returned constraint symbol can be assigned and evaluated for a model state:

>>> with model.lock():
...     model.states.resize(1)
...     i.set_state(0, 1) # Feasible state
...     print(constraint_sym.state(0))
1.0
>>> with model.lock():
...     i.set_state(0, 6) # Infeasible state
...     print(constraint_sym.state(0))
0.0

decision_state_size()

An estimated size, in bytes, of the model’s decision states.

Examples

This example checks the size of a model with one \(10 \times 10\)-sized integer symbol.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> visit_site = model.integer((10, 10))
>>> model.decision_state_size()
800

classmethod from_file(file, *, check_header=True)

Construct a model from the given file.

Parameters:

file – File pointer to a readable, seekable file-like object encoding a model. Strings are interpreted as a file name.

Returns:

A model.

See also

into_file(), to_file()

into_file(file, *, max_num_states=0, only_decision=False)

Serialize the model into an existing file.

Parameters:

• file – File pointer to an existing writeable, seekable file-like object encoding a model. Strings are interpreted as a file name.

• max_num_states – Maximum number of states to serialize along with the model. The number of states serialized is min(model.states.size(), max_num_states).

• only_decision – If True, only decision variables are serialized. If False, all symbols are serialized.

See also

from_file(), to_file()

TODO: describe the format

is_locked()

Lock status of the model.

No new symbols can be added to a locked model.

See also

lock(), unlock()

iter_constraints()

Iterate over all constraints in the model.

Examples

This example adds a single constraint to a model and iterates over it.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> i = model.integer()
>>> c = model.constant(5)
>>> model.add_constraint(i <= c) 
<dwave.optimization.symbols.LessEqual at ...>
>>> constraints = next(model.iter_constraints())

iter_decisions()

Iterate over all decision variables in the model.

Examples

This example adds a single decision symbol to a model and iterates over it.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> i = model.integer()
>>> c = model.constant(5)
>>> model.add_constraint(i <= c) 
<dwave.optimization.symbols.LessEqual at ...>
>>> decisions = next(model.iter_decisions())

iter_symbols()

Iterate over all symbols in the model.

Examples

This example iterates over a model’s symbols.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> i = model.integer(1, lower_bound=10)
>>> c = model.constant([[2, 3], [5, 6]])
>>> symbol_1, symbol_2 = model.iter_symbols()

num_constraints()

Number of constraints in the model.

Examples

This example checks the number of constraints in the model after adding a couple of constraints.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> i = model.integer()
>>> c = model.constant([5, -14])
>>> model.add_constraint(i <= c[0]) 
<dwave.optimization.symbols.LessEqual at ...>
>>> model.add_constraint(c[1] <= i) 
<dwave.optimization.symbols.LessEqual at ...>
>>> model.num_constraints()
2

num_decisions()

Number of independent decision nodes in the model.

An array-of-integers symbol, for example, counts as a single decision node.

Examples

This example checks the number of decisions in a model after adding a single (size 20) decision symbol.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> c = model.constant([1, 5, 8.4])
>>> i = model.integer(20, upper_bound=100)
>>> model.num_decisions()
1

num_edges()

Number of edges in the directed acyclic graph for the model.

Examples

This example minimizes the sum of a single constant symbol and a single decision symbol, then checks the number of edges in the model.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> c = model.constant(5)
>>> i = model.integer()
>>> model.minimize(c + i)
>>> model.num_edges()
2

num_nodes()

Number of nodes in the directed acyclic graph for the model.

See also

num_symbols()

Examples

This example add a single (size 20) decision symbol and a single (size 3) constant symbol checks the number of nodes in the model.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> c = model.constant([1, 5, 8.4])
>>> i = model.integer(20, upper_bound=100)
>>> model.num_nodes()
2

num_symbols()

Number of symbols tracked by the model.

Equivalent to the number of nodes in the directed acyclic graph for the model.

See also

num_nodes()

Examples

This example add a single (size 20) decision symbol and a single (size 3) constant symbol checks the number of symbols in the model.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> c = model.constant([1, 5, 8.4])
>>> i = model.integer(20, upper_bound=100)
>>> model.num_symbols()
2

remove_unused_symbols()

Remove unused symbols from the model.

A symbol is considered unused if all of the following are true :

• It is not a decision.

• It is not an ancestor of the objective.

• It is not an ancestor of a constraint.

• It has no ArraySymbol object(s) referring to it. See examples below.

Returns:

The number of symbols removed.

Examples

In this example we create a mix of unused and used symbols. Then the unused symbols are removed with remove_unused_symbols().

>>> from dwave.optimization import Model
>>> model = Model()
>>> x = model.binary(5)
>>> x.sum()  # create a symbol that will never be used 
<dwave.optimization.symbols.Sum at ...>
>>> model.minimize(x.prod())
>>> model.num_symbols()
3
>>> model.remove_unused_symbols()
1
>>> model.num_symbols()
2

In this example we create a mix of unused and used symbols. However, unlike the previous example, we assign the unused symbol to a name in the namespace. This prevents the symbol from being removed.

>>> from dwave.optimization import Model
>>> model = Model()
>>> x = model.binary(5)
>>> y = x.sum()  # create a symbol and assign it a name
>>> model.minimize(x.prod())
>>> model.num_symbols()
3
>>> model.remove_unused_symbols()
0
>>> model.num_symbols()
3

set(n: int, min_size: int = 0, max_size: Optional[int] = None) → SetVariable

Create a set symbol as a decision variable.

Parameters:

• n – Values in the set are subsets of range(n).

• min_size – Minimum set size. Defaults to 0.

• max_size – Maximum set size. Defaults to n.

Returns:

A set symbol.

Examples

This example creates a set symbol of up to 4 elements with values between 0 to 99.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> destinations = model.set(100, max_size=4)

state_size()

An estimate of the size, in bytes, of all states in the model.

Iterates over the model’s states and totals the sizes of all.

Examples

This example estimates the size of a model’s states.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> c = model.constant([1, 5, 8.4])
>>> i = model.integer(20, upper_bound=100)
>>> model.state_size()
184

to_file(**kwargs) → BinaryIO

Serialize the model to a new file-like object.

See also

into_file(), from_file()

to_networkx() → object

Convert the model to a NetworkX graph.

Returns:

A NetworkX graph.

Examples

This example converts a model to a graph.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> one = model.constant(1)
>>> two = model.constant(2)
>>> i = model.integer()
>>> model.minimize(two * i - one)
>>> G = model.to_networkx()  

One advantage of converting to NetworkX is the wide availability of drawing tools. See NetworkX’s drawing documentation.

This example uses DAGVIZ to draw the NetworkX graph created in the example above.

>>> import dagviz                      
>>> r = dagviz.render_svg(G)           
>>> with open("model.svg", "w") as f:  
...     f.write(r)

This creates the following image:

unlock()

Release a lock, decrementing the lock count.

Symbols can be added to unlocked models only.

See also

is_locked(), lock()

States Class

class States

States of a symbol in a model.

States represent assignments of values to a symbol’s elements. For example, an integer() symbol of size \(1 \times 5\) might have state [3, 8, 0, 12, 8], representing one assignment of values to the symbol.

Examples

This example creates a knapsack model and manipulates its states to test that it behaves as expected.

First, create a model.

>>> from dwave.optimization import Model
...
>>> model = Model()
>>> # Add constants
>>> weights = model.constant([10, 20, 5, 15])
>>> values = model.constant([-5, -7, -2, -9])
>>> capacity = model.constant(30)
>>> # Add the decision variable
>>> items = model.set(4)
>>> # add the capacity constraint
>>> model.add_constraint(weights[items].sum() <= capacity) 
<dwave.optimization.symbols.LessEqual at ...>
>>> # Set the objective
>>> model.minimize(values[items].sum())

Lock the model to prevent changes to directed acyclic graph. At any time, you can verify the locked state, which is demonstrated here.

>>> with model.lock():
...     model.is_locked()
True

Set a couple of states on the decision variable and verify that the model generates the expected values for the objective.

>>> model.states.resize(2)
>>> items.set_state(0, [0, 1])
>>> items.set_state(1, [0, 2, 3])
>>> with model.lock():
...     print(model.objective.state(0) > model.objective.state(1))
True

You can clear the states you set.

>>> model.states.clear()
>>> model.states.size()
0

clear()

Clear any saved states.

Clears any memory allocated to the states.

Examples

This example clears a state set on an integer decision symbol.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> i = model.integer(2)
>>> model.states.resize(3)
>>> i.set_state(0, [3, 5])
>>> print(i.state(0))
[3. 5.]
>>> model.states.clear()

from_file(file, *, replace=True, check_header=True)

Construct states from the given file.

Parameters:

• file – File pointer to a readable, seekable file-like object encoding the states. Strings are interpreted as a file name.

• replace – If True, any held states are replaced with those from the file. If False, the states are appended.

• check_header – Set to False to skip file-header check.

Returns:

A model.

from_future(future, result_hook)

Populate the states from the result of a future computation.

A Future object is returned by the solver to which your problem model is submitted. This enables asynchronous problem submission.

Parameters:

• future – Future object.

• result_hook – Method executed to retrieve the Future.

initialize()

Initialize any uninitialized states.

into_file(file)

Serialize the states into an existing file.

Parameters:

file – File pointer to an existing writeable, seekable file-like object encoding a model. Strings are interpreted as a file name.

TODO: describe the format

resize(n)

Resize the number of states.

If n is smaller than the current size(), states are reduced to the first n states by removing those beyond. If n is greater than the current size(), new uninitialized states are added as needed to reach a size of n.

Resizing to 0 is not guaranteed to clear the memory allocated to states.

Parameters:

n – Required number of states.

Examples

This example adds three uninitialized states to a model.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> i = model.integer(2)
>>> model.states.resize(3)

resolve()

Block until states are retrieved from any pending future computations.

A Future object is returned by the solver to which your problem model is submitted. This enables asynchronous problem submission.

size()

Number of model states.

Examples

This example adds three uninitialized states to a model and verifies the number of model states.

>>> from dwave.optimization.model import Model
>>> model = Model()
>>> model.states.resize(3)
>>> model.states.size()
3

to_file()

Serialize the states to a new file-like object.