next up previous
Next: Embedded Solver Up: NTP Algorithms Previous: Greedy Solver

Multicommodity Solver

A second version of our Lego structure simulator incorporated a state-of-the-art multicommodity algorithm, by Castro and Nabona [18]. A special case of Linear Programming, these solvers have exponential order in the worst case, although with some luck they are faster on practical cases. We found this algorithm to be slower than the greedy version by a factor of 10 or more. The gain in accuracy did not compensate the loss in speed.



Pablo Funes
2001-05-08