Composition with Zero Cost Abstraction in Optimization

My name is Uğur Arıkan. I am an Operations Research (OR) scientist in Data and Analytics, DHL. As the OR team, we help global business units optimize their decisions for various business problems such as routing, network planning, container loading and pricing.

Around six years ago, we created our first internal rust repository to experiment our ideas on routing problems. It didn’t take long until I noticed that rust is great for solving two of our biggest challenges simultaneously: efficient computation and composition of business requirements.

For the last two years, we have been developing our core OR tools with rust. This talks reflects the underlying reason of this choice and how rust empowers our OR applications.

To avoid confusion, this talk does not focus on function composition. It rather discusses the importance of composing business criteria and how rust's type system makes it very convenient and efficient 🤩.

A. Our Challenge

As a team, we try to solve as many business problems as possible within our limited time.

Different business problems share certain decision criteria. However, two business problems hardly ever have exactly the same set of criteria, which makes each problem unique.

For brevity, we can assume that there is a set of criteria C for a certain class of problems and each individual business problem can be represented as a subset X = {x | x ∈ C}.

Obviously, we cannot develop a solution for all subsets X. However, we can manage to solve each criterion x ∈ C individually, at least the most relevant and critical ones.

Question is:

Provided that we can handle x, y ∈ C, can we solve the problem X = {x, y}?

This is our challenge for composing business requirements.

What makes it hard is the fact that we cannot sacrifice efficiency, which is a requirement for almost all of our applications.

Numerous Real Life Problems Variants

In order to make it more concrete, consider the routing problem where we are required to create tours.

In its simplest form, we can implement a solver for the traveling salesperson (TSP) problem which creates the optimal sequence given a list of delivery points. You may imagine its signature as simple as taking a tour and a duration matrix, returning back the optimized tour.

fn f1(tour: Tour, duration_matrix: &DurationMatrix) -> Tour { ... }

This algorithm would be useful for our parcel delivery tours; however, we discover that we can do much better in terms of quality in most of the cases. For instance, we use machine learning to extract the knowledge of experienced couriers. We represent these learnings as precedence relations among delivery points. In order to be able to make use of this valuable knowledge, our solver must handle precedence constraints.

fn f2(
    tour: Tour,
    duration_matrix: &DurationMatrix,
    precedence_relations: &PrecedenceRelations,
) -> Tour { ... }

For our time critical deliveries, we are required to visit to certain locations within defined time windows.

fn f3(
    tour: Tour,
    duration_matrix: &DurationMatrix,
    precedence_relations: &PrecedenceRelations,
    time_windows: &TimeWindows,
) -> Tour { ... }

In our pickup and delivery routes, capacity becomes relevant. We must make sure that the volume of the loaded shipments never exceeds the available volume of the truck throughout the tour.

fn f4(
    tour: Tour,
    duration_matrix: &DurationMatrix,
    precedence_relations: &PrecedenceRelations,
    time_windows: &TimeWindows,
    capacity_deltas: &CapacityDeltas,
) -> Tour { ... }

In certain regions, we learn that there are special locations where we can attach and detach trailers to the truck. In other words, capacity is not only a relevant constraint but also a decision. This decision turns out to be critical in creating efficient tours, and hence, our algorithm must also handle this.

fn f5(
    tour: Tour,
    duration_matrix: &DurationMatrix,
    precedence_relations: &PrecedenceRelations,
    time_windows: &TimeWindows,
    capacity_deltas: &CapacityDeltas,
    trailer_state_deltas: &TrailerStateDeltas,
) -> Tour { ... }

You may imagine, as the signature changes, the implementation also changes to handle the new criteria.

The list of variants goes on, but let's limit the number of criteria to five for now, |C| = 5.

In the example, we kept adding the criteria to the previous set. Actually, a business problem can require any subset of these criteria, so we might have 2^|C|-1 = 31 variants.

Actually more because in some cases we can use the same criterion twice. For instance, sometimes we have two capacity constraints one for the weight and one for the volume.

Since f5 is the most general version, we can try to handle each problem with f5. For instance, even if the precedence is not relevant, we can call f5 with an empty precedence list. However, the optimality search will still perform precedence feasibility evaluations for every possible move. This brings us to our second challenge, efficiency.

