2
$\begingroup$

I am looking for software (open-source or otherwise) or an implementable algorithm for solving a continuous transportation problem. The input consists of a pointset in a planar rectangle, and we need to relocate these points within the rectangle to decrease the peak density below a given threshold (feasibility can be assumed), while minimizing total displacement.

The distances inside the rectangle are Manhattan/taxicab, although efficient solutions for the Euclidean distance can also be helpful. Total displacement is interpreted in the $L_1$ sense, but efficient solutions for the $L_2$ case can also be helpful. The peak density can be evaluated with respect to a uniform grid (is there another practical way ?)

My students implemented a geometric algorithm (without having any background in transportation) that works great in our application, but we don't know how far the results are from optimal. Just in case, our application also imposes rectangular "exclusion zones", where no points can be placed (more generally, we can assume a "bounding probability distribution").

Improve this question
$\endgroup$
2
  • $\begingroup$ Have you tried it on examples where you know what the optimal placement is? Gerhard "Ask Me About System Design" Paseman, 2012.02.04 $\endgroup$
    – Gerhard Paseman
    Commented Feb 5, 2012 at 5:07
  • $\begingroup$ Yes, and it is suboptimal. Recall that 1D transportation has a simple/closed-form solution, implemented for a pointset input by sorting. In 2D, we alternate optimal transportation in X,Y directions, position cutlines at median locations, then recursively divide and conquer. Now consider a pointset distributed normally in 2D. The 1D solution can be applied radially, but our algorithm produces something blocky. A more important question for us is how the suboptimality affects our application (which can "transport" millions of points 40-50 times per run)- this is difficult to answer w/o a solver $\endgroup$
    – Igor Markov
    Commented Feb 6, 2012 at 8:15

3 Answers 3

Reset to default
2
$\begingroup$

How much have you looked into the theory of optimal transport? It's very popular for image warping/registration.

There's codes available to compute the $l1$-optimal transport distance (also referred to as "Earth mover's distance") here: http://ai.stanford.edu/~rubner/emd/default.htm and here: http://www.cs.huji.ac.il/~ofirpele/FastEMD/code/

The $l2$ optimal mass transport problem is quite difficult but can be solved: http://www.springerlink.com/index/40PGJBKDC9V0UH94.pdf

Once it's possible to compute the cost to get between two distributions of points I guess you'll have to optimize to see which distribution is closest to the one you have. Maybe something like: $$ \min_\rho d(\rho_0, \rho)\;subject\;to\;\rho \leq c, \rho \geq 0,\int \rho = 1 $$ where $\rho$ is a probability distribution describing the density of points and $c$ is your threshold. Maybe you can do this with a Lagrange multiplier and gradient descent?

Improve this answer
$\endgroup$
4
  • $\begingroup$ Looking into it very closely now. While we are now leaning toward $l_2$-optimal transport because it tends to preserve the relative ordering of "the grains of sand" being transported. Also, the uniqueness of $l_2$-optimal solutions is useful. But we'll definitely take a look at the software you suggested. $\endgroup$
    – Igor Markov
    Commented Mar 30, 2012 at 21:36
  • $\begingroup$ Sure. The book by Villani (who got a fields medal last time around) "Topics in Optimal Transportation" has more information in this field than I can give you. $\endgroup$
    – dranxo
    Commented Mar 30, 2012 at 22:36
  • $\begingroup$ The link to springerlink.com is broken. I'm also unable to find any copy saved on the Wayback Machine. $\endgroup$
    – The Amplitwist
    Commented Apr 17, 2023 at 22:51
  • $\begingroup$ The link to cs.huji.ac.il also seems to be broken, but a snapshot is saved on the Wayback Machine. $\endgroup$
    – The Amplitwist
    Commented Apr 17, 2023 at 22:51
0
$\begingroup$

You can use the code packages rcompton mentioned to compute transportation with any kind of cost function (called also ground distance). If you have "exclusion zones" you can just set the cost there to be a very high number there (you can for example, compute a solution that is not optimal and set it as a cost). If you have many edges with this maximum distance, it also has the advantage of this code running faster: http://www.cs.huji.ac.il/~ofirpele/FastEMD/code/

Improve this answer
$\endgroup$
1
  • $\begingroup$ The link to cs.huji.ac.il seems to be broken, but a snapshot is saved on the Wayback Machine. $\endgroup$
    – The Amplitwist
    Commented Apr 17, 2023 at 22:52
0
$\begingroup$

I need to solve a similar problem for VLSI global placement and legalization - we probably have the same goal.

I had very good results with recursive partitioning with local improvements: I divide the placement region and the pointset by bipartitioning, which can be done optimally if you allow fractional allocations, then improve the placement between nearby regions until the region size is small enough.

You need to be careful to optimize between diagonally adjacent regions, but with a few trial-and-error steps it is the best algorithm I found for very large pointsets.

For local optimization you may use this algorithm (or here) to solve the transportation problem optimally for a few regions. My implementation is usually an order of magnitude slower than bipartitioning for similar results, but it may yield slightly better solutions (and it gives some confidence in the result).

Last, but not least, the last level of optimization in my algorithm spreads the points independently on each coordinate within a region.

I hope it will be of some help to someone implementing VLSI placement algorithms.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .