The HTRO Workshop was conducted on December 14th-15th, 2012. There were 20 speakers, whose talks are listed below. Where available, the presentation slides are also linked.

 

The program and list of abstracts can be found here.

 

 

Footsteps in Instance Space: Steps Towards a Free Lunch

fProf. Kate Smith-Miles
Monash University

The No-Free-Lunch Theorem tells us that, without prior knowledge of the properties of an instance of a problem, we cannot expect any single algorithm to outperform all others across all instances. If an algorithm performs exceptionally well on a certain class of instances, there will always be some other class of instances where it is outperformed by another algorithm. Understanding how the properties of an instance affect algorithm performance is the key to being able to articulate the strengths and weaknesses of an algorithm, and to anticipate when it is likely to be better than others.


In this talk I will present a new methodology for achieving this goal, and demonstrate its applicability to optimization, although it generalizes to other problem domains. The methodology involves: visualizing the set of all possible instances based on features that correlate with difficulty; statistical generalization of algorithm performance in this instance space, shown as a footprint where an algorithm's performance is deemed to be good; and then measuring the relative area of the footprint of different algorithms. The methodology is applied to provide insights into optimization algorithm performance on the Travelling Salesman Problem and graph colouring.

 

 

 The Traveling Salesman Problem with Pickup and Delivery: A Polyhedral Approach

Dr. Irina Dumitrescu
IBM Research Australia

 The Traveling Salesman Problem with Pickup and Delivery (TSPPD) is defined on a graph containing pickup and delivery vertices between which there exists a one-to-one relationship. The problem consists of determining a minimum cost tour such that each pickup vertex is visited before its corresponding delivery vertex. We discuss modelling the TSPPD as an integer linear program and we investigate its polyhedral structure. We determine the dimension of the TSPPD polytope and present several valid inequalities, some of which are facet defining. Finally, we show how some of the valid inequalities can be integrated into a branch-and-cut algorithm.

 

 The Hamiltonian Cycle Problem and Markov Decision Processes

Prof. Jerzy Filar
Flinders University

We consider the famous Hamiltonian cycle problem (HCP) embedded in a Markov decision process (MDP). More specifically, we consider a moving object on a graph G where, at each vertex, a controller may select an arc emanating from that vertex according to a probabilistic decision rule. A stationary policy is simply a control where these decision rules are time invariant.  Such a policy induces a Markov chain on the vertices of the graph. Therefore, HCP is equivalent to a search for a stationary policy that induces a 0-1 probability transition matrix whose non-zero entries trace out a Hamiltonian cycle in the graph.  A consequence of this embedding is that we may consider the problem over a number of, alternative, convex - rather than discrete - domains.  These include: (a) the space of stationary policies, (b) the more restricted but, very natural, space of doubly stochastic matrices induced by the graph, and (c) the associated spaces of so-called "occupational measures".

 

 Hamiltonian Cycles, Extreme Points and Rapidly Mixing Markov Chains

Dr. Ali Eshragh
Adelaide University

In this talk, we introduce a certain polytope, H, induced by a particular discounted Markov decision process corresponding to a given graph G. It has been proved that if the graph G is Hamiltonian, then corresponding to each Hamiltonian cycle in G there exists an extreme point in H, namely, a Hamiltonian extreme point. We concentrate on Erdös-Renyi random graph G{n,p}, where n is the total number of nodes and p is the probability of having an arc between any pair of nodes. We show that the set of all extreme points of polytope H corresponding to a random graph G{n,p} can be partitioned into five subsets and derive the expected cardinality of each of them. These results indicate that the ratio of expected number of Hamiltonian extreme points to all extreme points decays rapidly as the latter is of the order O(nn). However, an adaptation of the polytope H, will be shown to have much more favourable ratios of this type. In particular, we constrain H by appropriately designed, efficient linear constraints, to obtain a new polytope WHH. Numerical results suggest the following two conjectures on WH: (i) Extreme points of polytope WH can be generated, uniformly, in polynomial time, (ii) The rational frequency of Hamiltonian extreme points in WH is bounded below by a rational function of n. In order to prove (i), one may try to design a random walk on extreme points of WH which has the property that the underlying Markov chain is rapidly mixing. To prove (ii), a good approach might be to extract certain geometric properties of extreme points of WH and try to use the same notion as utilized in H. We support our conjectures by numerical results. If we prove these two conjectures, we can assert that for any given graph G the Hamiltonian cycle problem can be solved, with high probability, in polynomial time.

 

 

 On The Decision of Non-Hamiltonicity via Linear Feasibility Models

Dr. Michael Haythorpe
Flinders University

We construct polyhedra, defined by a polynomially-bounded number of linear constraints dependent on the structure of a 3-regular graph Γ, that are guaranteed to be non-empty if Γ contains Hamiltonian cycles, but which may be empty otherwise. Then, if such a set of constraints is found to be inconsistent, we may conclude that Γ is non-Hamiltonian. We present a (nontrivial) proof of the inconsistency of constraints produced for bridge graphs. A further refinement of this approach which takes advantage of particular k-bonds (where k = 1, 2, 3) is shown, along with experimental evidence to indicate that almost all 3-regular non-Hamiltonian graphs can be identified by this approach.

 

 Traveling Salesman Problem with Side Constraints

Prof. Martin Savelsbergh
University of Newcastle

The vehicle routing problem (VRP), introduced by Dantzig and Ramser in 1959, is an important problem in the fields of transportation, distribution, and logistics. The VRP seeks to serve a number of customers with a fleet of vehicles at minimum cost. Many variants of the VRP have been proposed and investigated to accommodate complexities encountered in real-life settings, e.g., time windows and pickup and deliveries. Once an assignment of customers to vehicles is known, minimizing the cost for a vehicle corresponds to solving a Traveling Salesman Problem (TSP), often a TSP with side constraints. We explore computational challenges encountered when solving a TSP with time window flexibility and a TSP with delivery quantity flexibility.

 

 Understanding Heuristics and the Hamiltonian Cycle Problem

Dr. Richard Taylor
Defence, Science and Technology Organisation

We shall discuss an optimisation form of the Hamilton cycle problem and goodness measures of heuristics for this problem. This will include discussion of the boundary between what we currently know and what we would like to know.

 

 Genetic Theory of Cubic Graphs

Mr. Pouya Baniasadi
Flinders University

We propose a partitioning of the set of unlabelled, connected cubic graphs into two disjoint subsets named genes and descendants, where the cardinality of the descendants is much larger than that of the genes. The key distinction between the two subsets is the presence of special edge cut sets, called crackers, in the descendants. We show that every descendant can be constructed by starting from a finite set of genes, and introducing the required crackers by special breeding operations. We prove that it is always possible to identify which genes are used to generate a descendant, and provide inverse operations that enable their reclamation. A number of interesting properties of genes, such as planarity and non-Hamiltonicity, may be inherited by the descendant, and we therefore propose a natural polynomial algorithm that decomposes a descendant into its ancestor genes. We conjecture that each descendant can only be generated by starting with a unique set of ancestor genes.

 

 Snakes and Ladders Heuristic for the Hamiltonian Cycle Problem

A/Prof. Vladimir Ejov
Flinders University

We present a polynomial complexity heuristic for solving the Hamiltonian Cycle Problem in an undirected graph of order fn. 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 quickly on all HCP examples of large graphs listed on 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 fn 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. This is a joint work with P. Baniasadi, J. Filar, M. Haythorpe and S. Rossomakhine (all Flinders University).

 

 Scheduling Arc Capacity Changes over Time so as to Maximize Dynamic Flow in a Network

Prof. Natashia Boland
University of Newcastle

Many real life systems can be viewed as a network with arc capacities, supporting the flow of a commodity, in which maximizing throughput of the commodity in the network is a key concern. Whilst this suggests a maximum flow model would be appropriate, in fact, the real network is not static: capacities change over time. Changes can arise in strategic planning as a result of capacity expansion, with either new arcs or extra capacity added to existing arcs, subject to budget constraints on limiting what can be built in a time period. In tactical planning, capacity changes can occur as a result of maintenance activities, leading to reductions in arc capacities for the period of the maintenance. To obtain maximum throughput, it is important to select the schedule for capacity changes (such as addition of new arcs, or timing of maintenance jobs) that leads to minimum loss of flow. This leads to a model in which arc capacity change "jobs" need to be scheduled so as to maximize the total flow in the network over time. The resulting combinatorial optimization problem provides a rich field for analysis: computational complexity, approximation algorithms, and asymptotic analysis are all of interest. Some initial results in these directions will be discussed.

 

 Improving Christofides' Algorithm with Randomization and Linear Programming

Prof. David Shmoys
Cornell University

We will survey a number of recent results that yield improved approximation algorithms for variants of the traveling salesman problem (TSP); an r-approximation algorithm for an optimization is a polynomial-time algorithm that is guaranteed to find a feasible solution of objective function value within a factor of r of optimal. We shall briefly discuss recent results of Oveis Gharan, Saberi, & Singh and Mumka & Svensson for the graphical TSP,  Asadpour, Goemans, Madry, Oveis Gharan, & Saberi  for the asymmetric TSP, but we shall focus on a result of An, Kleinberg, and Shmoys for the s-t path traveling salesman problem, which provides an approximation algorithm that is guaranteed to find a solution of cost within a factor of the golden ratio of optimal in polynomial time.

In the s-t path TSP, we are given pairwise distances among n points that satisfy the triangle inequality, and two specified endpoints s and t; the problem is to find a shortest Hamiltonian path between s and t. Hoogeveen showed that the natural variant of the classic TSP algorithm of Christofides is a 5/3-approximation algorithm for this problem, and this asymptotically tight bound in fact has been the best approximation ratio known until now. We modify this algorithm so that it randomly chooses the initial spanning tree based on an optimal solution to a natural linear programming relaxation, rather than a minimum spanning tree; we prove this simple but crucial modification leads to an improved approximation ratio, surpassing the 20-year-old barrier set by the natural Christofides' algorithm variant.

 

 

Coherent Structures in Geophysical Flows

A/Prof. Gary Froyland
University of New South Wales

The detection and tracking of minimally dispersive regions in fluid flow is of importance in oceanography and atmospheric science. The strong non-dispersiveness of coherent objects such as eddies (resp. vortices) makes them excellent transporters of water (resp. air) with different physical properties to the surrounding water (resp. air). I will describe a method for identifying and tracking coherent regions in flows, which is based on the classical minimax characterisation of eigenvalues of compact self-adjoint operators.

 

 Some Problems in Hamiltonian cycles

Prof. Brendan McKay
Australian National University

We present a random selection of problems regarding Hamiltonian cycles. These include Hamiltonian cycles in various types of planar graphs, as well as hypo-hamiltonian graphs. Algorithms for finding cycles will be discussed in this context.

 

 Everything You Always Wanted to Know About the Second Hamiltonian Cycle Problem

Dr. János Barát
Monash University

Starring Thomassen, Thomason, Haxell, Fleischner, Edmonds, Sheehan, Jackson. featuring Deletion and contraction, Hamiltonian pairs, Lollipop method, Cubic and other regular graphs, Algorithms: polynomial and exponential, Lovasz local lemma, Chromatic roots, etc.

 

 The Tutte Polynomial of a Graph: Background, Computation and Theory

Prof. Gordon Royle
University of Western Australia

The Tutte polynomial of a graph is a 2-variable polynomial associated a graph that is a universal deletion/contraction invariant, in the sense that ANY graphical parameter that can be computed by a deletion/contraction recurrence, such as the chromatic polynomial, number of spanning trees, reliability polynomial and so on, is an evaluation of the Tutte polynomial.

The ubiquity of the Tutte polynomial is further evidenced by the fact that it appears in statistical physics under the guise of the q-state Potts model, and there is a substantial literature in Physics on the computational and theoretical aspects of the Tutte polynomial.

As deletion/contraction is inherently exponential in nature and many of these graphical parameters are known to be NP-hard to compute individually, computing the Tutte polynomial is hard both in theory and in practice, making data-driven computational exploration and experimentation difficult.

In this talk, I will survey various approaches to computing the Tutte polynomial, some of the problems that have been resolved or refined as a result of computational experimentation, and some of the many interesting remaining problems.

 

 On Hamiltonian Cycles in Planar Graphs

A/Prof. David Wood
Monash University

