Antonio Frangioni (University of Pisa, Italy)

Large (un)structured master problems in decomposition algorithms and interior-point methods: friend or foe?
Thursday 5 Febrary 2015 at 13.00, JCMB 4325A

Abstract

Using multicommodity flow/network design problems as motivating examples, we review some (more or less recent) developments in decomposition approaches for large-scale structured optimization which lead to the notion that "the master problem has to be large" for convergence to occur quickly. Besides, for optimal performances the structure of the master problem may have to be significantly different from the ones employed in by-the-book implementations, requiring the use of general-purpose solvers (or the development of approaches capable of "exploiting the structure of an unstructured problem"). This highlights the importance of correctly choosing within the trade-off between master problem size, and therefore computational cost, and the number of iterations required to attain convergence (which, in turn, has an effect on the average size of all the master problems solved). Which solution approach is employed to solve the master problems is clearly very relevant in this context. Interior-point methods may on one hand be promising candidates due to several aspects (capability of exploiting different forms of structure in the coefficient matrix, resilience to the introduction of nonlinear terms, good influence on the quality of the generated dual solutions, outright computational efficiency, ...), but on the other hand may be challenged by the need of performing more complex reoptimizations than in the case of more standard master problems. The seminar offers no answers to these issues, just hopes to rise the right questions in front of the right audience.

Seminars by year

Current 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996