Model Generators#

Model generators for optimization problems.

bin_packing(weights: numpy.typing.ArrayLike, capacity: float) → Model[source]#

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 – A 1D array-like (row vector or Python list) of weights per item. 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.

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

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 disjoint_lists class as the decision variable being optimized, with permutations of its sublist representing various itineraries for each vehicle.

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

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 time_window_open and before time_window_close. 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 colum of the distance matrix are customer distances form the depot.

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

  • time_window_close – The closing time of each customer, as an array-like. The first element is the depot.

  • service_time – The time it takes to serve each customer, as an array-like. The first element is the depot and must be zero.

Returns:

A model encoding the CVRPTW problem.

Notes

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

flow_shop_scheduling(processing_times: numpy.typing.ArrayLike) → Model[source]#

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.

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)
job_shop_scheduling(times: numpy.typing.ArrayLike, machines: numpy.typing.ArrayLike, *, upper_bound: int | None = None) → Model[source]#

Generate a model encoding a job-shop scheduling problem.

Job-shop scheduling has many variant. Here, what we have implemented is 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.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 job 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 – An n jobs by m machines array-like where times[n, m] is the processing time of job n on machine m.

  • machines – An n jobs by m machines array-like where machines[n, :] is the order of machines that job n will be processed on.

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

Returns:

A model encoding the job-shop scheduling problem.

knapsack(values: numpy.typing.ArrayLike, weights: numpy.typing.ArrayLike, capacity: float) → Model[source]#

Generate a model encoding a knapsack problem.

The knapsack problem is, for a given set of items, each with a weight and a value, 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 – A 1D array-like (row vector or Python list) of values per item. The length of values must be equal to the length of weights. Values can be any non-negative number.

  • weights – A 1D array-like (row vector or Python list) of weights per item. 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.

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

quadratic_assignment(distance_matrix: numpy.typing.ArrayLike, flow_matrix: numpy.typing.ArrayLike) → Model[source]#

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, minimize the sum of the products of distances and flows.

Parameters:

  • distance_matrix – 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 – A array-like where flow_matrix[n, m] is the flow between location n and m. Represents the (known and constant) flow between every possible pair of facility location

Returns:

A model encoding the quadratic_assignment problem.

traveling_salesperson(distance_matrix: numpy.typing.ArrayLike) → Model[source]#

Generate a model encoding a traveling-salesperson problem.

The traveling salesperson is, for a given a 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 – 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.

Returns:

A model encoding the traveling-salesperson problem.

Typically, solver performance strongly depends on the size of the solution space for your modelled problem: models with smaller spaces of feasible solutions tend to perform better than ones with larger spaces. A powerful way to reduce the feasible-solutions space is by using variables that act as implicit constraints. This is analogous to judicious typing of a variable to meet but not exceed its required assignments: a Boolean variable, x, has a solution space of size 2 (\(\{True, False\}\)) while an integer variable, i, might have a solution space of over 4 billion values.

The model generated uses a dwave.optimization.Model.list class as the decision variable being optimized, with permutations of this ordered list representing possible itineraries through the required cities.

The dwave.optimization.Model.list 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 to 4 for each decision variable with no repetitions; such constraints are implicit to the ordered-list variable.

The objective is to minimize the distance traveled. 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).