| dc.creator |
Belloni, Alexandre |
|
| dc.creator |
Sagastizabal, Claudia |
|
| dc.date |
2004-09-10T19:48:34Z |
|
| dc.date |
2004-09-10T19:48:34Z |
|
| dc.date |
2004-06 |
|
| dc.date.accessioned |
2013-10-09T02:39:56Z |
|
| dc.date.available |
2013-10-09T02:39:56Z |
|
| dc.date.issued |
2013-10-09 |
|
| dc.identifier |
http://hdl.handle.net/1721.1/5538 |
|
| dc.identifier.uri |
http://koha.mediu.edu.my:8181/xmlui/handle/1721 |
|
| dc.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 |
|
| dc.format |
309629 bytes |
|
| dc.format |
application/pdf |
|
| dc.language |
en_US |
|
| dc.publisher |
Massachusetts Institute of Technology, Operations Research Center |
|
| dc.relation |
Operations Research Center Working Paper Series;OR 370-04 |
|
| dc.title |
Dynamic Bundle Methods: Application to Combinatorial Optimization |
|
| dc.type |
Working Paper |
|