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

##### Abstract

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*