Cole Smith (University of Florida, USA)

Variable expansion and hybrid optimization techniques for solving bi-level problems
Wednesday 28 April 2010 at 15.30, JCMB 6206


Bi-level optimization algorithms such as Benders decomposition have been developed for use in a variety of settings, particularly those involving multiple decision-makers and/or stochasticity. These algorithms divide the decision-making process into two stages: a first-stage master problem that controls certain "linking variable" values, and a second-stage problem (or often, set of problems) that uses the linking variable values as inputs. The second-stage problems provide feedback to the first-stage problems by establishing relationships regarding the impact of changing linking variable values on the second-stage objective function value.

This talk will describe two investigations in which standard bi-level approaches are not practically useful, and where methodological innovation is necessary to solve the problems within reasonable computational limits. First, we consider the creation of additional linking master problem variables that represent nonlinear relationships among the original variables, and show that cutting planes generated in this expanded variable space can be substantially tighter than those in the original variable space. In particular, for both applications discussed in this talk, we show that whereas an exponential number of nondominated cutting planes can be generated at some stage of a bi-level algorithm in the original variable space, a single inequality in the (polynomially) expanded variable space can imply all of these exponentially many cutting planes.

Using this concept, we demonstrate a substantial computational time reduction in solving a three-stage competitive product introduction problem, and modest computational improvements in solving a stochastic telecommunication network design problem. For the latter problem, we analyze reasons why even the improved algorithm fails to converge quickly, and address these problems by prescribing a hybrid integer programming/constraint programming algorithm that substantially outperforms pure mathematical programming approaches. The talk will conclude by providing general guidelines on when each of these new approaches should be considered when solving difficult bi-level optimization problems.

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