Recently, there was some commotion on Twitter because a competitor heavily restricts publicizing benchmarks of their Solver as part of their license. That might seem harsh, but I can understand the sentiment: when a competitor publicizes a benchmark report comparing our product against their own, I know we’re gonna get screwed. Unlike single product benchmarking, competitive benchmarking is inherently dishonest…

Competitive benchmarking for dummies

As as competitor, you can utilize several (obvious and not so obvious) means to prove your superiority over another Solver:

• Publication bias
  • Pick a use case which is known to work well in your Solver.
  • Use datasets with a scale and granularity which are known to work well in your Solver.
  • If you’re really evil, benchmark multiple use cases and datasets in both Solvers and only retain those for which your Solver wins.
• Expertise imbalance
  • Let one of your experts develop an implementations for both Solvers.
    • Motivation: like any other company, your company only employs experts in your own technology.
  • If he has years of recent experience in your technology, it’s unlikely he’ll had time for any recent experience in the competitive technology.
    • So you’re effectively using your jockey on someone else’s horse.
• Tweaking imbalance
  • Spend an equal amount of time on both implementations.
    • The use case is probably already implemented in your Solver (or straightforward to implement), so you can spend most of the time budget to tweak it better.
    • You’ll need to learn the competitor’s Solver first, so you’ll spend most of the time budget in that implementation to learn the technology, which leaves no room for tweaking.
• Funding
  • There’s no need to explicitly set a desired outcome: your developer will know better than to bite the hand that feeds him.

Notice how these approaches don’t require any malice (except for the evil one): it’s normal to conduct a competitive benchmark like this…

Furthermore, you can make the competitive benchmark comparison look more objective, by sponsoring an academic research group to do the benchmark for you. Just make sure that’s a research group which has been happily using your technology for years and has little or no experience with the competition.

Marketing value

The marketing value of such a benchmark report should not be underestimated. These numbers, written in black and white, which clearly show the superiority of your Solver against another Solver, make a strong argument:

• To close sales deals, when in direct competition with the other Solver.
• To convince developers, researchers and students to learn and use your technology.
• To build a strong, long-term reputation.
  • Benchmarks from the 90’s can still affect the Google search results today, for example for “performance of Java vs C++”.
  • Such information spreads virally, and counter claims might not.

Empirical evidence

Are all competitive benchmark reports lying? Yes, they are probably misrepresenting the truth.

Should we therefore restrict users from publicizing benchmarks on our Solver? No, of course not (even if our open source licence would allow such conditions, which it does not).

Computer science - like any other science - is built on empirical evidence: the promise that any experiment I publish can be repeated by others independently. If we prevent people from publishing such repeated experiments, we undermine our science. In fact, the more people which report their benchmarks, the clearer our strengths and weaknesses show. Historically, this approach has already enabled us to diagnose and fix weaknesses, regardless whether those were caused by our Solver or the user’s domain specific implementation.

Therefore, OptaPlanner welcomes external benchmark reports. I believe in Open Science, as strongly as I believe in Open Source. I do ask the courtesy of allowing public comments/feedback on a public report website, as well as to publicize the details (such as the Solver configuration). If you use the OptaPlanner Benchmarker toolkit (which you will find convenient), simply share the benchmarker HTML report.

To run any of the benchmarks of the OptaPlanner Examples locally, simply run a *BenchmarkApp executable class, for example CloudBalancingBenchmarkApp. Notice how a small change in the *BenchmarkConfig.xml, such as switching score calculation from Easy Java to Drools or from Drools to Incremental Java, can have a serious effect in the results.

In short: I like external benchmarks, but dislike competitive benchmarks, except for …

Independent research challenges

Can we compare fairly with our competition? Yes, through an independent research challenge.

Regularly, the academic community launches such challenges. Each challenge:

• defines a real-world use case with real-world constraints
• provides multiple, real-world datasets (half of which they keep hidden)
• expects reproducible results within a specific time limit on specific hardware
• gets worldwide participation from the academic and/or enterprise Operations Research community
• benchmarks each contestant’s implementation on the same hardware in the same time limit to determine a winner
• benchmarks those hidden datasets to counter overfitting and dataset recognition

It’s fair: each jockey rides his own horse. Most of the arguments against competitive benchmarking do not apply. And as an added bonus, we get to learn from and compare with the academic research community.

