RWTH - Aachen
April 07, 2008, 14:15, Room MA A3 30 (click here for the map)
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.