In a recent work, we identified and characterized a general class of linear programming (LP) problems–known as problems with column-dependent-rows (CDR-problems). These LPs feature two sets of constraints with mutually exclusive groups of variables in addition to a set of structural linking constraints, in which variables from both groups appear together. In a typical CDR-problem, the number of linking constraints grows very quickly with the number of variables so that to solve these problems, we need to be able to generate both columns and rows on-the-fly within an efficient solution approach. We characterized the underlying assumptions for the proposed column-and-row generation algorithm and introduce in detail a set of pricing subproblems, which are used within the proposed column-and-row generation algorithm. In a series of papers that follows, we have tackled several problems with column-dependent-rows, such as multi-stage cutting stock, robust airline crew pairing, time-constrained routing and robust vehicle scheduling, and developed novel simultaneous column-and-row generation algorithms to solve them. Moreover, we exposed the decomposable structure of CDR-problems via Benders decomposition. However, this approach brings on its own theoretical challenges. We designed a novel integration of Benders cut generation and the simultaneous generation of columns and constraints that yields a brand-new algorithm for solving large-scale CDR-problems. In this seminar, I will introduce the general problems with column-dependent-rows along with several examples, and demonstrate various applications of simultaneous column-and-row generation to handle these large-scale LP problems.
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