In the past, OptaPlanner has done well on these challenges, despite the limited weekend time we have to spend on them. In the last challenge, the ICON power scheduling challenge, we (Lukas, Matej and me) finished in 2nd place. A minority of the researchers still beat us (with their innovative algorithms in their experimental contraptions and massive time to tweak/build those), but it’s been years since a competitive Solver has beaten us.

Long term vision

Sharing our benchmarks and enabling others to easily reproduce them, is part of a bigger vision: Too many research papers (on metaheuristics and other optimization algorithms) are hard to reproduce. That’s the paradox in computer science research: to reproduce the findings of a research paper, all we really need is a computer and the code. We don’t need an expensive laboratory. Yet, in practice, the code is usually closed and the raw benchmark data is not accessible. It’s like everyone is scared of sharing the dirty secrets of their code and their benchmarks.

I believe that we - the worldwide optimization research community - need to create a benchmark repository: a centralized repository of benchmarks for every use case, for every dataset, for every algorithm, for every implementation version, for any amount of running time. That, together with a good statistical interface, will give us some real insight as to which optimization algorithms are good under which circumstances.

We - in OptaPlanner - are well on our way to build exactly that:

• OptaPlanner Examples already implements 14 distinct use cases.
• For each use case, we’re already benchmarking on many different optimization algorithms.
• Our benchmarker HTML report already includes many useful statistics to analyse the raw benchmark data.

In the real world, vehicles in a Vehicle Routing Problem (VRP) have to follow the roads: they can’t travel in a straight line from customer to customer. Most VRP research papers and demos happily ignore this implementation detail. As did I, in the past. Although using road distances (instead of air distances) doesn’t impact the NP-hard nature of a VRP much, it does result in a few extra challenges. Let’s take a look at those challenges.

Datasets with road distances

First off, we need realistic datasets. Unfortunately, public VRP datasets with road distances are scarce in the VRP research community. The VRP Web has few small ones, such as a dataset of Bavaria with 29 locations, but nothing serious. So I had to generate some realistic datasets myself with the following requirements:

1. Use Google Maps like roads with real distances in km between every pair of locations in the dataset.
   • For example, use highways when reasonable over small roads.
2. For every dataset, generate an air distance variant and a road distance variant, to compare results.
3. Generate a similar dataset in multiple orders of magnitude, to compare scalability.
4. Add reasonable vehicle capacities and customer demands, for the vehicle capacity constraint in VRP.

I ended up generating datasets of Belgium with a location for cities, towns and subtowns. The biggest one has 2750 locations. I might add a road variant of the USA datasets later, those go up to 100 000 locations.

By using the excellent Java library GraphHopper, based on OpenStreetMap, querying practical road distances was relatively easy. It’s also fast, as long as the entire road network (only 200MB for Belgium) can be loaded into memory. Loading the entire road network of North-America (6GB) is a bit more challenging. I’ll submit these datasets to the VRP Web, so others researchers can use them too.

All this happens before OptaPlanner's VRP example starts solving it. During solving, the distances are already available in a lookup table. Once we start generating datasets with 1000 locations or more, pre-calculating all distances between every location pair can introduce memory and performance issues. I’ll explain those and the remedies in my next blog.

Air distance vs Road distance

For clarity, I’ll focus on the dataset belgium-n50-k10.vrp which has 50 locations and 10 vehicles with capacity 125 each. OptaPlanner was given 5 minutes to solve both variants (air and road distance).

Using air distances (which calculates the euclidean distance based on latitude and longitude) results in:

The total distance, 22.99 doesn’t mean much because it’s not in a common unit of measurement and because our vehicles can’t fly from point to point anyway. We need to apply this air distance solution on the real road network (shown below), to know the real distance:

Now, let’s compare that air distance solution above with the road distance solution below.

The road distance solution takes 108.45 km less, so it’s almost 5% better! And that’s on one of the most dense road networks in the world (Belgium’s road network): on more sparse road networks the gain might be more.

Conclusion

Using real distances instead of air distances does matter. Solving an VRP with air distances and then apply road distances is suboptimal.

Many Solver distributions include an N Queens example, in which n queens need to be placed on a n*n sized chessboard, with no attack opportunities. So when you’re looking for the fastest Solver, it’s tempting to use the N Queens example as a benchmark to compare those solvers. That’s a tragic mistake, because the N Queens problem is solvable in polynomial time, which means there’s a way to cheat.

That being said, OptaPlanner solves the 1 000 000 queens problem in less than 3 seconds :) Here’s a log to prove it (with time spent in milliseconds):

