Dynamic Bundle Methods: Application to Combinatorial Optimization
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 dynamical...
| Main Authors: | , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5538 |
| _version_ | 1826214755805691904 |
|---|---|
| author | Belloni, Alexandre Sagastizabal, Claudia |
| author_facet | Belloni, Alexandre Sagastizabal, Claudia |
| author_sort | Belloni, Alexandre |
| collection | MIT |
| description | 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 |
| first_indexed | 2024-09-23T16:10:39Z |
| format | Working Paper |
| id | mit-1721.1/5538 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:10:39Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/55382019-04-11T09:10:31Z Dynamic Bundle Methods: Application to Combinatorial Optimization Belloni, Alexandre Sagastizabal, Claudia 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 2004-09-10T19:48:34Z 2004-09-10T19:48:34Z 2004-06 Working Paper http://hdl.handle.net/1721.1/5538 en_US Operations Research Center Working Paper Series;OR 370-04 309629 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Belloni, Alexandre Sagastizabal, Claudia Dynamic Bundle Methods: Application to Combinatorial Optimization |
| title | Dynamic Bundle Methods: Application to Combinatorial Optimization |
| title_full | Dynamic Bundle Methods: Application to Combinatorial Optimization |
| title_fullStr | Dynamic Bundle Methods: Application to Combinatorial Optimization |
| title_full_unstemmed | Dynamic Bundle Methods: Application to Combinatorial Optimization |
| title_short | Dynamic Bundle Methods: Application to Combinatorial Optimization |
| title_sort | dynamic bundle methods application to combinatorial optimization |
| url | http://hdl.handle.net/1721.1/5538 |
| work_keys_str_mv | AT bellonialexandre dynamicbundlemethodsapplicationtocombinatorialoptimization AT sagastizabalclaudia dynamicbundlemethodsapplicationtocombinatorialoptimization |