Efficiency

Once we define a business problem as a mathematical problem, we try to solve it as fast as possible.

In operational problems, speed is simply a business requirement. For instance, in one of our applications, we optimize parcel delivery routes for more than ten thousand couriers every morning after trucks are loaded and before couriers leave the depot. With all surrounding IT systems and api calls, we are given less than half a second to optimize the tour.

In tactical problems where we have more time to solve the problem, speed is still a critical feature. Naively, the faster our code runs, the more solutions we can explore. This allows us to find higher quality solutions within a given time frame.

Rust is very efficient in most of the cases out of the box without any micro-optimizations.

The challenge is to have efficient execution with the required abstractions.

Summarize the Challenge

We have numerous real life problem variants and we are required to solve all these variants within limited development time and with zero-cost abstraction:

• If capacity is irrelevant for the problem, the algorithm must spend zero time on capacity criterion.
• When we receive a new criterion from a use case, we must implement only the new criterion, completely independently of others, and it must be available to be used in any subsets of business criteria.

In other words, we must be able to conveniently and efficiently compose business criteria.

B. Composing Iterators

Iterators are amazing.

Defining computations through iterators are very expressive and often less error prone.

But there is more magic in its power of abstracting away complexity.

Algorithms using Iterators

A local search to find improving moves is of course nothing but iteration over possible moves. And our first important step to solve our challenge was to define the abstraction over the iterators.

Back to the routing example.

A local search takes a tour together with other inputs, improves it and returns the improved tour.

In order to improve the solution, it iterates over the neighbors of the solutions, finds the one with the greatest improvement and moves to it.

The procedure is repeated until none of the neighbors are better; and hence, we stop at the so-called local optimum.

The following method finds the best improving move with respect to the duration criterion.

fn improving_move_duration(
    criterion: &Duration,
    input: &DurationMatrix,
    tour: &Tour,
    initial_cost: u64,
) -> Option<Move> {
    let mut best_cost = initial_cost;
    let mut best_move = None;
    for mv in criterion.moves(input, tour) {
        if mv.cost() < best_cost {
            (best_cost, best_move) = (mv.cost(), Some(mv));
        }
    }
    best_move
}

The moves method of the Duration criterion creates an iterator of moves for the given tour and input. Created iterator goes over the neighbors in a standard order and yields the feasible moves which are later evaluated, and skips the infeasible ones.

We can use this method for our first problem to solve the classical TSP.

If, instead, precedence relations were important for the business case, then we could have used the following.

fn improving_move_precedence(
    criterion: &Precedence,
    input: &PrecedenceRelations,
    tour: &Tour,
    initial_cost: u64,
) -> Option<Move> {
    // looks the same
}

We can see the potential abstraction here. We have three differences to handle:
* Our input is naturally the precedence relations rather than the duration matrix.
* In both implementations, moves method returns an iterator of feasible moves. However, the returned moves are now feasible with respect to precedence constraint rather than duration.
* Further, the new_cost is cost of the tour with respect to precedence criterion rather than duration.

Defining Required Compositions

What if our problem had both of the criteria: duration and precedence?

How do we handle them simultaneously?

We need to define the composition of the three differences mentioned above.
* Input types are different. Naturally, the composed algorithm would require both, so the composition of the inputs could be the tuple of duration matrix and precedence relations.
* Assume our duration criterion yields moves {a, b, c, d} while our precedence criterion yields moves {b, c, e}. What should the composed criteria return? A move is feasible only if it is feasible with respect to all problem criteria. Hence, we must get the intersection {b, c}.
* Finally, the cost of the move. There are different ways to approach this, but the simplest is to add up individual costs. Then, the cost of a feasible move is the sum of its duration-cost and precedence-cost.

Composing Iterators of Feasible Moves

While defining the composition, we sort of decided on implementations for composition of inputs (tuple) and cost (sum).

The challenging one is the intersection of the feasible move sets.

Naively, we can iterate over the moves of the two criteria separately, store them in different collections and get the intersection. However, this will be too slow for our requirements.

Let's say N is the size of the neighborhood. Notice that the criterion-specific implementation has O(N) time complexity and constant space complexity (no allocation).

