The set partitioning problem is a fundamental model for many important real-life transportation problems, including airline crew and bus driver scheduling and vehicle routing. In this paper we propose a new dual heuristic and an exact method for the set partitioning problem. The dual heuristic combines Lagrangean relaxation and column generation and uses subgradient optimization to find an effective dual solution of the linear relaxation of the set partitioning problem. This procedure is faster than traditional simplex based methods, moreover, we show that the lower bound achieved dominates the bound obtained by the classic Lagrangean relaxation of the set partitioning constraints. The exact method iteratively solves a sequence of reduced set partitioning problems using a general purpose integer programming solver. Our computational results indicate that the new bounding procedure is fast and produces very good dual solutions. Moreover, the exact method is easy to implement and it is competitive with the best branch and cut algorithms.

M.A. Boschetti, A. Mingozzi, S. Ricciardelli (2004). Solving the set partitioning problem using Lagrangean relaxation and column generation. RHODES : s.n.

Solving the set partitioning problem using Lagrangean relaxation and column generation

BOSCHETTI, MARCO ANTONIO;MINGOZZI, ARISTIDE;
2004

Abstract

The set partitioning problem is a fundamental model for many important real-life transportation problems, including airline crew and bus driver scheduling and vehicle routing. In this paper we propose a new dual heuristic and an exact method for the set partitioning problem. The dual heuristic combines Lagrangean relaxation and column generation and uses subgradient optimization to find an effective dual solution of the linear relaxation of the set partitioning problem. This procedure is faster than traditional simplex based methods, moreover, we show that the lower bound achieved dominates the bound obtained by the classic Lagrangean relaxation of the set partitioning constraints. The exact method iteratively solves a sequence of reduced set partitioning problems using a general purpose integer programming solver. Our computational results indicate that the new bounding procedure is fast and produces very good dual solutions. Moreover, the exact method is easy to implement and it is competitive with the best branch and cut algorithms.
2004
EURO XX - OR and the Management of Electronic Services
114
114
M.A. Boschetti, A. Mingozzi, S. Ricciardelli (2004). Solving the set partitioning problem using Lagrangean relaxation and column generation. RHODES : s.n.
M.A. Boschetti; A. Mingozzi; S. Ricciardelli
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/41536
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact