MOPTA 2005
Volume Algorithm (VOL)
¡A subgradient method that produces approximate primal as well as dual solutions
lScales exceptionally well on large problems with combinatorial structure
lPrimal solution comes from estimating the volumes below the faces of the dual problem.
lSmall infeasibilities in the primal vector are negligible in many practical settings.
lThe original subgradient algorithm produces only dual solutions.
¡
¡Francisco Barahona, Project Manager
¡
¡
- The Volume Algorithm has been very effective at producing approximate solutions to large
linear programs coming from large combinatorial problems.
- What is unique is that it is extremely easy to implement and use.
- A search in Google Scholar found 64 articles that cite the VA. This is relatively high for an article published in 2000.
- There are groups in Italy, Portugal, UK, US, Brazil that have used the VA.
- At IBM the VA was used for (1) set partition problems coming from airlines optimization and (2) later for
the Boston Coach project.