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

Section

Articles