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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.