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
Accelerating column generation schemes: applications to routing problems
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
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: urn:nbn:se:liu:diva-30273Local ID: 15790ISBN: 91-85457-50-7 (print)OAI: oai:DiVA.org:liu-30273DiVA: diva2:251095
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
List of papers
1. A stabilized column generation scheme for the traveling salesman subtour problem
Open this publication in new window or tab >>A stabilized column generation scheme for the traveling salesman subtour problem
2006 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 154, no 15, 2212-2238 p.Article in journal (Refereed) Published
Abstract [en]

Given an undirected graph with edge costs and both revenues and weights on the vertices, the traveling salesman subtour problem is to find a subtour that includes a depot vertex, satisfies a knapsack constraint on the vertex weights, and that minimizes edge costs minus vertex revenues along the subtour.

We propose a decomposition scheme for this problem. It is inspired by the classic side-constrained 1-tree formulation of the traveling salesman problem, and uses stabilized column generation for the solution of the linear programming relaxation. Further, this decomposition procedure is combined with the addition of variable upper bound (VUB) constraints, which improves the linear programming bound. Furthermore, we present a heuristic procedure for finding feasible subtours from solutions to the column generation problems. An extensive experimental analysis of the behavior of the computational scheme is presented.

National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-36277 (URN)10.1016/j.dam.2005.04.012 (DOI)30825 (Local ID)30825 (Archive number)30825 (OAI)
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2017-12-13
2. A note on relatives to the Held and Karp 1-tree problem
Open this publication in new window or tab >>A note on relatives to the Held and Karp 1-tree problem
2006 (English)In: Operations Research Letters, ISSN 0167-6377, E-ISSN 1872-7468, Vol. 34, no 3, 275-282 p.Article in journal (Refereed) Published
Abstract [en]

We study a class of graph problems which includes as special cases the Held and Karp 1-tree problem, and the minimum spanning tree problem with one degree constraint studied by Glover and Klingman. For another special case, we note a mistake in a paper by Ramesh, Yoon and Karwan.

National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-36273 (URN)10.1016/j.orl.2005.04.010 (DOI)30783 (Local ID)30783 (Archive number)30783 (OAI)
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2017-12-13
3. Subgradient optimization prior to column generation: a means for predicting optimal columns (and non-binding restrictions)
Open this publication in new window or tab >>Subgradient optimization prior to column generation: a means for predicting optimal columns (and non-binding restrictions)
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:nbn:se:liu:diva-29698 (URN)15091 (Local ID)15091 (Archive number)15091 (OAI)
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2013-08-30
4. A column generation scheme for the fixed fleet heterogeneous vehicle routing problem
Open this publication in new window or tab >>A column generation scheme for the fixed fleet heterogeneous vehicle routing problem
2005 (English)Report (Other academic)
Abstract [en]

We present an optimizing column generation procedure for solving the vehicle routing problem with a fixed heterogeneous fleet of vehicles; if the method is used in a truncated fashion it turns into a heuristic. The method is based on a new mathematical formulation, which includes a new type of valid inequalities, strengthened by the use of Chvátal-Gomory rounding, and a Lagrangian dualization of this formulation. The dual problem is attacked by subgradient optimization and a near-optimal dual solution obtained is used for enumerating routes that are promising candidates for being used in an optimal solution. These routes are collected in a set partitioning problem, which is finally solved, and an upper bound to the optimal objective value is obtained. The method is evaluated on a set of small-scale test instances. The valid inequalities improves the lower bound significantly: the improvement depends on the ratio between total customer demand and total vehicle capacity. The qualities of the upper bounds varies quite much among the instances.

Place, publisher, year, edition, pages
Linköping: Linköpings universitet, 2005
Series
LiTH-MAT-R, 12
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-29699 (URN)15092 (Local ID)15092 (Archive number)15092 (OAI)
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2013-08-30

Open Access in DiVA

No full text

Authority records BETA

Westerlund, Andreas

Search in DiVA

By author/editor
Westerlund, Andreas
By organisation
Optimization The Institute of Technology
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 417 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