matsen/pplacer — Issue #203: Maximum WPD for a collection of placement locations
Author: cmccoy
Created: 2012-01-05 21:03:07+00:00
State: open

Compute the maximum WPD for a collection of placement locations

#### Define

Let `P` = the set of placements on the tree

Let `I` = the points that form the convex hull of `P`

Let `p_i` = the proportion of total mass at point `i`

Let `E` = the set of edges connecting `I`

Let `D_e` = the subset of `I` distal to edge `e`

Let `x_e = 1 - 2\sum_{i \in D_e} p_i`, for edge `e`, so `|x_e|` is
one minus the proportion of mass on the side with least mass.

Let `l_e` = length of edge `e`

#

We want to minimize:

`z = \sum_e l_e |x_e|`

Subject to:

* `p_i \ge 0` (no negative mass)
* `\sum_i p_i = 1` (mass proportions sum to 1)

#### Linear Conversion

To convert this to a linear program, replace:

* `x_e = xp_e - xn_e`
* `|x_e| = xp_e + xn_e`

subject to `xp_e,xn_e >= 0` (see [AIIMS linear programming tricks](http://www.aimms.com/aimms/download/manuals/aimms3om_linearprogrammingtricks.pdf))

The problem becomes:

Minimize:

`z = \sum_e l_e (xp_e + xn_e)`

Subject to:

* `p_i >= 0` for all `i` (no negative mass)
* `\sum_{i \in i} p_i = 1` (mass proportions sum to 1)
* `1 - 2\sum_{i \in D_e} p_i = xp_e - xn_e` for all `e`
* `xp_e,xn_e >= 0` for all `e`