Serguei Rossomakhine
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Serguei Rossomakhine has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
- Michael Haythorpe
Flinders University, Adelaide, Australia
8 shared publications - Jerzy A. Filar
The University of Queensland
6 shared publications - Vladimir Ejov
Flinders University
6 shared publications - Vladimir Gaitsgory
Department of Mathematics and Statistics Macquarie University Eastern Road 2113 Macquarie Park NSW Australia
5 shared publications - Pouya Baniasadi
Flinders University
3 shared publications - John F. Roddick
Flinders University
2 shared publications
Latest Publications
- Open Access
A Note on Using the Resistance-Distance Matrix to solve Hamiltonian Cycle Problem
An instance of Hamiltonian cycle problem can be solved by converting it to an instance of Travelling salesman problem, assigning any choice of weights to edges of the underlying graph. In this note we demonstrate that, for difficult instances, choosing the edge weights to be the resistance distance between its two incident vertices is often a good choice. We also demonstrate that arguably stronger performance arises from using the inverse of the resistance distance. Examples are provided demonstrating benefits gained from these choices.
Open AccessA Note on Using the Resistance-Distance Matrix to solve Hamiltonian Cycle Problem
An instance of Hamiltonian cycle problem can be solved by converting it to an instance of Travelling salesman problem, assigning any choice of weights to edges of the underlying graph. In this note we demonstrate that, for difficult instances, choosing the edge weights to be the resistance distance between its two incident vertices is often a good choice. We also demonstrate that arguably stronger performance arises from using the inverse of the resistance distance. Examples are provided demonstrating benefits gained from these choices.
- Open Access
A New Heuristic for Detecting Non-Hamiltonicity in Cubic Graphs
We analyse a polyhedron which contains the convex hull of all Hamiltonian cycles of a given undirected connected cubic graph. Our constructed polyhedron is defined by polynomially-many linear constraints in polynomially-many continuous (relaxed) variables. Clearly, the emptiness of the constructed polyhedron implies that the graph is non-Hamiltonian. However, whenever a constructed polyhedron is non-empty, the result is inconclusive. Hence, the following natural question arises: if we assume that a non-empty polyhedron implies Hamiltonicity, how frequently is this diagnosis incorrect? We prove that, in the case of bridge graphs, the constructed polyhedron is always empty. We also demonstrate that some non-bridge non-Hamiltonian cubic graphs induce empty polyhedra as well. We compare our approach to the famous Dantzig-Fulkerson-Johnson relaxation of a TSP, and give empirical evidence which suggests that the latter is infeasible if and only if our constructed polyhedron is also empty. By considering special edge cut sets which are present in most cubic graphs, we describe a heuristic approach, built on our constructed polyhedron, for which incorrect diagnoses of non-Hamiltonian graphs as Hamiltonian appear to be very rare. In particular, for cubic graphs containing up to 18 vertices, only four out of 45,982 undirected connected cubic graphs were so misdiagnosed. By constrast, we demonstrate that an equivalent heuristic, when built on the Dantzig-Fulkerson-Johnson relaxation of a TSP, is mostly unsuccessful in identifying additional non-Hamiltonian graphs. These empirical results suggest that polynomial algorithms based on our constructed polyhedron may be able to correctly identify Hamiltonicity of a cubic graph in all but rare cases.
Open AccessA New Heuristic for Detecting Non-Hamiltonicity in Cubic Graphs
We analyse a polyhedron which contains the convex hull of all Hamiltonian cycles of a given undirected connected cubic graph. Our constructed polyhedron is defined by polynomially-many linear constraints in polynomially-many continuous (relaxed) variables. Clearly, the emptiness of the constructed polyhedron implies that the graph is non-Hamiltonian. However, whenever a constructed polyhedron is non-empty, the result is inconclusive. Hence, the following natural question arises: if we assume that a non-empty polyhedron implies Hamiltonicity, how frequently is this diagnosis incorrect? We prove that, in the case of bridge graphs, the constructed polyhedron is always empty. We also demonstrate that some non-bridge non-Hamiltonian cubic graphs induce empty polyhedra as well. We compare our approach to the famous Dantzig-Fulkerson-Johnson relaxation of a TSP, and give empirical evidence which suggests that the latter is infeasible if and only if our constructed polyhedron is also empty. By considering special edge cut sets which are present in most cubic graphs, we describe a heuristic approach, built on our constructed polyhedron, for which incorrect diagnoses of non-Hamiltonian graphs as Hamiltonian appear to be very rare. In particular, for cubic graphs containing up to 18 vertices, only four out of 45,982 undirected connected cubic graphs were so misdiagnosed. By constrast, we demonstrate that an equivalent heuristic, when built on the Dantzig-Fulkerson-Johnson relaxation of a TSP, is mostly unsuccessful in identifying additional non-Hamiltonian graphs. These empirical results suggest that polynomial algorithms based on our constructed polyhedron may be able to correctly identify Hamiltonicity of a cubic graph in all but rare cases.
- Open Access
Deterministic "Snakes and Ladders" Heuristic for the Hamiltonian Cycle Problem
We present a polynomial complexity, deterministic, heuristic for solving the Hamiltonian Cycle Problem (HCP) in an undirected graph of order $n$. Although finding a Hamiltonian cycle is not theoretically guaranteed, we have observed that the heuristic is successful even in cases where such cycles are extremely rare, and it also performs very well on all HCP instances of large graphs listed on the TSPLIB web page. The heuristic owes its name to a visualisation of its iterations. All vertices of the graph are placed on a given circle in some order. The graph's edges are classified as either snakes or ladders, with snakes forming arcs of the circle and ladders forming its chords. The heuristic strives to place exactly $n$ snakes on the circle, thereby forming a Hamiltonian cycle. The Snakes and Ladders Heuristic (SLH) uses transformations inspired by $k-$opt algorithms such as the, now classical, Lin-Kernighan heuristic to reorder the vertices on the circle in order to transform some ladders into snakes and vice versa. The use of a suitable stopping criterion ensures the heuristic terminates in polynomial time if no improvement is made in $n^3$ major iterations.Open AccessDeterministic "Snakes and Ladders" Heuristic for the Hamiltonian Cycle Problem
We present a polynomial complexity, deterministic, heuristic for solving the Hamiltonian Cycle Problem (HCP) in an undirected graph of order $n$. Although finding a Hamiltonian cycle is not theoretically guaranteed, we have observed that the heuristic is successful even in cases where such cycles are extremely rare, and it also performs very well on all HCP instances of large graphs listed on the TSPLIB web page. The heuristic owes its name to a visualisation of its iterations. All vertices of the graph are placed on a given circle in some order. The graph's edges are classified as either snakes or ladders, with snakes forming arcs of the circle and ladders forming its chords. The heuristic strives to place exactly $n$ snakes on the circle, thereby forming a Hamiltonian cycle. The Snakes and Ladders Heuristic (SLH) uses transformations inspired by $k-$opt algorithms such as the, now classical, Lin-Kernighan heuristic to reorder the vertices on the circle in order to transform some ladders into snakes and vice versa. The use of a suitable stopping criterion ensures the heuristic terminates in polynomial time if no improvement is made in $n^3$ major iterations. - Open Access
A new benchmark set for Traveling salesman problem and Hamiltonian cycle problem
We present a benchmark set for Traveling salesman problem (TSP) with characteristics that are different from the existing benchmark sets. In particular, we focus on small instances which prove to be challenging for one or more state-of-the-art TSP algorithms. These instances are based on difficult instances of Hamiltonian cycle problem (HCP). This includes instances from literature, specially modified randomly generated instances, and instances arising from the conversion of other difficult problems to HCP. We demonstrate that such benchmark instances are helpful in understanding the weaknesses and strengths of algorithms. In particular, we conduct a benchmarking exercise for this new benchmark set totalling over five years of CPU time, comparing the TSP algorithms Concorde, Chained Lin-Kernighan, and LKH. We also include the HCP heuristic SLH in the benchmarking exercise. A discussion about the benefits of specifically considering outlying instances, and in particular instances which are unusually difficult relative to size, is also included.
Open AccessA new benchmark set for Traveling salesman problem and Hamiltonian cycle problem
We present a benchmark set for Traveling salesman problem (TSP) with characteristics that are different from the existing benchmark sets. In particular, we focus on small instances which prove to be challenging for one or more state-of-the-art TSP algorithms. These instances are based on difficult instances of Hamiltonian cycle problem (HCP). This includes instances from literature, specially modified randomly generated instances, and instances arising from the conversion of other difficult problems to HCP. We demonstrate that such benchmark instances are helpful in understanding the weaknesses and strengths of algorithms. In particular, we conduct a benchmarking exercise for this new benchmark set totalling over five years of CPU time, comparing the TSP algorithms Concorde, Chained Lin-Kernighan, and LKH. We also include the HCP heuristic SLH in the benchmarking exercise. A discussion about the benefits of specifically considering outlying instances, and in particular instances which are unusually difficult relative to size, is also included.
- 28 June 2017
- Published by Springer Nature in Annals of Operations Research
- Vol. 261 (1-2) , 393-399
A note on using the resistance-distance matrix to solve Hamiltonian cycle problem
- 28 June 2017
- Published by Springer Nature in Annals of Operations Research
- Vol. 261 (1-2) , 393-399
A note on using the resistance-distance matrix to solve Hamiltonian cycle problem
- Open Access
Using a Hamiltonian cycle problem algorithm to assist in solving difficult instances of Traveling Salesman Problem
We describe a hybrid procedure for solving the traveling salesman problem (TSP) to provable optimality. We first sparsify the instance, and then use a hybrid algorithm that combines a branch-and-cut TSP solver with a Hamiltonian cycle problem solver. We demonstrate that this procedure enables us to solve difficult instances to optimality, including one which had remained unsolved since its construction in 2002.
Open AccessUsing a Hamiltonian cycle problem algorithm to assist in solving difficult instances of Traveling Salesman Problem
We describe a hybrid procedure for solving the traveling salesman problem (TSP) to provable optimality. We first sparsify the instance, and then use a hybrid algorithm that combines a branch-and-cut TSP solver with a Hamiltonian cycle problem solver. We demonstrate that this procedure enables us to solve difficult instances to optimality, including one which had remained unsolved since its construction in 2002.
- Open Access
On near optimal control of systems with slow observables
The paper deals with a problem of control of a system characterized by the fact that the influence of controls on the dynamics of certain functions of state variables (called observables) is relatively weak and the rates of change of these observables are much slower than the rates of change of the state variables themselves. The contributions of the paper are twofold. Firstly, the averaged system whose solutions approximate the trajectories of the slow observables is introduced, and it is shown that the optimal value of the problem of optimal control with time discounting criterion considered on the solutions of the system with slow observables (this problem is referred to as perturbed) converges to the optimal value of the corresponding problem of optimal control of the averaged system. Secondly, a way how an asymptotically optimal control of the perturbed problem can be constructed on the basis of an optimal solution of the averaged problem is indicated, sufficient and necessary optimality conditions for the averaged problem are stated, and a way how a near optimal solution of the latter can be constructed numerically is outlined (the construction being illustrated with an example).
Open AccessOn near optimal control of systems with slow observables
The paper deals with a problem of control of a system characterized by the fact that the influence of controls on the dynamics of certain functions of state variables (called observables) is relatively weak and the rates of change of these observables are much slower than the rates of change of the state variables themselves. The contributions of the paper are twofold. Firstly, the averaged system whose solutions approximate the trajectories of the slow observables is introduced, and it is shown that the optimal value of the problem of optimal control with time discounting criterion considered on the solutions of the system with slow observables (this problem is referred to as perturbed) converges to the optimal value of the corresponding problem of optimal control of the averaged system. Secondly, a way how an asymptotically optimal control of the perturbed problem can be constructed on the basis of an optimal solution of the averaged problem is indicated, sufficient and necessary optimality conditions for the averaged problem are stated, and a way how a near optimal solution of the latter can be constructed numerically is outlined (the construction being illustrated with an example).
- 26 June 2015
- Published by Elsevier in Computers & Operations Research
- Vol. 64, 283-292
A new heuristic for detecting non-Hamiltonicity in cubic graphs
- 26 June 2015
- Published by Elsevier in Computers & Operations Research
- Vol. 64, 283-292
A new heuristic for detecting non-Hamiltonicity in cubic graphs
- 12 October 2014
- Published by Springer Nature in Set-Valued and Variational Analysis
- Vol. 23 (1) , 87-131
On Average Control Generating Families for Singularly Perturbed Optimal Control Problems with Long Run Average Optimality Criteria
- 12 October 2014
- Published by Springer Nature in Set-Valued and Variational Analysis
- Vol. 23 (1) , 87-131
On Average Control Generating Families for Singularly Perturbed Optimal Control Problems with Long Run Average Optimality Criteria
- Open Access
On average control generating families for singularly perturbed optimal control problems with long run average optimality criteria
The paper aims at the development of tools for analysis and construction of near optimal solutions of singularly perturbed (SP) optimal controls problems with long run average optimality criteria. The idea that we exploit is to first asymptotically approximate a given problem of optimal control of the SP system by a certain averaged optimal control problem, then reformulate this averaged problem as an infinite-dimensional (ID) linear programming (LP) problem, and then approximate the latter by semi-infinite LP problems. We show that the optimal solution of these semi-infinite LP problems and their duals (that can be found with the help of a modification of an available LP software) allow one to construct near optimal controls of the SP system. We demonstrate the construction with a numerical example.
Open AccessOn average control generating families for singularly perturbed optimal control problems with long run average optimality criteria
The paper aims at the development of tools for analysis and construction of near optimal solutions of singularly perturbed (SP) optimal controls problems with long run average optimality criteria. The idea that we exploit is to first asymptotically approximate a given problem of optimal control of the SP system by a certain averaged optimal control problem, then reformulate this averaged problem as an infinite-dimensional (ID) linear programming (LP) problem, and then approximate the latter by semi-infinite LP problems. We show that the optimal solution of these semi-infinite LP problems and their duals (that can be found with the help of a modification of an available LP software) allow one to construct near optimal controls of the SP system. We demonstrate the construction with a numerical example.