liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Subgradient optimization prior to column generation: a means for predicting optimal columns (and non-binding restrictions)
Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.ORCID iD: 0000-0003-2094-7376
Linköping University, Department of Science and Technology. Linköping University, The Institute of Technology.
2005 (English)Report (Other academic)
Abstract [en]

Many classes of combinatorial and mixed integer optimization problems are attacked with decomposition methods. One technique is to perform subgradient optimization on a Lagrangean dual problem: another is to perform column generation on a Dantzig-Wolfe problem, or equivalently, cut generation on its linear programming dual. These techniques both have advantages and disadvantages. In this paper these techniques are combined into a two-phase method, with the purpose of overcoming drawbacks of the techniques.

The two-phase method consists of a prediction phase and a solution phase. In the prediction phase, subgradient optimization is performed: subgradients found are stored and used as starting columns for the solution phase. (Optionally, non-binding restricitions can be predicted based on information from the prediction phase.) The columns found are used to construct a Dantzig/Wolfe master problem. In the solution phase, column generation is performed if needed. A solid theoretical bases for the two-phase method is presented which includes strong asymptotical results. ln practise, truncated usage must be performed: practical guidelines are given in the paper.

The two-phase method is tested on two applications: a multicommodity network flow problem and a convexified version of the traveling salesman subtour problem. Two categories of numerical experiments are presented. ln the first category, various aspects of truncated usage of the theory are illustrated. In the second category, the two-phase method is tested on a relatively large number of test problems.

An overall conclusion of our work is that the two-phase method can perform significantly better, in terms of CPU-times, compared to a (stabilized) Dantzig-Wolfe algorithm. ln general, whenever the subproblems are computationaly inexpensive, compared to the Dantzig-Wolfe master programs, the two-phase method might be an interesting alternative to use instead of pure Dantzig-Wolfe.

Place, publisher, year, edition, pages
Linköping: Linköpings universitet , 2005.
Series
LiTH-MAT-R, 77
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-29698Local ID: 15091OAI: oai:DiVA.org:liu-29698DiVA: diva2:250515
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2013-08-30
In thesis
1. Accelerating column generation schemes: applications to routing problems
Open this publication in new window or tab >>Accelerating column generation schemes: applications to routing problems
2005 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Many integer optimization problems of great practical importance are today attacked with column generation. Merits of column generation is that it enables the use of compact and flexible formulations of many complex optimization problems, and that it often gives rise to good (strong) formulations. A potential drawback with column generation is the well-known tailing-off phenomenon, that is, that the objective value is improved rapidly in early iterations but very slowly in the late iterations.

We study various techniques for accelerating column generation methods for (integer) linear programs. We evaluate the use of stabilized column generation on a Traveling Salesman Subtour Problem, TSSP, a problem which is closely related to the Prize Collecting Traveling Salesman Problem. We further study how subgradient optimization can be used with the purpose of predicting optimal columns (and, optionally, non-binding restrictions). This technique is tested on the TSSP and the multicommodity network flow problem.

Another idea evaluated in this thesis is the use of over-generation of columns in a column generation scheme for an integer programming problem, in this case a vehicle routing problem with a heterogeneous fleet of vehicles.

The thesis also includes a note on a class of relatives to the Held and Karp 1–tree problem. It is shown that two subclasses have polynomial time-complexity. Further, we note a mistake in an earlier work and provide a counter-example to the erroneous result.

Place, publisher, year, edition, pages
Linköping: Linköpings universitet, 2005. 34 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 978
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-30273 (URN)15790 (Local ID)91-85457-50-7 (ISBN)15790 (Archive number)15790 (OAI)
Public defence
2005-11-28, Glashuset, Hus B, Campus Valla, Linköping, 10:15 (Swedish)
Opponent
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2012-12-06

Open Access in DiVA

No full text

Authority records BETA

Westerlund, AndreasGöthe-Lundgren, MaudLarsson, TorbjörnYuan, Di

Search in DiVA

By author/editor
Westerlund, AndreasGöthe-Lundgren, MaudLarsson, TorbjörnYuan, Di
By organisation
Department of MathematicsThe Institute of TechnologyDepartment of Science and Technology
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 443 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf