On due-date based valid cuts for the sequential ordering problem

The Sequential Ordering Problem with precedence relationships was introduced in Escudero, and extended to cover release and due dates in Escudero and Schiomachen. The problem consists of finding a minimum weight Hamiltonian path on a directed graph with weights on the nodes and the arcs, satisfying precedence relationships among the nodes and lower and upper bounds on the Hamiltonian subpaths. In this paper we introduce valid cuts derived from the due date constraints that can be used in a separation framework for the dual (Lagrangian based) relaxation of the problem. We also provide an heuristic separation algorithm to obtain those cuts.