Wedged-MIP heuristic
In the branch-and-fix method, one of the fathoming techniques involves the checking, at each iteration, whether a certain bound can still be satisfied. In Haythorpe [1] additional constraints, called Wedge constraints, were added to this bound check that greatly improved the performance of the branch-and-fix method. Motivated by this result, the Wedged-MIP heuristic was developed.
The Wedged-MIP heuristic is a mixed integer programming feasibility problem which can only be satisfied by solutions corresponding to Hamiltonian cycles. If a graph is non-Hamiltonian, the formulation is infeasible. The Wedged-MIP heuristic was implemented in IBM ILOG OPL-CPLEX 5.1. In the implementation, the input variables are continuous, and all sets of constraints except for one are linear constraints. Only the final set of constraints is nonlinear, which takes the form of complementarity constraints. OPL-CPLEX then interprets these constraints in such a way that they can be submitted to the CP Optimizer, creating new integer and binary variables and leaving only linear constraints in these new variables.
In addition to the complentarity constraints, the constraints used in the branch-and-fix method, simple constraints preventing the formation of 2-cycles and 3-cycles, and the Wedge constraints from the branch-and-fix method are used. The combination of constraints enables OPL-CPLEX to solve some large graphs in reasonable time. For example, the 1000-vertex graph from the TSPLIB website was solved in 30 minutes, and the 2000-vertex graph was solved in 10 hours.
PUBLICATIONS
[1] Haythorpe, M. “Markov Chain based algorithms for the Hamiltonian cycle problem.” University of South Australia, 2010. Systems Optimization Laboratory