1
$\begingroup$

In Schrijver's A course in combinatorial optimization (page 49, Application 3.3), I came across the transporting earth problem which is quoted below (replaced the French text by its English translation in footnote 10). I am having trouble in understanding why the geometric method as mentioned in the last paragraph works. It will be highly appreciated if someone can explain this.

Monge [1784] was one of the first to consider the assignment problem, in the role of the problem of transporting earth from one area to another, which he considered as the discontinuous, combinatorial problem of transporting molecules:

When one must transport earth from one place to another, one usually gives the name of Déblai to the volume of earth that one must transport, & the name of Remblai to the space that they should occupy after the transport.

The price of the transport of one molecule being, if all the rest is equal, proportional to its weight & to the distance that one makes it covering, & hence the price of the total transport having to be proportional to the sum of the products of the molecules each multiplied by the distance covered, it follows that, the déblai & the remblai being given by figure and position, it makes difference if a certain molecule of the déblai is transported to one or to another place of the remblai, but that there is a certain distribution to make of the molcules from the first to the second, after which the sum of these products will be as little as possible, & the price of the total transport will be a minimum.

Monge describes an interesting geometric method to solve the assignment problem in this case: let $l$ be a line touching the two areas from one side; then transport the earth molecule touched in one area to the position touched in the other area. Then repeat, until all molecules are transported.

EDIT: It turns out that Monge's method is not fully correct (see Carlo Beenakker's answer below). Now I have the following follow up questions:

Under what conditions does Monge's method work or fail to work? Is it possible to characterize shapes for which Monge's method work?

$\endgroup$
1
  • $\begingroup$ It may be better known as the "mass transfer problem". $\endgroup$
    – Nik Weaver
    May 17, 2020 at 22:47

1 Answer 1

2
$\begingroup$

Schrijver explains Monge's reasoning in On the history of combinatorial optimization (till 1960):

Monge [1784] described an interesting geometric method to solve this problem. Consider a line that is tangent to both areas, and move the molecule $m$ touched in the first area to the position $x$ touched in the second area, and repeat, until all earth has been transported. Monge's argument that this would be optimum is simple: if molecule $m$ would be moved to another position, then another molecule should be moved to position $x$, implying that the two routes traversed by these molecules cross, and that therefore a shorter assignment exists.

Although geometrically intuitive, the method is however not fully correct, as noted by Appell [1928]: "It is very easy to make the figure in such a way that the routes followed by the two particles of which Monge speaks, do not cross each other."

$\endgroup$
1
  • $\begingroup$ Thanks. Now I have some follow up questions (see my edits). Does Appell's paper address these? $\endgroup$ May 18, 2020 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.