Model Generators

Model generators for optimization problems.

See examples such as Traveling Salesperson: Simple Nonlinear Model and Vehicle Routing: Using a Nonlinear Model, as well as application examples in the D-Wave Examples GitHub repository, for more detailed usage.

bin_packing(weights: numpy.typing.ArrayLike, capacity: float) → Model

Generate a model encoding a bin packing problem.

The bin packing problem, BPP, seeks to find the smallest number of bins that will fit a set of weighted items given that each bin has a weight capacity.

Parameters:

• weights – Weight per item as a 1D array-like (row vector or Python list). Weights can be any non-negative number.

• capacity – Maximum capacity of each bin. Must be a positive number.

Returns:

A model encoding the BPP problem.

Notes

The model uses a DisjointBitSets class as the decision variable being optimized, with permutations of its bit sets representing various packings for each bin.

Examples

This example finds how many bins are needed to pack four items with various weights into bins with maximum capacity 7.

>>> from dwave.optimization.generators import bin_packing
>>> model = bin_packing([3, 5, 1, 3], 7)

An example feasible solution might be four bit sets (for four items the maximum possible number of bins is four) of four bits each (a bit per item), with \(1.0\) signifying placement of the corresponding item in the corresponding bin,

\[\begin{split}[0. \quad 1. \quad 0. \quad 0.], \\ [1. \quad 0. \quad 1. \quad 1.], \\ [0. \quad 0. \quad 0. \quad 0.], \\ [0. \quad 0. \quad 0. \quad 0.],\end{split}\]

where here the second item with weight 5 is in one bin and the remaining items are in a second bin. The objective value for this solution is 2, as shown in the following code.

The iter_decisions() method obtains the decision variables of the generated model.

>>> items = next(model.iter_decisions())

To test the solution above, set it in the model as the state of the decision variable. Skip these next lines if you have submitted your model to the Leap hybrid nonlinear solver.

>>> model.states.resize(1)
>>> items.set_state(0, [[0, 1, 0, 0], [1, 0, 1, 1], 4*[0], 4*[0]])

You can use the iter_constraints() method to check feasibility of constructed or returned solutions. Here, the number of states (size()) is set to 1 for the constructed solution so a single value of the objective property is printed.

>>> with model.lock():
...     capacity_constraint = next(model.iter_constraints())
...     for i in range(model.states.size()):
...         if capacity_constraint.state(i):    # Filter on feasibility
...             print((f"Objective value #{i} is {model.objective.state(i)} for packing\n"
...                    f"    {[b.state(i).tolist() for b in items.iter_successors()]}"))
Objective value #0 is 2.0 for packing
    [[0.0, 1.0, 0.0, 0.0], [1.0, 0.0, 1.0, 1.0], [0.0, 0.0, 0.0, 0.0], [0.0, 0.0, 0.0, 0.0]]

capacitated_vehicle_routing(demand: numpy.typing.ArrayLike, number_of_vehicles: int, vehicle_capacity: float, distances: None | numpy.typing.ArrayLike = None, locations_x: None | numpy.typing.ArrayLike = None, locations_y: None | numpy.typing.ArrayLike = None, depot_x_y: None | numpy.typing.ArrayLike = None) → Model

Generate a model encoding a capacitated vehicle routing problem.

The capacitated vehicle routing problem, CVRP, is to find the shortest possible routes for a fleet of vehicles delivering to multiple customer locations from a central depot. Vehicles have a specified delivery capacity, and on the routes to locations and then back to the depot, no vehicle is allowed to exceed its carrying capacity.

Parameters:

• demand – Customer demand, as an array-like. If distances is specified, the first element must be zero. If distances is not specified and the first element is zero, [locations_x[0], locations_y[0]] must be the location of the depot. Elements other than the first must be positive numbers.

• number_of_vehicles – Number of available vehicles, as a positive integer.

• vehicle_capacity – Maximum capacity for any vehicle. The total delivered demand by any vehicle on any route must not exceed this value.

• distances – Distances between all the problem’s locations, as an array-like of positive numbers, including both customer sites and the depot. When specified, the first element of demand must be zero and specifying X coordinates or X coordinates is not supported

• locations_x – X coordinates, as an array-like, of locations for customers, and optionally the depot. When specified, 2D Euclidean distances are calculated and specifying distances is not supported. If the first element represents the X coordinate of the depot, the first element of demand must be zero.

