The Sequential Ordering Problem (SOP) is an optimization problem
used to model many different real applications such as production
planning, single vehicle routing problems with pick-up and
delivery constraints and transportation problems in flexible
manufacturing systems.  Ant Colony System (ACS) is a well-known
metaheuristic metaphor, and it has been successfully applied to
many combinatorial optimization problems, among which the SOP.
We present a study on the hybridization of a well-known
adaptation of the ACS method to the SOP with a Mixed Integer
Linear Programming (MILP) describing the problem, leading
therefore to a Matheuristic framework.  Different combination of
the the ACS algorithm with the MILP are considered, critically
analyzed and compared.  Computational experiments on the set of
benchmarks commonly adopted in the literature show the
effectiveness of the novel Matheuristic approaches: the first
lower bounds were produced for many instances, together with some
new best-known upper bounds. The combination of the bounds also
provided an optimality proof for many instances.