We've released Hop v0.7.0! This release introduces a cool new feature we call expanders into Hop to help customers manage time to first feasible solution and memory use as they scale their models. Customers can upgrade today. New users can explore it working behind the scenes with a free trial on Nextmv Cloud.
Hop is a decision modeling and optimization tool that uses decision diagrams to find solutions to business problems. A problem might be how to optimally pack a pallet in a warehouse (a packing problem) or how to route drivers for a food delivery service (also known as a vehicle routing problem or VRP).
When a Hop model runs, it first reads JSON input that describes the state of a system. In the case of a food delivery service, for example, the initial (or root) state of a system might describe a single driver who needs to visit four locations. Hop reads this input and generates a decision diagram expressing all the possible resulting (or child) states. This is called an “exact diagram” because it exactly represents a problem’s search space. As part of this expression, the Hop model generates various attributes for each possible state: locations left to visit, the route, the value of the state, and whether or not it is feasible.
The first few states and their attributes generated for a routing problem with one vehicle and four locations. The child states of S1 both add a second location to their routes but in different positions in the route. This ordering results in a different overall value.
While being thorough has its advantages, generating an exact diagram for every possible decision can get very unwieldy very quickly. The resulting state explosion impacts Hop’s overall performance by lengthening the time to first feasible solution and increasing memory use. In practice, this means certain poorly performing models can take minutes to return a good delivery route instead of seconds. And with real-time operations, that matters.
The good news is that there are techniques to manage this such as restrictors, reducers, and bounds. In Hop v0.7.0, we've introduced another: expanders.
Expanders are a technique for limiting how many child states a parent state can create at a time. Essentially, they cap the number of child states immediately generated by each node in a decision diagram, mitigating state explosion and managing performance impact.
To understand this a bit better, let’s have a closer look at the vehicle routing problem from earlier in this post: one vehicle, four locations. Without any limits imposed on it, Hop creates an exact diagram. It begins with the root state (S0) and goes to work generating child states. At each layer in the diagram, Hop adds a location to the route and experiments with the position of that location within the route. Some of the child states will be feasible (the resulting route visits all four locations) and some will not (the resulting route does not visit all four locations). In this example, you can see that we don’t reach feasible states until the fourth layer.
Exact diagram for our vehicle routing problem with a single driver that needs to visit four locations. There are 34 states total (S0 through S33). S = state, L = locations left to visit, V = value, R = route. L, V, and R are excluded from Layer 4 for simplicity.
Another consideration in this process is the value calculated for each state. In this example, lower values are better than higher values. Of the 24 feasible states, Hop will select the one with the lowest value as the solution. In this case, S23 is our solution.
Exact diagram that’s explored all states and associated values. Hop selects S23 because it has the lowest value of all feasible states. (Only some state attributes are shown for some nodes in Layer 4 for simplicity.)
This walkthrough showed an unlimited scenario. Within Hop, this corresponds to
expansion.Limit = 0. So what would happen if we did impose a limit? Let’s try setting
expansion.Limit = 1, where the integer value represents the number of child states Hop will explore at a time.
We start at S0, our root state, and walk the diagram like we did before. S0 produces one child state, S1, in Layer 1. This is within our defined expansion limit. Hop keeps exploring. Layer 2 of our diagram generates two child states. We can’t explore both because we set our expansion limit to 1.
Which does Hop choose? Hop looks at the value of each state and will pursue the one with the lower value. (This is known as a “greedy search.”) In this case, S2 has the lower value so the model generates S2’s child states but not S3’s. S2 results in three child states. The expansion limit tells Hop to pick one. Hop looks for the lowest value, in this case S5, and keeps going. S5 generates four child states. Hop selects a state with the lowest value. But this time there are no further child states to explore. Hop can return S15 as the solution for how to route our driver. Decision made.
With the expansion limit set to 1, the model limits the number of states it has to generate by more than half. This reduces the number of states Hop has to search across to arrive at a solution.
By setting an expansion limit, we reduce the state space that Hop must explore to find an operational solution. This is particularly apparent at larger scale — tens or hundreds of drivers visiting hundreds to thousands of locations. The expansion limit technique gets us to a first feasible solution more quickly and uses less memory.
The expansion limit implementation we just described is called
Eager. It’s one of two expansion implementations we’ve developed with the v0.7.0 release. The second one is called
Lazy, and it’s even more efficient in returning the first feasible solution and managing memory use.
The Lazy expander has an edge over the Eager expander. We’ve engineered Lazy to be more clever in helping Hop generate and navigate the state space. Where Eager gives you the option to generate all child states up front, Lazy lets you generate them on demand, therefore limiting the number of overall states generated.
The Lazy expander implementation accomplishes this by calculating the values of child states before generating the complete state (and all of its attributes).
In this example, the expansion limit is set to 1 using the Lazy implementation. This approach generates fewer state spaces than Eager.
The Lazy implementation of expansion limits comes with demonstrated performance improvements. We’ve compared previous Hop releases to v0.7.0 running internal benchmark sets configured with a time limit of 10 seconds and an expansion limit of 1.
Here is a capacitated fleet example with 30,000 customers and 256 vehicles. Hop found an operational solution after 3.7 seconds.
Here is an example with 4,461 locations for which hop found this first solution after 6.6 seconds:
After walking through the examples above, you might be trying to reconcile the solution we got when the expansion limit was set to 0 (S23, V=15) compared to when it was set to 1 (S15, V=25). The solution in the first scenario is better than the second. In fact, it is the optimal solution. While this is true, that doesn’t mean that the second scenario returned a bad result. It returns a first solution very quickly and improves on that solution over time. And if given enough time, it will also find the optimal solution.
Let’s take a step back to understand why. The example we’ve explored in this post looks at a single driver and four locations. Imagine what our diagram would like at scale with more drivers and locations?
When dealing with real-time operations, it’s important to keep in mind that best is the enemy of good. For a food delivery service, for example, you might have mere seconds to determine how to route a driver in order to keep up with your business needs. Finding the best solution could take minutes or hours. By that time, the moment has passed, the pizzas are cold, and your customers aren’t happy. Hop can deliver a good route that aligns with your business goals within the seconds needed to keep operations going.
As of Hop v0.7.0, all Hop models have configurable expansion limits. All Hop models (except for knapsack) use the Lazy implementation by default to make our models as efficient as possible.
Enterprise customers who are upgrading to v0.7.0 will need to migrate their models to use expansion limits. Learn more about the migration details in our documentation.
If you’re interested in trying out our Fleet Routing model for free on Nextmv Cloud, you’ll experience this new capability at work behind the scenes.
You have two vehicles and ten locations to visit. What's the best way to route your fleet? You have seconds to solve and Nextmv Cloud. Ready, set, go!
Transporting raw milk from farms to processing plants is a daily occurrence that seems simple at first glance. But it gets complex quickly when time is of the essence and milk volumes vary.
We've released Hop v0.7.0! This release introduces a cool new feature we call expanders into Hop to help customers manage time to first feasible solution and memory use as they scale their models.
Building decision models into binaries is a beautiful thing. It eliminates a lot of sticky deployment processes and gets you to production faster.
We're thrilled to have FirstMark Capital lead our Series A round, putting even more momentum behind our vision to bring the power of decision science to every developer.
Everyone talks about Santa's big night on his sleigh - a vision of efficiency with millions of chimneys traversed in a mere 24 hours
Launching Nextmv Cloud
Our quarantined world is even more on-demand than it used to be. We order groceries, gadgets and green goddess salad, and they all show up at our doors within minutes.
Routing, Packing, and Clustering - Optimization Fundamentals
We completed our seed round!
How does Hop make decisions?
What does nextmv do?