• locations_y – Y coordinates, as an array-like, of locations for customers, and optionally the depot. When specified, 2D Euclidean distances are calculated and specifying distances is not supported. If the first element represents the Y coordinate of the depot, the first element of demand must be zero.

• depot_x_y – Location of the depot, as an array-like of exactly two elements, [X, Y]. Required if the first element of demand is nonzero and distances is not specified; not allowed otherwise.

Returns:

A model encoding the CVRP problem.

Notes

The model uses a DisjointLists class as the decision variable being optimized, with permutations of its sublists representing various itineraries for each vehicle.

Examples

This example finds delivery routes for two vehicles delivering from a depot to nine sites with maximum vehicle capacity 200.

>>> from dwave.optimization.generators import capacitated_vehicle_routing
...
>>> demand = [0, 34, 12, 65, 10, 43, 27, 55, 61, 22]
>>> sites = [(15, 38), (23, -19), (44, 62), (3, 12), (-56, -21), (-53, 2),
...          (33, 63), (14, -33), (42, 41), (13, -62)]
>>> model = capacitated_vehicle_routing(
...     demand=demand,
...     number_of_vehicles=2,
...     vehicle_capacity=200,
...     locations_x=[x for x,y in sites],
...     locations_y=[y for x,y in sites])

The Vehicle Routing: Using a Nonlinear Model example demonstrates the use of the Leap hybrid nonlinear solver and handles the returned solutions.

An example feasible solution might be,

\[[2., 7., 1., 5], [4., 3., 8., 6., 0.],\]

meaning one vehicle visits customer sites \(2, 7, 1, 5\) and the other vehicle visits the remaining sites. The objective value for this solution is \(\approx 424\), as shown in the following code.

The iter_decisions() method obtains the decision variables of the generated model.

>>> routes = next(model.iter_decisions())

To test the solution above, set it in the model as the state of the decision variable. Skip these next lines if you have submitted your model to the Leap hybrid nonlinear solver.

>>> model.states.resize(1)
>>> routes.set_state(0, [[2., 7., 1., 5.], [4., 3., 8., 6., 0.]])

You can use the iter_constraints() method to check feasibility of constructed or returned solutions. Here, the number of states (size()) is set to 1 for the constructed solution so a single value of the objective property is printed.

>>> with model.lock():
...     capacity_constraint = next(model.iter_constraints())
...     for i in range(model.states.size()):
...         if capacity_constraint.state(i):    # Filter on feasibility
...             print((f"Objective value #{i} is {model.objective.state(i).round(2)} for routes\n"
...                    f"    {[r.state(i).tolist() for r in routes.iter_successors()]}"))
Objective value #0 is 423.8 for routes
    [[2.0, 7.0, 1.0, 5.0], [4.0, 3.0, 8.0, 6.0, 0.0]]

capacitated_vehicle_routing_with_time_windows(demand: numpy.typing.ArrayLike, number_of_vehicles: int, vehicle_capacity: float, time_distances: numpy.typing.ArrayLike, time_window_open: numpy.typing.ArrayLike, time_window_close: numpy.typing.ArrayLike, service_time: numpy.typing.ArrayLike) → Model

Generate a model encoding a capacitated vehicle routing problem with time windows.

The capacitated vehicle routing problem with time windows, CVRPTW, is to find the shortest possible routes for a fleet of vehicles delivering to multiple customer locations from a central depot. Each customer should be served after their time window opens and before it closes. Vehicles have a specified delivery capacity, and on the routes to locations and then back to the depot, no vehicle is allowed to exceed its carrying capacity.

Parameters:

• demand – Customer demand, as an array-like. The first element is the depot and must be zero.

• number_of_vehicles – Number of available vehicles, as a positive integer.

• vehicle_capacity – Maximum capacity for any vehicle. The total delivered demand by any vehicle on any route must not exceed this value.

• time_distances – Time distances between all the problem’s locations, as an array-like of positive numbers, including both customer sites and the depot. The first row and column of the distance matrix are customer distances from the depot.

• time_window_open – Opening time for each customer, as an array-like. The first element is the depot.

• time_window_close – Closing time for each customer, as an array-like. The first element is the depot. Arrival at each customer \(i\) must occur earlier than time_window_close[i] - service_time[i] to enable the delivery to be serviced before the window closes.

