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.
Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
