| |
|
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: |
|
| 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>
|
|