Even if we manage to keep the time complexity of the naive implementations (with hash maps) at O(N), it will still be inefficient due to the storage requirement. Number of moves N is at least linear in tour length, often quadratic or cubic. Therefore, the naive approach comes with a significant additional space complexity.

Instead, since all move builders iterate over the standard order, we can create a composed iterator which handles both iterators simultaneously.

enum ComposedNextResult {
    OneIteratorConsumed,
    BothYieldedSameValue(Move),
    FirstIteratorYieldedSmaller(Move, Move),
    FirstIteratorYieldedGreater(Move, Move),
}

impl ComposedNextResult {
    fn new(move1: Option<Move>, move2: Option<Move>) -> Self {
        match move1.and_then(|x| move2.map(|y| (x, y))) {
            Some((x, y)) => match x.cmp(&y) {
                Ordering::Equal => {
                    let total_cost = x.cost() + y.cost();
                    ComposedNextResult::BothYieldedSameValue(x.with_cost(total_cost))
                }
                Ordering::Greater => ComposedNextResult::FirstIteratorYieldedGreater(x, y),
                Ordering::Less => ComposedNextResult::FirstIteratorYieldedSmaller(x, y),
            },
            None => ComposedNextResult::OneIteratorConsumed,
        }
    }
}

struct SortedIntersectingMoves<Iter1, Iter2>
where
    Iter1: Iterator<Item = Move>,
    Iter2: Iterator<Item = Move>,
{
    iter1: Iter1,
    iter2: Iter2,
}

impl<Iter1, Iter2> Iterator for SortedIntersectingMoves<Iter1, Iter2>
where
    Iter1: Iterator<Item = Move>,
    Iter2: Iterator<Item = Move>,
{
    type Item = Move;
    fn next(&mut self) -> Option<Self::Item> {
        let (x, y) = (self.iter1.next(), self.iter2.next());

        let mut result = ComposedNextResult::new(x, y);

        loop { // to prevent potential stack-overflow issues
            match result {
                ComposedNextResult::OneIteratorConsumed => return None,
                ComposedNextResult::BothYieldedSameValue(k) => return Some(k),
                ComposedNextResult::FirstIteratorYieldedGreater(k1, _) => {
                    result = ComposedNextResult::new(Some(k1), self.iter2.next());
                }
                ComposedNextResult::FirstIteratorYieldedSmaller(_, k2) => {
                    result = ComposedNextResult::new(self.iter1.next(), Some(k2));
                }
            }
        }
    }
}

This is the most complicated bit of our solution yet it fits to the screen.

It is actually pretty simple considering that it single-handedly solves our efficiency problem and sits in the core of our abstraction to achieve the desired flexibility.

SortedIntersectingMoves iterator takes any two generic iterators of moves and returns the list of intersecting moves:
* without any memory allocation (constant space complexity), and
* with the same time complexity as a single move builder (O(M)).

Even better 🤩, since SortedIntersectingMoves itself is an Iterator<Item = Move> it can be further composed with other iterators, allowing us to compose as many move builders as we need.

We can now have a search for improving moves that is generic over any Criterion.

// such as: Duration and Precedence
trait Criterion {
    // such as DurationMatrix or PrecedenceRelations
    type Input;

    fn new() -> Self;

    fn cost_of_tour(input: &Self::Input, tour: &Tour) -> u64;

    fn moves(&mut self, input: &Self::Input, tour: &Tour) -> impl Iterator<Item = Move>;

    fn improving_move(&self, input: &Self::Input, tour: &Tour, initial_cost: u64) -> Option<Move> {
        let mut best_cost = initial_cost;
        let mut best_move = None;
        for mv in self.moves(input, tour) {
            if mv.cost() < best_cost {
                (best_cost, best_move) = (mv.cost(), Some(mv));
            }
        }
        best_move
    }
}

C. Composing Business Criteria

We defined the Criterion which represents a unique business problem. We also defined how the moves iterators could be composed.

The last step is to define the type that represents the composition of two criteria.

struct ComposedCriteria<X1, X2>(X1, X2)
where
    X1: Criterion,
    X2: Criterion;

