### Pedro Munari (University of São Paulo, Brazil)

#### Further developments in the primal-dual column generation technique

*Wednesday 27 October 2010 at 15.30, JCMB 6206*

##### Abstract

The column generation technique is an essential tool in the context of integer
programming. This technique consists in an iterative method applied to solve a
linear programming problem with columns of its coefficient matrix generated by
following a known rule. In the context of integer programming, the linear
programming problems usually arise when a decomposition or relaxation
technique is applied to the original integer programming problem. The
classical column generation is based on optimal solutions, which usually
present an unstable behaviour and may require an unnecessarily large number of
iterations. To overcome this, variations of the classical approach avoid
optimal solutions. This is the case in the primal-dual column generation
technique, which relies in well-centred suboptimal solutions found by a
primal-dual interior point method. In this talk, I will review the main
aspects of different column generation approaches and present new theoretical
developments concerning the primal-dual technique. Also, computational results
for three different classes of applications of integer programming will be
presented. They show that the primal-dual technique usually leads to a
substantial reduction in both number of iterations and running time when
compared to other approaches.

### 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*