INFO  Opened: data/nqueens/unsolved/10000queens.xml INFO  Solving ended: time spent (23), best score (0), ...INFO  Opened: data/nqueens/unsolved/100000queens.xml INFO  Solving ended: time spent (159), best score (0), ...INFO  Opened: data/nqueens/unsolved/1000000queens.xml INFO  Solving ended: time spent (2981), best score (0), ...

How to cheat on the N Queens problem

The N Queens problem is not NP-complete, nor NP-hard. That is math speak for stating that there’s a perfect algorithm to solve this problem: the Explicits Solutions algorithm. Implemented with a CustomPhaseCommand in OptaPlanner it looks like this:

public class CheatingNQueensPhaseCommand implements CustomPhaseCommand {

   public void changeWorkingSolution(ScoreDirector scoreDirector) {
       NQueens nQueens = (NQueens) scoreDirector.getWorkingSolution();
       int n = nQueens.getN();
       List<Queen> queenList = nQueens.getQueenList();
       List<Row> rowList = nQueens.getRowList();

       if (n % 2 == 1) {
           Queen a = queenList.get(n - 1);
           scoreDirector.beforeVariableChanged(a, "row");
           a.setRow(rowList.get(n - 1));
           scoreDirector.afterVariableChanged(a, "row");
           n--;
       }
       int halfN = n / 2;
       if (n % 6 != 2) {
           for (int i = 0; i < halfN; i++) {
               Queen a = queenList.get(i);
               scoreDirector.beforeVariableChanged(a, "row");
               a.setRow(rowList.get((2 * i) + 1));
               scoreDirector.afterVariableChanged(a, "row");

               Queen b = queenList.get(halfN + i);
               scoreDirector.beforeVariableChanged(b, "row");
               b.setRow(rowList.get(2 * i));
               scoreDirector.afterVariableChanged(b, "row");
           }
       } else {
           for (int i = 0; i < halfN; i++) {
               Queen a = queenList.get(i);
               scoreDirector.beforeVariableChanged(a, "row");
               a.setRow(rowList.get((halfN + (2 * i) - 1) % n));
               scoreDirector.afterVariableChanged(a, "row");

               Queen b = queenList.get(n - i - 1);
               scoreDirector.beforeVariableChanged(b, "row");
               b.setRow(rowList.get(n - 1 - ((halfN + (2 * i) - 1) % n)));
               scoreDirector.afterVariableChanged(b, "row");
           }
       }

   }

}

Now, one could argue that this implementation doesn’t use any of OptaPlanner’s algorithms (such as the Construction Heuristics or Local Search). But it’s straightforward to mimic this approach in a Construction Heuristic (or even a Local Search). So, in a benchmark, any Solver which simulates that approach the most, is guaranteed to win when scaling out.

Why doesn’t that work for other planning problems?

This algorithm is perfect for N Queens, so why don’t we use a perfect algorithm on other planning problems? Well, simply because there are none!

Most planning problems, such as vehicle routing, employee rostering, cloud optimization, bin packing, …​are proven to be NP-complete (or NP-hard). This means that these problems are in essence the same: a perfect algorithm for one, would work for all of them. But no human has ever found such an algorithm (and most experts believe no such algorithm exists).

Note: There are a few notable exceptions of planning problems that are not NP-complete, nor NP-hard. For example, finding the shortest distance between 2 points can be solved in polynomial time with A*-Search. But their scope is narrow: finding the shortest distance to visit n points (TSP), on the other hand, is not solvable in polynomial time.

Because N Queens differs intrinsically from real planning problems, it is a terrible use case to benchmark.

Conclusion

Benchmarks on the N Queens problem are meaningless. Instead, benchmark implementations of a realistic competition. A realistic competition is an official, independent competition:

1. that clearly defines a real-word use case
2. with real-world constraints
3. with multiple, real-world datasets
4. that expects reproducible results within a specific time limit on specific hardware
5. that has had serious participation from the academic and/or enterprise Operations Research community

‍

To solve a planning or optimization problem, some solvers tend to scale out poorly: As the problem has more variables and more constraints, they use a lot more RAM memory and CPU power. They can hit hardware memory limits at a few thousand variables and few million constraint matches. One way their users typically work around such hardware limits, is to use MapReduce. Let’s see what happens if we MapReduce a planning problem, such as the Traveling Salesman Problem.

About MapReduce

