Dynamic Bundle Methods: Application to Combinatorial Optimization

Abstract

Lagrangian relaxation is a popular technique to solve difficult optimization problems. However, the applicability of this technique depends on having a relatively low number of hard constraints to dualize. When there are exponentially many hard constraints, it is preferable to relax them dynamically, according to some rule depending on which multipliers are active. For instance, only the most violated constraints at a given iteration could be dualized. From the dual point of view, this approach yields multipliers with varying dimensions and a dual objective function that changes along iterations. We discuss how to apply a bundle methodology to solve this kind of dual problems. We analyze the convergence properties of the resulting dynamic bundle method, including finite convergence for polyhedral problems, and report numerical experience on Linear Ordering and Traveling Salesman Problems