# Dr. Stefan Irnich

RWTH - Aachen

April 07, 2008, 14:15, Room MA A3 30 (click here for the map)

## A new hybrid exact algorithm for the TSPTW

The fixing of variables based on reduced costs is one of the standard
acceleration techniques in mixed integer programming (MIP) that has been
used in numerous applications: If the reduced cost of an integer variable
exceeds the duality gap, the variable can be fixed to zero. An extension of
this idea is to consider reduced costs of several decision variables
simultaneously: Any solution to a MIP, where the sum of the reduced costs
of some integer variables exceeds the duality gap, is necessarily a
non-optimal solution. We exploit this idea and show that hybrid exact
algorithms with two phases can benefit from this general result. The first
phase is the computation of a dual feasible solution to some (strong)
relaxation of the problem. For a minimization problem, the dual solution
provides a lower bound and reduced costs of the variables. Any upper bound
then permits the traditional variable fixing for the individual variables.
The second phase is a direct, enumerative decision-tree approach. The
additivity of the reduced costs allows bounding the decision-tree algorithm
whenever too many decision variables with positive reduced costs have been
included in a (partial) solution. In order to empirically test the
effectiveness of the new idea, we have developed a hybrid exact approach for
the traveling salesman problem with time windows (TSPTW). Its first phase
is a cutting-plane algorithm and the second phase a dynamic-programming
algorithm. The new hybrid approach clearly and consistently outperforms the
currently best methods at hand.