• service_time – Time it takes to serve each customer, as an array-like. The first element is the depot and must be zero. For feasible solutions, service_time[i] <= time_window_close[i] - time_window_open[i] for each customer \(i\).

Returns:

A model encoding the CVRPTW problem.

Notes

The model uses a DisjointLists class as the decision variable being optimized, with permutations of its sublists representing various itineraries for each vehicle.

Examples

This example finds delivery routes for two vehicles delivering from a depot to three sites with maximum vehicle capacity 40 and varying opening,closing, and service times.

>>> from dwave.optimization.generators import capacitated_vehicle_routing_with_time_windows
...
>>> time_distances=[[0, 14, 19, 32],
...                 [14, 0, 15, 19],
...                 [19, 15, 0, 21],
...                 [32, 19, 21, 0]]
>>> model = capacitated_vehicle_routing_with_time_windows(
...     demand=[0, 19, 30, 16],
...     number_of_vehicles=2,
...     vehicle_capacity=40,
...     time_distances=time_distances,
...     time_window_open=[0, 0, 10, 5],
...     time_window_close=[100, 90, 50, 90],
...     service_time=[0, 10, 5, 5])

The Vehicle Routing: Using a Nonlinear Model example demonstrates the use of the Leap hybrid nonlinear solver and handles the returned solutions for a similar problem.

An example feasible solution might be,

\[[0, 2], [1],\]

meaning one vehicle visits customer sites \(0, 2\) and the other vehicle visits site \(1\). The objective value for this solution is \(\approx 103\), as shown in the following code.

The iter_decisions() method obtains the decision variables of the generated model.

>>> routes = next(model.iter_decisions())

To test the solution above, set it in the model as the state of the decision variable. Skip these next lines if you have submitted your model to the Leap hybrid nonlinear solver.

>>> model.states.resize(1)
>>> routes.set_state(0, [[0, 2], [1]])

You can use the iter_constraints() method to check feasibility of constructed or returned solutions. Here, the number of states (size()) is set to 1 for the constructed solution so a single value of the objective property is printed.

>>> with model.lock():
...     for i in range(model.states.size()):
...         if all(sym.state(i) for sym in model.iter_constraints()): # Filter feasibility
...             print((f"Objective value #{i} is {model.objective.state(i).round(2)} for routes\n"
...                    f"    {[r.state(i).tolist() for r in routes]}"))
Objective value #0 is 103.0 for routes
    [[0.0, 2.0], [1.0]]

flow_shop_scheduling(processing_times: numpy.typing.ArrayLike) → Model

Generate a model encoding a flow-shop scheduling problem.

Flow-shop scheduling is a variant of the renowned job_shop_scheduling() optimization problem. Given \(n\) jobs to schedule on \(m\) machines, with specified processing times for each job per machine, minimize the makespan (the total length of the schedule for processing all the jobs). For every job, the \(i\)-th operation is executed on the \(i\)-th machine. No machine can perform more than one operation simultaneously.

E. Taillard provides benchmark instances compatible with this generator.

Note

There are many ways to model flow-shop scheduling. The model returned by this function may or may not give the best performance for your problem.

Parameters:

processing_times – Processing times, as an \(m \times n\) array-like of integers, where processing_times[m, n] is the time job \(n\) is on machine \(m\).

Returns:

A model encoding the flow-shop scheduling problem.

Notes

The model uses a ListVariable class as the decision variable being optimized, with permutations of its integer values representing various job orderings.

Examples

This example creates a model for a flow-shop-scheduling problem with three jobs on two machines. For example, the first job requires processing for 20 time units on the second machine in the flow of operations.

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

An example feasible solution might be \([1, 0, 2]\), meaning the order of jobs is job 1 first, job 0 second, and job 2 last. The objective value (makespan) for this solution is \(50\), as shown in the following code.

The iter_decisions() method obtains the decision variables of the generated model.

>>> order = next(model.iter_decisions())

To test the solution above, set it in the model as the state of the decision variable. Skip these next lines if you have submitted your model to the Leap hybrid nonlinear solver.

>>> model.states.resize(1)
>>> order.set_state(0, [1, 0, 2])

Here, the number of states (size()) is set to 1 for the constructed solution so a single value of the objective property is printed.

>>> with model.lock():
...     for i in range(model.states.size()):
...         print((f"Order #{i} is {order.state(i).tolist()} with makespan "
...                f"{model.objective.state(i).round(2)}"))
Order #0 is [1.0, 0.0, 2.0] with makespan 50.0