MapReduce is programming model which has proven to be very effective to run a query on big data. Generally speaking, it works like this:

• The data is partitioned across multiple computer nodes.
• A map function runs on every partition and returns a result.
• A reduce function reduces 2 results into one result. It’s continuously run until only a single result remains.

For example, suppose we need to find the most expensive invoice record in a data cluster:

• The invoice records are partitioned across multiple computer nodes.
• For each node, the map function extracts the most expensive invoice for that node.
• The reduce function takes 2 invoices and returns the most expensive.

About the Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is a very basic planning problem. Given a list of cities, find the shortest path to visit all cities.

For example, here’s a dataset with 68 cities and its optimal tour with a distance of 674:

The search space of this small dataset has 68! (= 1096) combinations. That’s a lot.

A more realistic planning problem, such vehicle routing, has more constraints (both in number as in complexity), such as: vehicle capacity, vehicle type limitations, time windows, driver limits, etc.

MapReduce on TSP

Even though most solvers probably won’t go out of memory on only 68 variables, the small size of this problem allows us to visualize it clearly:

Let’s apply MapReduce on it:

1) Partition: Divide the problem into n pieces

First, we take the problem and split it into n pieces. Usually, n is the number of computer nodes in our system. For visual reasons, we divide it into only 4 pieces:

TSP is easily partitioned because of it only has 1 relevant constraint: find the shortest path.

In a more realistic planning problem, sane partitioning can be hard or even impossible. For example:

• In capacitated vehicle routing, no 2 partitions should share the same vehicle. What if we have more partitions than vehicles?
• In vehicle routing with time windows, each partition should have enough vehicle time to service each customer and drive to each location. Catch 22: How do we determine the drive time if we don’t know the vehicle routes yet?

It’s tempting to make false assumptions.

2) Map: Solve each piece separately

Solve each partition using a Solver:

We get 4 pieces, each with a partial solution.

3) Reduce: Merge solution pieces

Merge the pieces together. To merge 2 pieces together, we remove an arc from each piece and add 2 arcs to connect cities of different pieces:

We do merge several times until all pieces are merged:

There are several ways to merge 2 pieces together. Here we try every combination and take the optimal one. For performance reasons, we might instead connect the 2 closest cities of different pieces with an arc, and then add a correcting arc on the other side (however long that may be).

In a more realistic planning problem, with more complex constraints, merging feasible partial solutions often results into an infeasible solution (with broken hard constraints). Smarter partitioning, which takes all the hard constraints into account, can sometimes solve this…​at the expense of more broken soft constraints and a higher maintenance cost.

4) Result: What is the quality of the result?

Each piece was solved optimally. Pieces were merged optimally. But the result is not optimal:

In fact, the results aren’t even near optimal, especially as we scale out with a MapReduce approach:

• More variables result in a lower result quality.
• More constraints result in a lower result quality, presuming it’s even possible to partition and reduce sanely.
• More partitions result in a lower result quality.

Conclusion

MapReduce is great approach to handle a query problem (and presumably many other problems). But MapReduce is a terrible approach on a planning or optimization problem. Use the right tool for the job.

Note: We applied MapReduce on the planning problem, not on the optimization algorithm implementation in a Solver, for which it can make sense. For example, in a depth-first search algorithm, MapReduce can make sense to explore the search tree (although the search tree scales exponentially bad which dwarfs any gain of MapReduce).

To solve a big planning problem, use a Solver (such as OptaPlanner, now continued as Timefold) that scales well in memory, so you don’t need to resort to partitioning at the expense of solution quality.

‍

Not every organization is comfortable with letting a computer program, such as OptaPlanner, now continued as Timefold (Java, open source planning engine), optimize their schedules. Let’s take a look why - and how to remedy it - on the course scheduling example.

Course scheduling introduction

In course scheduling, we need to assign each lecture to a time and a place. So we’re basically telling teachers and students were to be at what time. In the example schedule below, the Math lecture will be given the Monday morning in room 36:

In the example above, OptaPlanner has come up with a feasible schedule. This means that no room, nor any teacher, nor any student has 2 lectures at the same time.

The boss wants to do it differently

Despite that the previous schedule is optimized according to the score function (which the boss probably defined in the first place), the boss wants to make some ad hoc changes. The Math lecture should be given on Tuesday morning instead of Monday morning:

The schedule is now infeasible because Geo and Math are now in the same room at the same time. So we ask the computer to make it feasible…​

