Automation and combination of linear-programming based stabilization techniques in column generation
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | PESSOA, Artur Alves | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | SADYKOV, Ruslan | |
| hal.structure.identifier | Universidade Federal Fluminense [Rio de Janeiro] [UFF] | |
| dc.contributor.author | UCHOA, Eduardo | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | VANDERBECK, François | |
| dc.date.accessioned | 2024-04-04T03:10:09Z | |
| dc.date.available | 2024-04-04T03:10:09Z | |
| dc.date.created | 2017-07-09 | |
| dc.date.issued | 2018 | |
| dc.identifier.issn | 1091-9856 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193665 | |
| dc.description.abstractEn | The convergence of a column generation algorithm can be improved in practice by using stabilization techniques. Smoothing and proximal methods based on penalizing the deviation from the incumbent dual solution have become standards of the domain. Interpreting column generation as cutting plane strategies in the dual problem, we analyze the mechanisms on which stabilization relies. In particular, the link is established between smoothing and in-out separation strategies to derive generic convergence properties. For penalty function methods as well as for smoothing, we describe proposals for parameter self-adjusting schemes. Such schemes make initial parameter tuning less of an issue as corrections are made dynamically. Such adjustments also allow to adapt the parameters to the phase of the algorithm. We provide extensive test reports that validate our self-adjusting parameter scheme and highlight their performances. Our results also show that using smoothing in combination with penalty function yields a cumulative effect on convergence speed-ups. | |
| dc.language.iso | en | |
| dc.publisher | Institute for Operations Research and the Management Sciences (INFORMS) | |
| dc.subject.en | Stabilization | |
| dc.subject.en | Cutting Plane Separation | |
| dc.subject.en | Column Generation | |
| dc.title.en | Automation and combination of linear-programming based stabilization techniques in column generation | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1287/ijoc.2017.0784 | |
| dc.subject.hal | Mathématiques [math]/Optimisation et contrôle [math.OC] | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.journal | INFORMS Journal on Computing | |
| bordeaux.page | 339-360 | |
| bordeaux.volume | 30 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 2 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-01077984 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01077984v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=INFORMS%20Journal%20on%20Computing&rft.date=2018&rft.volume=30&rft.issue=2&rft.spage=339-360&rft.epage=339-360&rft.eissn=1091-9856&rft.issn=1091-9856&rft.au=PESSOA,%20Artur%20Alves&SADYKOV,%20Ruslan&UCHOA,%20Eduardo&VANDERBECK,%20Fran%C3%A7ois&rft.genre=article |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||