This solution is shown in the figure below.

Fig. 254 Visualization of the solution.

job_shop_scheduling(times: numpy.typing.ArrayLike, machines: numpy.typing.ArrayLike, *, upper_bound: None | int = None) → Model

Generate a model encoding a job-shop scheduling problem.

There are many variants of job-shop scheduling, a problem where given \(n\) jobs to schedule on \(m\) machines, with specified processing times for each job per machine, the aim is to minimize the makespan (the total length of the schedule for processing all the jobs). This generator implements a variant of job-shop scheduling with the additional assumption that every job makes use of every machine.

E. Taillard provides benchmark instances compatible with this generator.

Changed in version 0.6.13: From version 0.4.1 to 0.6.12, the model generated used integer variables for the start times and included explicit non-overlap constraints between each pair of jobs on the machines.

Now the model uses a list variable for the global ordering of all tasks and greedily constructs a feasible ordering from which the start times are determined.

Changed in version 0.4.1: Prior to version 0.4.1, the model generated was based on one proposed by

L. Blaise, “Modélisation et résolution de problèmes d’ordonnancement au sein du solveur d’optimisation mathématique LocalSolver”, Université de Toulouse, https://hal-lirmm.ccsd.cnrs.fr/LAAS-ROC/tel-03923149v2.

Now the model uses the more natural formulation where the only decision variables are the task start times, but with disjunctive non-overlapping constraints between each pair of jobs on the machines.

Note

There are many ways to model job-shop scheduling. The model returned by this function may or may not give the best performance for your problem.

Parameters:

• times – Processing times as an \(n\) jobs by \(m\) machines array-like where times[n, m] is the processing time of job \(n\) on machine \(m\).

• machines – Machine order as an \(n\) jobs by \(m\) machines array-like where machines[n, :] is the order of machines that job \(n\) is processed on.

• upper_bound – Upper bound on the makespan. If not given, defaults to times.sum(). Note that if upper_bound is too small the model may be infeasible.

Returns:

A model encoding the job-shop scheduling problem. The model includes three additional methods added to it:

• model.get_global_task_ordering(state_index: int): Given an index of a state on the model, returns an array corresponding to the global ordering of all tasks where the global task index for the \(j\) th task of the \(i\) th job is given by \(n * i + j\).

• model.get_start_times(state_index: int): Given an index of a state on the model, returns an \(n\) by \(m\) array of start times of each task of each job.

• model.get_end_times(state_index: int): Given an index of a state on the model, returns an \(n\) by \(m\) array of end times of each task of each job.

Notes

The model formulation has a single ListVariable decision variable of size \(n \times m\) (total number of tasks), and consists of two main parts: One to derive a global task ordering that respects the task-ordering requirement of each job, and another to build a feasible schedule based on that global ordering.

The first part is achieved by taking the list decision variable output, and using \(m\) AccumulateZip nodes nodes to select and then reorder the tasks of each job.

The second part is achieved by iterating through the tasks in the global ordering and placing each task at the earliest possible time it can run. Finish times for each task, as well as the finish time for the last task on each machine, are maintained in lists and updated with Put nodes at each iteration.

Finally, the makespan is equal to the maximum value of the finish-times array.

Examples

This example creates a model for a job-shop-scheduling problem with three jobs on three machines. For example, the first job requires processing for 2 time units on the first machine, then 1 time unit on the second machine, then 3 time units on the third machine.

>>> from dwave.optimization.generators import job_shop_scheduling
...
>>> times = [[2, 1, 3],
...          [4, 1, 2],
...          [1, 1, 2]]
>>> machines = [[0, 1, 2],
...             [2, 0, 1],
...             [2, 1, 0]]
>>> model = job_shop_scheduling(times, machines)

In the global task ordering, the index for the \(j\) th task for the \(i\) th job is equal to \(n*i + j\). An example solution for the final global task ordering might be:

\[[0, 3, 4, 6, 1, 2, 7, 5, 8],\]

meaning that the first task is the first job on the first machine, the next task is the second job on the third machine, the next task is the second job on the first machine, etc. The model constructs a schedule based on when the next task is available to run. The goal of the solver is to determine a global ordering of tasks whose corresponding schedule minimizes the makespan. The makespan (objective value) is 7, as shown in the following code.

The iter_decisions() method obtains the decision variables of the generated model.

