The setpartitioningproblem 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 dualascent heuristic and an exact method for the setpartitioningproblem. The dualascent heuristic finds an effective dual solution of the linear relaxation of the setpartitioningproblem and it is faster than traditional simplex based methods. Moreover, we show that the lower bound achieved dominates the one achieved by the classic Lagrangean relaxation of the set partitioning constraints. We describe a simple exact method that uses the dual solution to define a sequence of reduced setpartitioningproblems that are solved by 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 proposed is easy to implement and it is competitive with the best branch and cut algorithms published in the literature so far.

Boschetti, M., Mingozzi, A., Ricciardelli, S. (2008). A dual ascent procedure for the set partitioning problem. DISCRETE OPTIMIZATION, 5(4), 735-747 [10.1016/j.disopt.2008.06.001].

A dual ascent procedure for the set partitioning problem

RICCIARDELLI, SALVATORE
2008-01-01

Abstract

The setpartitioningproblem 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 dualascent heuristic and an exact method for the setpartitioningproblem. The dualascent heuristic finds an effective dual solution of the linear relaxation of the setpartitioningproblem and it is faster than traditional simplex based methods. Moreover, we show that the lower bound achieved dominates the one achieved by the classic Lagrangean relaxation of the set partitioning constraints. We describe a simple exact method that uses the dual solution to define a sequence of reduced setpartitioningproblems that are solved by 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 proposed is easy to implement and it is competitive with the best branch and cut algorithms published in the literature so far.
2008
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore MAT/09 - RICERCA OPERATIVA
English
Con Impact Factor ISI
dual heuristics; Lagrangean relaxation; large scale set partitioning; linear programming; subgradient optimization
Boschetti, M., Mingozzi, A., Ricciardelli, S. (2008). A dual ascent procedure for the set partitioning problem. DISCRETE OPTIMIZATION, 5(4), 735-747 [10.1016/j.disopt.2008.06.001].
Boschetti, M; Mingozzi, A; Ricciardelli, S
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/2108/35728
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 19
social impact