impl<X1, X2> Criterion for ComposedCriteria<X1, X2>
where
    X1: Criterion,
    X2: Criterion,
{
    // composition #1: tuple
    type Input = (X1::Input, X2::Input);

    // composition #2: sum
    fn cost_of_tour(input: &Self::Input, tour: &Tour) -> u64 {
        let (input1, input2) = input;
        X1::cost_of_tour(input1, tour) + X2::cost_of_tour(input2, tour)
    }

    fn new() -> Self {
        Self(X1::new(), X2::new())
    }

    // composition #3: intersection of feasible moves
    fn moves(&self, input: &Self::Input, tour: &Tour) -> impl Iterator<Item = Move> {
        let (input1, input2) = input;
        let iter1 = self.0.moves(input1, tour);
        let iter2 = self.1.moves(input2, tour);
        SortedIntersectingMoves { iter1, iter2 }
    }
}

Even better 🤩, since ComposedCriteria itself is a criterion, it can be composed further with other criteria.

And this is it!

We can now compose any business criteria, freely and arbitrarily.

The following is our local search function. It looks terribly simple. However, it is as efficient as could be and works for any possible combination of business criteria.

fn local_search<X>(input: &X::Input, tour: Tour) -> Tour
where
    X: Criterion,
{
    let criterion = X::new();
    let mut tour = tour;

    let mut cost = X::cost_of_tour(input, &tour);
    while let Some(mv) = criterion.improving_move(input, &tour, cost) {
        mv.apply(&mut tour);
        cost = mv.cost();
    }

    tour
}

Assume we independently implemented five criteria: Duration, Precedence, Capacity, TimeWindows and TrailerState. In one of our use cases we need to find shortest duration tours while satisfying precedence relations and capacity constraint. We can solve this business problem as follows.

type MyCriteria = ComposedCriteria<ComposedCriteria<Duration, Precedence>, Capacity>;

let initial_tour = Tour; // construct an initial tour

let my_inputs = ((duration_matrix, precedence_matrix), capacity_deltas);

let optimized_tour = local_search::<MyCriteria>(&my_inputs, initial_tour);

D. Convenience by Builders

This was already pretty convenient.

However, the type signatures are naturally complex, especially when we have many business constraints. For instance, if we had five criteria at once, we would have the following.

type MyCriteria = ComposedCriteria<
    ComposedCriteria<
        ComposedCriteria<ComposedCriteria<Duration, Precedence>, Capacity>,
        TimeWindows,
    >,
    TrailerState,
>;

let initial_tour = Tour; // construct an initial tour
let my_inputs = (
    (
        ((duration_matrix, precedence_matrix), capacity_deltas),
        time_window_list,
    ),
    trailer_state_deltas,
);
let optimized_tour = local_search::<MyCriteria>(&my_inputs, initial_tour);

If you are bad with many nested parentheses, as I am, this can get out of hands.

Builder pattern to the rescue.

We first define our LocalSolver type for any generic criterion which stores the inputs, so that we do not need to organize them in the tuples with the correct parenthesis.

Using the builder pattern, we must be able convert a local solver of X to a local solver of X and Y. We already know that the criterion which is the composition of X and Y is ComposedCriteria<X, Y>. It seems like we have everything we need.

struct LocalSolver<X: Criterion> {
    input: X::Input,
}

impl<X: Criterion> LocalSolver<X> {
    fn new(input: X::Input) -> Self {
        Self { input }
    }

    fn and_with<Y: Criterion>(self, input: Y::Input) -> LocalSolver<ComposedCriteria<X, Y>> {
        LocalSolver::new((self.input, input))
    }

    fn run(&self, tour: Tour) -> Tour {
        let criterion = X::new();
        let mut tour = tour;

        let mut cost = X::cost_of_tour(&self.input, &tour);
        while let Some(mv) = criterion.improving_move(&self.input, &tour, cost) {
            mv.apply(&mut tour);
            cost = mv.cost();
        }

        tour
    }
}

We move the free standing local_solver function as a method of the LocalSolver type, there is no notable difference in the implementation.