>>> task_ordering = next(model.iter_decisions())

This gives the initial global task ordering from which the feasible final global task ordering is constructed.

To test the solution above, set the corresponding initial global task ordering in the model as the state of the decision variable. Skip these next lines if you have submitted your model to the Leap hybrid nonlinear solver.

>>> model.states.resize(1)
>>> task_ordering.set_state(0, [0, 5, 4, 7, 1, 2, 6, 3, 8])

To check that this task ordering corresponds to the global feasible task ordering [0,3,4,6,1,2,7,5,8] , use the method get_global_task_ordering().

>>> final_ordering = model.get_global_task_ordering(0)

You can use the methods get_start_times() and get_end_times() to obtain the corresponding start and end times of all tasks.

>>> start_times = model.get_start_times(0)
>>> end_times = model.get_end_times(0)

Finally, you can check the objective value of this state.

>>> makespan = model.objective.state(0)

The makespan is 7.0 for the schedule with start times [[0. 2. 4.] [0. 2. 6.] [2. 4. 6.]]

This solution is shown in the figure below.

Fig. 255 Visualization of the solution.

knapsack(values: numpy.typing.ArrayLike, weights: numpy.typing.ArrayLike, capacity: float) → Model

Generate a model encoding a knapsack problem.

The knapsack problem is, for a given set of items, each with a weight and a value, to determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Parameters:

• values – Value per item as a 1D array-like (row vector or Python list). Length of values must be equal to the length of weights. Values can be any non-negative number.

• weights – Weight per item as a 1D array-like (row vector or Python list). Weights can be any non-negative number.

• capacity – Maximum capacity of the knapsack. Must be a positive number.

Returns:

A model encoding the knapsack problem.

Notes

The model generated uses a SetVariable class as the decision variable being optimized, with permutations of the subsets of this set representing possible items included in the knapsack.

Examples

This example creates a model for a knapsack problem with four items.

>>> from dwave.optimization.generators import knapsack
...
>>> weights = [30, 10, 40, 20]
>>> values = [10, 20, 30, 40]
>>> model = knapsack(values=values, weights=weights, capacity=30)

An example feasible solution might be \([1, 2]\), meaning the knapsack should include the second and fourth items. The objective value for this solution is \(-1(20 + 40) = -60\), as shown in the following code.

The iter_decisions() method obtains the decision variables of the generated model.

>>> items = next(model.iter_decisions())

To test the solution above, set it in the model as the state of the decision variable. Skip these next lines if you have submitted your model to the Leap hybrid nonlinear solver.

>>> model.states.resize(1)
>>> items.set_state(0, [1, 3])

Here, the number of states (size()) is set to 1 for the constructed solution so a single value of the objective property is printed.

>>> with model.lock():
...     for i in range(model.states.size()):
...         print((f"Items in solution #{i} are {items.state(i)} with value "
...                f"{-model.objective.state(i)}"))
Items in solution #0 are [1. 3.] with value 60.0

predict(estimator, X: ArraySymbol) → ArraySymbol

Predict y from X using a fitted estimator.

Parameters:

• estimator –

  A fitted estimator, either a MLPClassifier or a MLPRegressor.

  Note that only binary MLPClassifier is supported.

• X – Input data as an array symbol.

Returns:

Predicted values, y.

Raises:

NotImplementedError – There are many ways to train estimators, some cases may not be supported. Feel free to open a feature request at dwavesystems/dwave-optimization for any missing cases.

Examples

This example solves a knapsack problem (see also the knapsack() function) where weights are known but values (prices) for these items are noisy observations.

import itertools

import numpy as np

from dwave.optimization import Model
from dwave.optimization.generators import predict
from sklearn.neural_network import MLPRegressor

# The weights are known exactly
weights = np.asarray([12, 1, 1, 2, 4])

# But the values, rather than being known directly, are given only
# through noisy observations
def observations():
    secret_values = np.asarray([4, 2, 1, 2, 10])

    rng = np.random.default_rng(42)
    X = rng.integers(low=0, high=2, size=(20, 5))

    y = X @ secret_values + rng.normal(scale=.5, size=20)

    return X, y

X, y = observations()

# You can now fit a multi-layer perceptron estimator to these observations. The
# estimator, given a collection of purchases, estimates the values of the items
regr = MLPRegressor(max_iter=2000).fit(X, y)

# Now you can use that estimator to construct a knapsack problem
model = Model()