The study of Hamiltonian cycles in cubic planar graphs has a rich history, originally motivated by Tait's conjecture that every cubic 3-connected planar graph is Hamiltonian (which implies the 4- colour theorem). Tutte disproved Tait's conjecture, which lead Barnette to conjecture that every bipartite cubic 3-connected planar graph is Hamiltonian. We prove a new sufficient condition for a cubic 3-connected planar graph to be Hamiltonian. This condition is most easily described as a property of the dual graph. Let G be a planar triangulation. Then the dual G* is a cubic 3-connected planar graph, and G* is bipartite if and only if G is Eulerian. We prove that if the vertices of G are (improperly) coloured blue and red, such that the blue vertices cover the faces of G, there is no blue cycle, and every red cycle contains a vertex of degree at most 4, then G* is Hamiltonian. This result implies the following special case of Barnette's Conjecture: if G is an Eulerian planar triangulation, whose vertices are properly coloured blue, red and green, such that every red-green cycle contains a vertex of degree 4, then G* is Hamiltonian. We also prove some results highlighting the limitations of using a proper colouring of G as a starting point for proving Barnette's Conjecture. This is joint work with Helmut Alt, Michael Payne, and Jens Schmidt.

 

 Hamiltonian Cycles, Where Art Thou?

Dr. Giang Nguyen
Adelaide University

We explore the relationship between the geometric structure of a graph and its spectrum, by investigating certain functionals of graph eigenvalues and showing that they are related to geodesics on the graph. In particular, we present an intriguing self-similar structure that groups cubic graphs according to the number of geodesics of certain lengths, and discuss the location of non-Hamiltonian graphs within this self-similar structure.

 

 Geometric and Algebraic Methods for Hamilton Cycles

Dr. David Glynn
Flinders University

We look at any simple 3-connected cubic graph on n vertices and discuss one of its matroid representations, which involves a "quantum set" of n lines in binary space PG(r,2) with r=n/2.    The edge 3-colourings of the graph correspond bijectively to another related set of lines of this space, and the Hamilton cycles correspond to the points on precisely one (or an odd number) of these lines. It follows (from coding-theoretic or algebraic considerations) that the number of Hamilton cycles through any edge is even and there cannot be just one or two Hamilton cycles in the graph.  W.T. Tutte and C.A.B. Smith obtained these results but from different methods.  We discuss other methods such as a way to find all edge 3-colourings from the solutions of a single polynomial equation over GF(4). So the graph is a "snark" if and only if there are no solutions.  Another method is to determine Hamilton cycles in bipartite cubic graphs from a binary determinant condition of degree r-1 in r+1 variables where the graph has 2r vertices.

 

 Graph Fragmentability and Planarisation

A/Prof. Graham Farr
Monash University

Planarisation is the process of removing part of a graph to leave behind a planar subgraph.  This is important in many applications where networks must be laid out on two-dimensional surfaces such as a screen or a circuit layer.  We consider the Maximum Induced planar Subgraph problem, in which planarisation is achieved by removal of vertices.  We have linked this to the problem of fragmentability of graphs, where we seek the smallest proportion of vertices in a graph whose removal breaks the graph into small (bounded size) pieces. This talk describes our algorithms for these and related problems, which give the best performance guarantees to date for them.

 

 Recent Progresses on Linear Programming and the Simplex Method

Prof. Yinyu Ye
Stanford University

Linear programming (LP), together with the simplex method, remain a core topic in Operations Research, Computer Science and Mathematics since 1947. Due to the relentless research effort, a linear program can be solved today one million times faster than it was done thirty years ago. Businesses, large and small, now use LP models to control manufacture inventories, price commodities, design civil/communication networks, and plan investments. LP even becomes a popular subject taught in under/graduate and MBA curriculums, advancing human knowledge and promoting science education. The aim of the talk is to describe several recent exciting progresses on LP and the simplex method, include counter examples to the Hirsch conjecture, some pivoting rules and their exponential behavior, strongly polynomial-time bounds of the simplex and policy-iteration methods for solving Markov Decision Process (MDP) and turn-based zero-sum game with constant discount factors, the strongly polynomial-time complexity of the simplex method for solving deterministic MDP regardless discounts, etc.