In 2000, Feinberg suggested an embedding of HCP in a discounted MDP. Feinberg introduced a polytope * X_{β} *defined for any given graph, such that every Hamiltonian cycle in the graph corresponds to an extreme point of

The characterisation given in Nguyen [5] indicates that 1-randomised policies induced by extreme points of * X_{β}* are less prevalent than might have been conjectured, since they cannot be constructed from convex combinations of just any two deterministic policies. This provides a motivation for testing algorithmic approaches based on successive elimination of arcs that could be used to construct these convex combinations. Since our goal is to find an extreme point

The branch-and-fix method is as follows. We solve a sequence of linear programs - two at each branching point of the logical B&F tree - with the generic structure

min *L*(**x**)

s.t.

* x* ∈

**Step 1 - Initiation.** We solve the original LP without any additional constraints and with some choice of an objective function *L*(**x**). We obtain an optimal basic feasible solution *x** _{0}*. We then find

**Step 2 - Branching.** We use the 1-randomised policy * f_{0}* to identify the splitting vertex

**Step 3 - Fixing**. In many subdigraphs, the fixing of one arc implies that other arcs can also be fixed, without a possibility of unintentionally eliminating a Hamiltonian cycle containing already fixed arcs that are part of a Hamiltonian cycle in the current subdigraph. Four checks for determining additional arcs that can be fixed are described later in this section. Once we identify these arcs, we also fix them at this step.

**Step 4 - Iteration**. We solve a second LP that checks if certain bounds can still be satisfied with the current fixing of arcs. If so, we repeat Step 1 with the LP constructed for the graph at the current branching point of the logical B&F tree, with additional constraints detailed in Ejov et al [1]. This branching point may correspond to G_{1}, G_{2}, ... , G_{d}, or to a sub-graph constructed from one of these with the help of additional arc fixing.

As is typical with branching methods, decisions guiding which branch to select first are important and open to alternative heuristics. Ejov et al [1] investigate five possible branching methods.

The branch-and-fix method is investigated in detail in Haythorpe [4] and experimental results are given for many instances. In addition, new constraints, called Wedge constraints, are added to the bound fathoming checks, that result in significant improvements to the efficiency of the heuristic. These improvements ultimately inspired the Wedged-MIP Heuristic.

[1] Ejov, V., Filar, J.A., Haythorpe, M. and Nguyen, G.T. "Refined MDP-based branch-and-fix algorithm for the Hamiltonian Cycle Problem." *Mathematics of Operations Research*, 34(3):758-768, 2009. ACM Digital Library

[2] Feinberg, E. "Constrained discounted Markov decision processes and Hamiltonian cycles." *Mathematics of Operations Research*, 25(1):130-140, 2000. JSTOR

[3] Filar, J.A. and Lasserre, J.B. "A non-standard branch and bound method for the Hamiltonian cycle problem." *Australian and New Zealand Industrial and Applied Mathematics Journal*, 42:586-607, 2000.ANZIAM Journal

[4] Haythorpe, M. "Markov Chain based algorithms for the Hamiltonian cycle problem." University of South Australia, 2010. Systems Optimization Laboratory

[5] Nguyen, G.T. "Hamiltonian cycle problem, Markov decision processes and graph spectra." University of South Australia, 2009.