items = model.binary(shape=(1, 5))

model.minimize(-predict(regr, items))
model.add_constraint(items @ weights <= 15)

# Finally, you can solve exactly by trying all possible solutions, and check
# that the solution is the correct one
model.lock()
model.states.resize(1)

best_value = float("inf")
best_state = None
for state in itertools.product((0, 1), repeat=5):
    items.set_state(0, state)

    if model.feasible() and model.objective.state() < best_value:
        best_value = model.objective.state()
        best_state = items.state()

assert np.array_equal(best_state, [[0, 1, 1, 1, 1]])

See also

sklearn.neural_network.MLPClassifier sklearn.neural_network.MLPRegressor

Added in version 0.6.11.

quadratic_assignment(distance_matrix: numpy.typing.ArrayLike, flow_matrix: numpy.typing.ArrayLike) → Model

Generate a model encoding a quadratic assignment problem.

The quadratic assignment is, for a given list of facilities, the distances between them, and the flow between each pair of facilities, to minimize the sum of the products of distances and flows.

Parameters:

• distance_matrix – Distances as an array-like, where distance_matrix[n, m] is the distance between location \(n\) and \(m\). Represents the (known and constant) distances between every possible pair of facility locations: in real-world problems, such a matrix can be generated from an application with access to an online map.

• flow_matrix – Flows as an array-like, where flow_matrix[n, m] is the flow between facilities \(n\) and \(m\). Represents the (known and constant) flow between every possible pair of facilities.

Returns:

A model encoding the quadratic-assignment problem.

Notes

The model generated uses a ListVariable class as the decision variable being optimized, with permutations of the values of this list representing assignments of facilities to locations.

Examples

This example creates a model for a quadratic-assignment problem that has three facilites to place in three locations.

>>> from dwave.optimization.generators import quadratic_assignment
...
>>> distance_matrix = [[0, 5, 3],
...                    [5, 0, 2],
...                    [3, 2, 0]]
>>> flow_matrix = [[0, 1, 3],
...                [4, 0, 2],
...                [1, 1, 0]]
>>> model = quadratic_assignment(distance_matrix=distance_matrix, flow_matrix=flow_matrix)

An example feasible solution might be \([2, 1, 0]\), meaning that facility two should be on site zero, facility one should be on site one, and facility zero should be on site two.[1] The objective value for this solution is \(37\), as shown in the following code.

The iter_decisions() method obtains the decision variables of the generated model.

>>> locations = next(model.iter_decisions())

To test the solution above, set it in the model as the state of the decision variable. Skip these next lines if you have submitted your model to the Leap hybrid nonlinear solver.

>>> model.states.resize(1)
>>> locations.set_state(0, [2, 1, 0])

Here, the number of states (size()) is set to 1 for the constructed solution so a single value of the objective property is printed.

>>> with model.lock():
...     for i in range(model.states.size()):
...         print((f"Locations for solution #{i} are {locations.state(i)} with objective "
...                f"value of {model.objective.state(i)}"))
Locations for solution #0 are [2. 1. 0.] with objective value of 37.0

This solution is shown in the figure below.

Fig. 256 Visualization of the solution. The shortest distance between pairs, of 2 between facilities 1 and 2, has the greatest total flow of \(1+4=5\), the longest distance between pairs, of 5 between facilities 0 and 1, has the least total flow of \(1+2=3\), while the intermediate distance of 3 has an intermediate total flow of \(1+3=4\).

[1]

To understand how the ListVariable decision variable orders facilities to locations, consider a simple example of two facilities and two locations, where the flow is asymmetric and the distance depends on direction. The cost given by the multiplication of flow matrix by distance matrix, for example,

\[\begin{split}\overbrace{ \begin{bmatrix} 0 & 2 \\ 1 & 0 \end{bmatrix}}^{\text{Flow}} * \overbrace{ \begin{bmatrix} 0 & 2 \\ 3 & 0 \end{bmatrix}}^{\text{Distance}} = \overbrace{ \begin{bmatrix} 0 & 4 \\ 3 & 0 \end{bmatrix}}^{\text{Cost}},\end{split}\]

gives 3 in element \((0, 1)\), meaning the cost of transfers between facility 0 to facility 1 (element \((0, 1)\) in the flow matrix) in location 0 and 1 (element \((0, 1)\) in the distance matrix) is 3.

This remains the product when the distance matrix is indexed as

