Using the Stride Solver#

This section describes the Leap service’s quantum-classical hybrid nonlinear solver, also known as the Stride™ hybrid solver (e.g., hybrid_nonlinear_program_version1), and provides usage information.

Note

Not all accounts have access to this type of solver.

When to Use this Solver#

Nonlinear models typically represent general optimization problems with an objective function and/or one or more constraints over integer and/or binary variables; the model supports constraints natively.

This model is 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. The design principles and major features of this solver are described in the dwave-optimization philosophy page.

The Stride solver accepts arbitrarily structured problems formulated as nonlinear models, with any constraints represented natively.

Solver Design Philosophy#

The dwave-optimization package and the Stride solver incorporate features and design principles from each of the following areas:

For a detailed description, see the Philosophy section.

Modeling Problems#

The Developing Quantum Applications section describes the process used by D‑Wave and other companies to develop successful quantum applications, which includes such steps as identifying problems that can benefit from quantum technology, describing such problems in a way that enables developers to model them, developing mathematical models, and implementing code.

The Model Construction section explains the nonlinear model.

The dwave-optimization package provides a class for nonlinear models and model generators for common optimization problems. For example, 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. The model below 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])

For more details on this and other model generators, see the Model Generators section.

Submitting problems#

Ocean software’s dwave-system provides the LeapHybridNLSampler class for submitting nonlinear models to the Stride solver. Submit the CVRP model to the selected solver.

>>> from dwave.system import LeapHybridNLSampler
...
>>> with LeapHybridNLSampler() as sampler:
...     print(sampler.solver.name)
...     results = sampler.sample(
...         model,
...         label='SDK Examples - CVRP')
hybrid_nonlinear_program_version1

Timing & Charges#

The Solver Timing and Solver Usage Charges sections provide information on how solver usage is charged to your account.

>>> results.result().info["timing"]["run_time"]
5024685

Properties & Parameters#

Real-world problems can be complex and models representing such problems can quickly grow large. The Stride Solver Properties section provides limitations on your model. For example, the state size of the decision variables (decision_state_size()) must not exceed the maximum supported by the solver (maximum_decision_state_size):

>>> model.decision_state_size() < sampler.properties["maximum_decision_state_size"]
True

The Stride Solver Parameters section describes the parameters you can configure when submitting problems to the solver. For example, you might experiment with various processing times:

>>> with LeapHybridNLSampler() as sampler:
...     results = sampler.sample(
...         model,
...         time_limit=10,
...         label='SDK Examples - CVRP')

Getting Solutions#

The Stride solver returns a nondeterministic number of solutions. Any feasible states returned are ordered by objective (from low to high), and precede infeasible states. While the first sample is the best, other feasible solutions may be useful.

Solutions are the assignment of values to the model’s decision variables. You access these by iterating through the model’s decision variables for each state you are interested in, typically filtered by feasibility.

Use the model’s iter_decisions() and iter_constraints() methods to do so. For this example, there is a single decision variable (a DisjointLists).

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

The best state (state zero) might look like this:

>>> print(f"Feasibility is {all(sym.state(0) for sym in model.iter_constraints())}")
Feasibility is True
>>> print((f"Objective value #0 is {model.objective.state(0).round(2)} for routes\n"
...        f"    {[r.state(0).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]]

The Model Generators section explains the returned solutions and gives more details on accessing them.

You can iterate over all the states returned by the solver (the size() method gives the number of returned states). For some models it can be helpful to retrieve non-decision variables that calculate useful information: use the iter_symbols() method to retrieve such additional symbols.

Converting from MILP#

Mixed integer linear programs (MILP) may represent problems that are, in fact, good candidates for solution by the nonlinear solver because often highly nonlinear problems are reformulated as linear programs for solvers that do not have more extensive modeling capabilities. The advanced modeling capability provided by dwave-optimization package, together with the Strides solver’s ability to handle the nonlinear formulations natively, enable more efficient formulation and solution.

However, naive conversion from linear program (LP) format to Ocean software’s nonlinear-model format is unlikely to provide the best performance. Good performance requires the formulation of good models. Consider the following points to get started:

  • Choose powerful decision variables

    Your choice of decision variables significantly affects the model’s clarity, size of the solution space, and, ultimately, the solver’s performance. The Implicitly Constrained Decision Variables section can help you make a good choice.

  • Use compact matrix formulation

    Compact matrix formulation is usually more efficient and should be preferred. The Compact Matrix Formulation section explains and demonstrates this.

The MIPLIB Benchmarks section provides examples of converting problems from the Mixed-Integer Programming Library (MIPLIB) to nonlinear models and demonstrates how the Stride solver can outperform on such problems. You may also find formulation templates for several standard optimization problems in the model generators section of the dwave-optimization package, which you may be able to adapt to your problem.

Improving Solutions and Productizing#

There can be a significant gap between solving an initial model for your problem, perhaps simplified and reduced in scale, and an application in production. The following resources can be useful: