Non-differentiable Optimization of Lagrangian Dual Formulations of Linear Programs with Recovery of Primal Solutions
 
 
Description:  We consider the solution of Lagrangian dual formulations of linear programs and examine various non-differentiable optimization techniques for obtaining both dual and primal solutions. The motivation for this study is that, for example, in the context of solving mixed-integer programs via LP-based branch-and-cut methods, one is confronted with the solution of a large number of lower bounding and separation linear programs at the different nodes of the enumeration tree. Often, these LPs are ill-conditioned, higher dimensional reformulations for which both simplex and interior point solvers can be too time-consuming. On the other hand, Lagrangian dual mechanisms can be effectively used to derive quick bounds/cuts in such contexts. We examine different deflected subgradient-based direction-finding and step length strategies in concert with new trust-region Variable Target Value methods to solve such Lagrangian dual formulations. Certain pre- and post-processing techniques are also discussed to refine the quality of the dual and primal solutions derived. Extensive computational results reveal that this approach can produce near-optimal solutions while consuming about 3.19% of the time taken by the software package CPLEX to obtain comparable quality solutions.
Area(s):
Date:  2005-04-29
Start Time:   14:00
Speaker:  Hanif D. Sherali (Virginia Tech, Department of Industrial and Systems Engineering)
Place:  Room Pedro Nunes
Research Groups: -Numerical Analysis and Optimization
See more:   <Main>  
 
© Centre for Mathematics, University of Coimbra, funded by
Science and Technology Foundation
Powered by: rdOnWeb v1.4 | technical support