\[\text{distance_matrix}[\text{index}, :][:, \text{index}],\]

where the index, a ListVariable decision variable, is the natural order, here \([0, 1]\).

\[\begin{split}\begin{bmatrix} 0 & 2 \\ 1 & 0 \end{bmatrix} * \begin{bmatrix} 0 & 2 \\ 3 & 0 \end{bmatrix}[[0, 1], :][:, [0, 1]] = \begin{bmatrix} 0 & 4 \\ 3 & 0 \end{bmatrix}\end{split}\]

Permutations of the index switch the resulting product around; here \([1, 0]\) gives the cost for facilty 0 at location 1 and facility 1 at location 0:

\[\begin{split}\begin{bmatrix} 0 & 2 \\ 1 & 0 \end{bmatrix} * \begin{bmatrix} 0 & 2 \\ 3 & 0 \end{bmatrix}[[1, 0], :][:, [1, 0]] = \begin{bmatrix} 0 & 6 \\ 2 & 0 \end{bmatrix}\end{split}\]

In this way, permutations of the ListVariable decision variable allow the model to represent all possible pairings of facilities and locations and the cost for each.

traveling_salesperson(distance_matrix: numpy.typing.ArrayLike) → Model

Generate a model encoding a traveling-salesperson problem.

The traveling salesperson is, for a given list of cities and distances between each pair of cities, to find the shortest possible route that visits each city exactly once and returns to the city of origin.

Parameters:

distance_matrix – Distances as an array-like, where distance_matrix[n, m] is the distance between city \(n\) and \(m\). Represents the (known and constant) distances between every possible pair of cities: In real-world problems, such a matrix can be generated from an application with access to an online map. Such matrices may be asymmetric if the direction of travel matters, such as when different routes are used depending on direction.

Returns:

A model encoding the traveling-salesperson problem.

Notes

The model generated uses a ListVariable class as the decision variable being optimized, with permutations of this ordered list representing possible itineraries through the required cities.[2]

Examples

This example creates a model for a traveling-salesperson problem that visits three cities, where the distance depends on the direction of travel.

>>> from dwave.optimization.generators import traveling_salesperson
...
>>> distance_matrix = [
...     [0, 3, 1],
...     [1, 0, 3],
...     [3, 1, 0]]
>>> model = traveling_salesperson(distance_matrix=distance_matrix)

Example solutions might be \([0, 1, 2]\) and \([2, 1, 0]\), the first solution meaning that the salesperson visits city 0 then city 1 then city 2 while the second solution reverses that order. The objective value for the first solution is \(9\) and for the second \(3\), as shown in the following code.[3]

The iter_decisions() method obtains the decision variables of the generated model.

>>> itinerary = next(model.iter_decisions())

To test the solution above, set it in the model as the state of the decision variable. Skip these next lines if you have submitted your model to the Leap hybrid nonlinear solver.

>>> model.states.resize(2)
>>> itinerary.set_state(0, [2, 1, 0])
>>> itinerary.set_state(1, [0, 1, 2])

Here, the number of states (size()) is set to 2 for the constructed solutions so two values of the objective property are printed.

>>> with model.lock():
...     for i in range(model.states.size()):
...         print((f"Itinerary #{i} is {itinerary.state(i)} with objective "
...                f"value of {model.objective.state(i)}"))
Itinerary #0 is [2. 1. 0.] with objective value of 3.0
Itinerary #1 is [0. 1. 2.] with objective value of 9.0

[2]

The ListVariable class used to represent the decision variable as an ordered list is implicitly constrained in the possible values that can be assigned to it; for example, compare a model representing five cities as five variables of type int, \(i_{Rome}, i_{Turin}, i_{Naples}, i_{Milan}, i_{Genoa}\), where \(i_{Rome} = 2\) means Rome is the third city visited, versus a model using an ordered list, \((city_0, city_1, city_2, city_3, city_4)\). The first model must explicitly constrain solutions to those that select a value between 0 and 4 for each decision variable with no repetitions; such constraints are implicit to the ordered-list variable.

[3]

Permutations of indices \((0, 1, 2, ...)\) that order distance_matrix represent itineraries that travel from list-element \(i\) to list-element \(i+1\) for \(i \in [0, N-1]\), where \(N\) is the length of the list (and the number of cities). Additionally, the problem requires a return to the city of origin (first element of the list) from the last city visited (the last element of the list).