<commit_before>= Can MapReduce solve planning problems?
:page-interpolate: true
:awestruct-author: ge0ffrey
:awestruct-layout: blogPostBase
:awestruct-tags: [tsp, insight, algorithm]

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

http://en.wikipedia.org/wiki/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. Its 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 http://en.wikipedia.org/wiki/Travelling_salesman_problem[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+:

image::mapReduceTspBlogExplanation.png[]

The search space of this small dataset has +68!+ (= +10^96^+) 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:

image::mapReduceTspBlog_0.png[]

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:

image::mapReduceTspBlog_1.png[]

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?_

=== 2) *Map*: Solve each piece separately

Solve each partition using a Solver:

image::mapReduceTspBlog_2.png[]

We get 4 pieces, each with a partial solution.

=== 3) *Reduce*: Merge solution pieces

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

image::mapReduceTspBlog_3.png[]

We need to do merge several times:

image::mapReduceTspBlog_4.png[]

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?<commit_msg>blog: it's tempting to make false assumptions<commit_after>= Can MapReduce solve planning problems?
:page-interpolate: true
:awestruct-author: ge0ffrey
:awestruct-layout: blogPostBase
:awestruct-tags: [tsp, insight, algorithm]

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

http://en.wikipedia.org/wiki/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. Its 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 http://en.wikipedia.org/wiki/Travelling_salesman_problem[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+:

image::mapReduceTspBlogExplanation.png[]

The search space of this small dataset has +68!+ (= +10^96^+) 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:

image::mapReduceTspBlog_0.png[]

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:

image::mapReduceTspBlog_1.png[]

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 link:#{relative('/blog/2013/08/06/FalseAssumptionsForVRP.html')}[false assumptions].

=== 2) *Map*: Solve each piece separately

Solve each partition using a Solver:

image::mapReduceTspBlog_2.png[]

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:

image::mapReduceTspBlog_3.png[]

We do merge several times until all pieces are merged:

image::mapReduceTspBlog_4.png[]

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?
{'fraction_non_alphanumeric': 0.056633934688284995, 'fraction_numerical': 0.00890614295501256, 'mean_word_length': 4.800662251655629, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4039338', 'n_tokens_mistral': 2343, 'n_tokens_neox': 2198, 'n_words': 1292}