Determinant interior point algorithm
In 2004, Borkar et al [1] presented the mathematical programming problems, (where G is a suitably perturbed fundamental matrix)
min G11
over the set of feasible doubly stochastic policies,
and showed that it was equivalent to the Hamiltonian cycle problem. It was later proved that the gap between optimal values of the above problem for a Hamiltonian graph and for a non-Hamiltonian graph of the same order is strictly positive [2]. This strengthens the potential usefulness of the optimisation model. However, in implementing an efficient algorithm, numerical difficulties arise. The first major challenge is the evaluation of the G11 functional, as the fundamental matrix is an inverse. The second major challenge is that relevant Hessian matrices, an important ingredient in many optimisation algorithms, are dense due to perturbation and consequently expensive to compute.
Looking for other functionals to determine Hamiltonicity, Ejov et al [3] proved that the determinant of the inverse of the fundamental matrix, too, is an appropriate optimisation functional. Furthermore, Ejov et al proved that the determinant objective function is more robust than the function G11, as it is maximised at Hamiltonian cycles with or without the linear symmetric perturbation required by G11.
The following result was proved in [3]. Consider P, a probability transition matrix for a given graph, containing continuous variables corresponding to the arcs in the graph. Then, if we restrict P to being doubly-stochastic – that is, P has row and column sums of 1, and contains only nonnegative values – the following optimisation problem (where I is the N × N identity matrix and J is an N × N matrix with unit entries)
det(I – P + 1/NJ)
s.t.
P is doubly-stochastic,
is bounded below by 0 and above by k, where k is the length of the longest cycle in the graph. For Hamiltonian graphs, k = N, and for non-Hamiltonian graphs, k <= N-1. Therefore there is a positive gap of at least 1 for this formulation.
Taking advantage of the inherent sparsity in difficult instances of HCP, Filar et al have developed efficient methods of computing derivatives of the objective function [4]. This method is used in an algorithm called DIPA (Determinant interior point algorithm) that seeks to solve the above formulation, detailed in Haythorpe [5,6].
PUBLICATIONS
[1] Borkar, V.S., Ejov, V. and Filar, J.A. “Directed graphs, Hamiltonicity and doubly stochastic matrices.” Random Structures and Algorithms, 25(4):376-395, 2004. Wiley Online Library
[2] Borkar, V.S., Ejov, V. and Filar, J.A. “On the Hamiltonicity gap and doubly stochastic matrices.” Random Structures and Algorithms, 34(4):502-519, 2009. Wiley Online Library
[3] Ejov, V., Filar, J.A., Murray, W. and Nguyen, G.T. “Determinants and longest cycles of graphs”. SIAM Journal on Discrete Mathematics, 22(3):1215-1225, 2008. SIAM
[4] Filar, J.A., Haythorpe, M. and Murray, W. “On the Determinant and its Derivatives of the Rank-one corrected Generator of a Markov Chain on a Graph.” Journal of Global Optimization, to appear. SpringerLink
[5] Haythorpe, M. “Markov Chain based algorithms for the Hamiltonian cycle problem.” PhD thesis, University of South Australia, 2010. Systems Optimization Laboratory
[6] Haythorpe, M. “Finding Hamiltonian cycles using an interior point method.” Australian Mathematics Society Gazette, 37:170-179, 2010. PDF available