Importantly, LocalSolver defines two constructors:
* new is the default constructor which creates the algorithm for a specific criterion with its input.
* and_with, on the other hand, converts the algorithm into a variant which handles its current criterion together with the additional criterion Y with its input.

This brief setup provides us with all the convenience we desire.

Now, we can run our algorithm without typing out any complex types.

// inputs
let duration_matrix = DurationMatrix;
let precedence_relations = PrecedenceRelations;
let capacity_deltas = CapacityDeltas;
let time_window_list = TimeWindowList;
let trailer_state_deltas = TrailerStateDeltas;

let initial_tour = Tour; // construct an initial tour

// algorithm
let algorithm = LocalSolver::<Duration>::new(duration_matrix)
    .and_with::<Precedence>(precedence_relations)
    .and_with::<Capacity>(capacity_deltas)
    .and_with::<TimeWindows>(time_window_list)
    .and_with::<TrailerState>(trailer_state_deltas);

let optimized_tour = algorithm.run(initial_tour);

When I check just out of curiosity, the compiler shows the following as the type of the algorithm:

LocalSolver<ComposedCriteria<ComposedCriteria<ComposedCriteria<ComposedCriteria<Duration, Precedence>, Capacity>, TimeWindows>, TrailerState>>

If we try carefully, we could manage to write this down, but we never need to. It is just one of the numerous local search variants that we can create and use.

Extensibility

Now the best part.

Going back to our challenge.

We aim to solve as many business problems as possible with the tools we develop in our limited time.

Assume that we talk to another business unit which has a specific business requirement. They need certain pairs (or groups) of delivery addresses to be served together. Their internal order might change but they must be consequent in the created tour.

Let's call this new criterion, GroupedVisits.

This business problem most likely involves some of the other criteria from what we already have implemented. Actually, let's assume it requires all five.

In order to solve this problem, we only need to focus on the new criterion and implement its moves iterator.

struct GroupedVisits;

struct GroupedVisitList;

impl Criterion for GroupedVisits {
    type Input = GroupedVisitList;

    fn cost_of_tour(input: &Self::Input, tour: &Tour) -> u64 { ... }

    fn init() -> Self { ... }

    fn moves(&mut self, input: &Self::Input, tour: &Tour) -> impl Iterator<Item = Move> { ... }

And everything will compose smoothly and efficiently.

let duration_matrix = DurationMatrix;
let precedence_relations = PrecedenceRelations;
let capacity_deltas = CapacityDeltas;
let time_window_list = TimeWindowList;
let trailer_state_deltas = TrailerStateDeltas;
let grouped_visit_list = GroupedVisitList;

let initial_tour = Tour; // construct an initial tour

let algorithm = LocalSolver::<Duration>::new(duration_matrix)
    .and_with::<Precedence>(precedence_relations)
    .and_with::<Capacity>(capacity_deltas)
    .and_with::<TimeWindows>(time_window_list)
    .and_with::<TrailerState>(trailer_state_deltas)
    .and_with::<GroupedVisits>(grouped_visit_list);

let optimized_tour = algorithm.run(initial_tour);

Further, like all other criteria, GroupedVisits will be available for any possible combination of business requirements.

This makes the development time of grouped visits much more valuable, allows and motivates us to continuously enhance our core solvers piece by piece.

Conclusion

We only discussed composition of business criteria here; however, in our real life applications:
* we need to abstract over concrete input types as different problems have different data representations, data sizes and memory requirements;
* we need to be able to compose local solvers over different neighborhoods which is crucial in improving the solution quality;
* and so on.

Without a great type system support, this complexity quickly turns into a maintenance mess where adding value to existing solutions is not possible. Rust helps us to solve this complexity conveniently and without sacrificing efficiency with:
* zero cost abstraction (monomorphization),
* traits, associated and generic associated types for composing business requirements, algorithm variants, etc.,
* and of course, with the power of iterators to abstract away complexity.

At the same time, we enjoy all other great features of rust, such as:

• memory safety that just comes for free!
• fewer bugs thanks to explicit mutability and borrow checker
• almost trivial parallelization over iterators
• great support and idioms for error handling
• nice code quality standards thanks to the clippy

We are very happy that we are building state of the art OR tools with rust which are maintainable, extensible, and last but not least, lots of fun to work on.