Solutions diversification in a column generation algorithm

Authors

  • Nora Touati Moungla LIPN
  • L. Létocart Université Paris
  • A. Nagih Université Paris

Keywords:

column generation, diversification, stabilization, cutting stock problem, vehicle routing problem with time windows.

Abstract

Column generation algorithms have been specially designed for solving mathematical programs with a huge number of variables. Unfortunately, this method suffers from slow convergence that limits its efficiency and usability. Several accelerating approaches are proposed in the literature such as stabilization-based techniques. A more classical approach, known as ``intensification'', consists in inserting a set of columns instead of only the best one. Unfortunately, this intensification typically overloads the master problem, and generates a huge number of useless variables. This article covers some characteristics of the generated columns from theoretical and experimental points of view. Two selection criteria are compared. The first one is based on column reduced cost and the second on column structure. We conclude our study with computational experiments on two kinds of problems: the acyclic vehicle routing problem with time windows and the one-dimensional cutting stock problem.

Author Biography

Nora Touati Moungla, LIPN

Laboratoire d'informatique de Paris Nord, 99 avenue Jean Baptiste Clement, 93430, Villetaneuse, France

Downloads

Published

2010-12-02

How to Cite

Touati Moungla, N., Létocart, L., & Nagih, A. (2010). Solutions diversification in a column generation algorithm. Algorithmic Operations Research, 5(2), Pages 86 – 95. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/12487

Issue

Vol. 5 No. 2 (2010)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.