How Hop Hops

Hop is a tool for automating decisions in production software stacks. These including things like routing, assignment, and pricing. Hop lets you encode your business rules and objectives in Go. You then build them into into simple, atomic binaries that read and write JSON data, and ship them off to just about any environment, from an edge device to AWS Lambda.

Hop handles the search part of finding solutions to business problems. Under the hood it uses decision diagram techniques. This post provides a basic introduction to these mechanics. It is not exhaustive, and merely imparts a working knowledge of some of the concepts underlying Hop's algorithms. For the theoretical foundations of optimization using decision diagrams, see the excellent book on the subject.

State-Based Models

Hop provides various solvers for maximizing or minimizing an objective, an satisfying a set of constraints. All of these require the modeler to provide a root state.

Think of the root as the starting point for search. It encodes the state of a system right now. In a delivery network, for example, the root state might include the current location and backlog for every driver, where unassigned orders go, and recent observations of travel speeds.

A Hop state must implement two methods: Feasible and Next.

```go
package model

type State interface {
	Feasible() bool
	Next() []State
}
```

Feasible should return true if a state is actionable. This means it can be implemented in the real world. Most decision models are feasible once they have considered and assigned some value to every choice they need to make.

Next should return every state that can be reached from a given state. Think of it as a transition function that projects the state of a system once a choice is made.

If we are maximizing or minimizing some objective, our model also needs a Value method to tell Hop the value of each state.

```go
type Valuer interface {
	Value() int
}
```

An example should make this clear.

Example: Knapsack Problems

Consider the 0-1 knapsack problem. We have a set of items 1 through n. Each item has a value and a weight. We can carry a total weight of 50. We would like to carry the maximum possible value within our weight limit.

Let's say our input data looks like this.

| Item | Value | Weight |
|:---- | -----:| ------:|
| 1    |   200 |     25 |
| 2    |   150 |     10 |
| 3    |   225 |     20 |

‍

Let's figure out how to model it as a decision diagram.

To get started, we need a root state. We aren't carrying anything to begin with, so our root state R is an empty set of items. It has weight and value of 0 each. We also call this the root "layer" and say it has a depth of 0. It is infeasible because we haven't made decisions about any items yet.

| State | Depth | Items | Value | Weight | Feasible |
|:----- | -----:| -----:| -----:| ------:|:-------- |
| `R`   |     0 |     - |     0 |      0 | No       |

‍

Let's consider packing each item in order 1 through n. For each item, we have two options: leave it out or pack it. States R0 and R1 correspond to those two options for item 1. Together they form layer 1 of our diagram. Note that we have more items to decide on, so we continue to label our states as infeasible.

| State | Depth | Items | Value | Weight | Feasible |
|:----- | -----:| -----:| -----:| ------:|:-------- |
| `R0`  |     1 |     - |     0 |      0 | No       |
| `R1`  |     1 |     1 |   200 |     25 | No       |

‍

Now we decide what to do about item 2 in the same manner. Isn't it nice having computers to do this sort of work for us?

| State | Depth | Items | Value | Weight | Feasible |
|:----- | -----:| -----:| -----:| ------:|:-------- |
| `R00` |     2 |     - |     0 |      0 | No       |
| `R01` |     2 |     2 |   150 |     10 | No       |
| `R10` |     2 |     1 |   200 |     25 | No       |
| `R11` |     2 |   1,2 |   350 |     35 | No       |

‍

Deciding whether or not to include item 3 generates a layer with 8 states in it. Each layer has twice the number of states (the "width") of the layer before it. This is called "expanding" the next layer. If you're thinking that our layers are going to get hopelessly big with a small number of items, you're right!

| State  | Depth | Items | Value | Weight | Feasible |
|:------ | -----:| -----:| -----:| ------:|:-------- |
| `R000` |     3 |     - |     0 |      0 | Yes      |
| `R001` |     3 |     3 |   225 |     20 | Yes      |
| `R010` |     3 |     2 |   150 |     10 | Yes      |
| `R011` |     3 |   2,3 |   375 |     30 | Yes      |
| `R100` |     3 |     1 |   200 |     25 | Yes      |
| `R101` |     3 |   1,3 |   425 |     45 | Yes      |
| `R110` |     3 |   1,2 |   350 |     35 | Yes      |
| `R111` |     3 | 1,2,3 |   575 |     55 | No       |

‍

Something interesting happened constructing layer 3. State R111 exceeded our weight limit. So we remove it from consideration as an infeasible state.

There aren't any more states to generate, so we choose R101 as our optimal state. It provides the most value without exceeding our weight limit.

Diagram Restriction

The exercise we just went through constructed what is called an "exact" decision diagram. That means it represents the entire state space of our problem, as shown in the following graph. Note that we leave R111 off the graph since it isn't feasible.

              ___________ R __________
             /                        \
       ___ R0 ___                    _ R1 _
      /          \                  /      \
    R00            R01            R10       R11
   /   \          /   \          /   \       |
R000     R001  R010     R011  R100     R101  R110

Obviously it gets impossible to generate exact diagrams for problems of any reasonable size. Luckily, we have a technique called restriction. Instead of generating all possible states, we merely keep a subset of them up to a configurable diagram width. We defer the remaining states for exploration later. This is exactly what Hop does.

Say we use a "value" restrictor that keeps the best states of each layer and defers the rest. Let's set our maximum diagram width to 2. We want to maximize total value, so the value restrictor keeps the two states from each layer with the highest values. Our restricted decision diagram looks like this.

  R
 / \
R0   R1
   /  \
 R10    R11
 |      |
R101    R110

This diagram is much smaller, and in this case it manages to find the optimal state for our problem. The other states aren't actually gone, we're just going to look at them later. We focussed our search on a promising section of the state space, and it paid off.

Once we've have this restricted diagram, we have two feasible solutions to consider: R101 and R110. R101is the better of the two, so we label it as our "incumbent" (best known solution). Now we can continue searching the rest of the state space. If we find a better feasible state, we'll use that as a new incumbent.

Hop Search Mechanics

We've covered two of the techniques Hop uses to search the state space of a decision model: expansion and restriction. There are many more pieces to Hop's search algorithm, and Hop makes them plug-able so the modeler can exploit domain knowledge about a problem's structure. The more Hop understands about a problem, the more efficient it can be at finding good solutions and reducing the size of the state space.

Briefly, Hop uses the following procedure to explore any state.

• Expand a deeper layer using each state's Next method.
• Filter out states that should not be considered for some reason.
• Reduce states that are dominated by other states.
• Restrict the states for further exploration and defer the rest.
• Merge deferred and previously merged states to generate bounds.

Hop repeats this procedure for each layer. By default, Hop uses a small restriction width to find feasible solutions quickly. Settings like width can be easily overridden using command line options or environment variables. Search components like restrictors can be plugged directly into the solver options. Hop provides interfaces to follow for custom implementations, if so desired.

[ddo]: http://www.andrew.cmu.edu/user/vanhoeve/mdd/
[ddobook]: https://www.springer.com/gp/book/9783319428475
[knapsack]: https://en.wikipedia.org/wiki/Knapsack_problem

‍

‍