“I’m sorry Dave, I’m afraid I can’t do that”

... and the first thing the computer does is change the Math lecture to another time and place:

The boss is unhappy because his commands are ignored. Let’s fix that.

Immovable lecture

We lock the Math lecture in place, making it immovable for OptaPlanner:

When we now solve the problem, the Math lecture isn’t moved. We get a feasible solution which makes the boss happy too:

Video demo

If you want to see this in action, skip to the end of this video:

The human must remain in control

We regularly see this requirement in other OptaPlanner use cases too (such as employee rostering, vehicle routing and equipment scheduling). But hopefully this article has shown that the human is indeed in control. There’s no Skynet or HAL algorithm to disobey us…​ for now :)

Many companies are faced with the vehicle routing problem, when they need to:

• Deliver/pick up items at multiple locations
• Or execute repairs/maintenance at multiple locations

These companies want to minimize their fuel and time usage, to reduce their costs and ecological footprint. Sounds easy, right? Just take the shortest route. Unfortunately it’s not that simple…​ Let’s take a closer look.

Minimize the distance

In Vehicle Routing Problem (VRP), we need to transport items from the warehouse to the customers:

In this case, we have 7 customers across the region and 2 available vehicles stationed at the warehouse.

The shortest route to visit all these customers is this:

This optimal solution requires 210 fuel (which includes each vehicle driving back to the warehouse).

Notice that we only use 1 vehicle. Let’s continue from that assumption.
Assumption: An optimal VRP route uses only 1 vehicle. (false)

Vehicle capacity

In a real-world delivery/pick up scenario, each customer needs a number of items, but a vehicle’s capacity to transport items is limited.

In this case, all 7 customers need 20 items and a vehicle can transport 100 items. So a single vehicle cannot transport the 140 items of all customers.

We need to use 2 vehicles now:

This optimal solution requires 224 fuel, which is - of course - more than the 210 fuel of the previous solution. The yellow truck transports 60 items and the green one 80 items.

Notice that none of the lines cross. Let’s assume that’s always the case.
Assumption: An optimal VRP route has no crossing lines. (false)

Let’s see what happens when some of the customers require more items than other customers.

In this case, 2 customers need 50 items and the other 5 still need 20 items. So the previous solution is infeasible because the yellow truck would need to transport 120 items.

Now the lines do need to cross:

The optimal solution now requires even more fuel: 284. We found a feasible solution with 2 vehicles.

So we don’t seem to need any more vehicles.
Assumption: An optimal, feasible VRP route with n vehicles is still optimal for n+1 vehicles. (false)

Let’s add a 3rd vehicle to disprove that:

By adding an extra vehicle, the optimal solution now uses less fuel: only 274. This is a paradox: buying more vehicles can reduce expenses.

Notice that in both solutions above, no vehicle crosses its own line.
Assumption: An optimal VRP route has no crossing lines of the same color. (false)

Time Windows

In any real-world scenario, time is of the essence. Items need to be delivered on time, within the time window of each customer.

In the case above, a vehicle needs to arrive at the top left customer between 3 and 4 o’clock. Different customers have different time windows. For example, all 4 customers on the right are flexible: they are available between 1 and 6 o’clock. Additionally, each delivery/pick up/repair at a customer takes 1 hour to complete.

In the optimal solution, the yellow truck does cross its own line now:

In the optimal solution, the yellow truck arrives at the most left customer at 1 o’clock. An hour later it leaves for the bottom left customer at which it arrives at 2:20 (because driving takes some 20 minutes). Again an hour later it departs and arrives at its 3rd customer at 3:40.

Notice how the time windows pretty much dictate the route, especially on the left side.
Assumption: We can focus on time windows before focusing on capacity (or vice versa). (false)

Let’s see what happens if the time windowed customers also need a number of items:

Given these requirements, we need to focus on the capacity and the time windows in parallel:

The optimal solution now puts the bottom right customer in the yellow truck, because there was no more room in the green truck.

Conclusion

In a real-world vehicle routing problem, many assumptions fail. Finding a good solution is hard: there are no short-cuts. We need to be able to optimize without making assumptions. Yet, we cannot iterate through all possible states in a brute force manner either - even on relatively small problems - because of hardware limitations. So we need good, flexible algorithms - such as the heuristics and metaheuristics implemented in OptaPlanner, now continued as Timefold (Open Source, Java) - to solve bigger cases:

‍