Finding the right cutting planes for the TSP.
Given an instance of the Traveling Salesman Problem (TSP), a reasonable way to get a lower bound on the optimal answer is to solve a linear programming relaxation of an integer programming formulation of the problem. These linear programs typically have an exponential number of constraints, but in theory they can be solved efficiently with the ellipsoid method as long as we have an algorithm that can take a solution and either declare it feasible or find a violated constraint. In practice, it is often the case that many constraints are violated, which raises the question of how to choose among them so as to improve performance. For the simplest TSP formulation it is possible to efficiently find all the violated constraints, which gives us a good chance to try to answer this question empirically. Looking at random two dimensional Euclidean instances and the large instances from TSPLIB, we ran experiments to evaluate several strategies for picking among the violated constraints. We found some information about which constraints to prefer, which resulted in modest gains, but were unable to get large improvements in performance.
Introduction
Given some set of locations and a distance function, the Traveling Salesman
Problem (TSP) is to find the shortest tour, i.e., simple cycle through all of the
locations. This problem has a long history (see, e.g. [11]) and is a famous example
of an NP-hard problem. Accordingly, there is also a long history of heuristics for
finding good tours and techniques for finding lower bounds on the length of the
shortest tour.
In this paper we focus on one well-known technique for finding lower bounds.
The basic idea is to formulate the TSP as an integer (linear) program (IP),
but only solve a linear programming (LP) relaxation of it. The simplest such
formulation is the following IP:
each pair fi; jg of cities
Objective: minimize
This work was done while the author was at AT&T Labs-Research.
Constraints:
The interpretation of this program is that x ij will tell us whether or not we
go directly from location i to location j. The first constraints say that we must
either go or not go; the second say that we must enter and leave each city exactly
once; and the third guarantee that we get one large cycle instead of several little
(disjoint) ones. The third constraints are called subtour elimination constraints,
and will be the main concern of our work.
We relax this IP to an LP in the standard way by replacing the first constraints
with 1. Observe that any solution to the IP will be a solution
to the LP, so the optimum we find can only be smaller than the original opti-
mum. Thus we get a lower bound, which is known as the Held-Karp bound[5, 6].
Experimental analysis has shown that this bound is pretty good: for random
two dimensional Euclidean instances, asymptotically the bound is only about
0:7% different from the optimal tour length, and for the "real-world" instances
of TSPLIB [12], the gap is usually less than 2% [7]. And if the distances obey the
triangle inequality, the bound will be at least 2=3 of the length of the optimal
tour [13, 15]. It is possible to give more complicated IPs whose relaxations have
smaller gaps, but we did not attempt to work with them for reasons that we will
explain after we have reviewed the method in more detail.
Observe that it is not trivial to plug this linear program into an LP solver,
because there are exponentially many subtour elimination constraints. Neverthe-
less, even in theory, there is still hope for efficiency, because the ellipsoid method
[4] only requires an efficient separation algorithm, an algorithm that takes a solution
and either decides that it is feasible or gives a violated constraint. For
the subtour elimination constraints, if we construct a complete graph with the
set of locations as vertices and the x ij as edge weights, it suffices to determine
whether or not the minimum cut of this graph, the way to separate the vertices
into two groups so that the total weight of edges crossing between the groups is
minimized, is less than two. If it is, the minimum cut gives us a violated constraint
(take the smaller of the two groups as S in the constraint); if not we are
feasible. Many algorithms for finding minimum cuts are known, ranging from
algorithms that follow from the early work on maximum flows in the 1950s [3]
to a recent Monte Carlo randomized algorithm that runs in O(m log 3 n) time on
a graph with m edges and n vertices [9].
Even better, it is possible to find all near-minimum cuts (as long as the graph
is connected) and thus find all the violated subtour elimination constraints. This
leads us to ask an obvious question: which violated constraints do we want to use?
When more than one constraint is violated, reporting certain violated constraints
before others may lead to a shorter overall running time. The primary goal of
this work is to explore this question.
There are several algorithms for finding all near-minimum cuts. They include
a flow-based algorithm due to Vazirani and Yannakakis [14], a contraction-based
algorithm due to Karger and Stein [10], and a tree-packing-based algorithm due
to Karger [9]. We chose to use the Karger-Stein algorithm, primarily because
of an implementation we had available that was not far from what we needed.
We did not try the others. We believe that the time to find the cuts is small
enough compared to the time spent by the LP solver that it would not change
our results significantly.
At this point we should justify use of the simplest IP. Our decision was made
partly on the grounds of simplicity and historical precedent. A better reason is
that with the simplest IP we can use the Karger-Stein minimum cut algorithm
and find all of the violated constraints. One can construct more complicated IPs
that give better bounds by adding more constraints to this simple IP, and there
are useful such constraints that have separation algorithms, but for none of the
sets of extra constraints that people have tried is it known how to efficiently find
all of the violated constraints, so it would be more difficult to determine which
constraints we would like to use. It may still be possible to determine which
constraints to use for a more complicated IP, but we leave that as a subject for
further research. Note that the constraints of the more complicated IPs include
the constraints of the simple IP, so answering the question for the simple IP is a
reasonable first step towards answering the question for more complicated IPs.
We found that it is valuable to consider only sets of small, disjoint constraints.
Relatedly, it seems to be better to fix violations in small areas of the graph
first. This strategy reduces both the number of LPs we have to solve and the
total running time. We note that it is interesting that we got this improvement
using the Karger-Stein algorithm, because in the context of finding one minimum
cut, experimental studies have found that other algorithms perform significantly
better [2, 8]. So our results are a demonstration that the Karger-Stein algorithm
can be useful in practice.
The rest of this paper is organized as follows. In Sect. 2 we give some important
details of the implementations that we started with. In Sect. 3 we discuss
the constraint selection strategies that we tried and the results we obtained. Fi-
nally, in Sect. 4 we summarize the findings and give some possibilities for future
work.
Starting Implementation
In this section we give some details about the implementations we started with.
We will discuss our attempts at improving them in Sect. 3. For reference, note
that we will use n to denote the number of cities/nodes and will refer to the
total edge weight crossing a cut as the value of the cut.
2.1 Main Loop
The starting point for our work is the TSP code concorde written by Applegate,
Bixby, Chv'atal, and Cook [1]. This code corresponds to the state of the art in
lower bound computations for the TSP. Of course it wants to use far more that
the subtour elimination constraints, but it has a mode to restrict to the simple
IP. From now on, when we refer to "the way concorde works", we mean the
way it works in this restricted mode. We changed the structure of this code very
little, mainly just replacing the algorithm that finds violated constraints, but
as this code differs significantly from the theoretical description above, we will
review how it works.
First of all, concorde does not use the ellipsoid method to solve the LP.
Instead it uses the simplex method, which has poor worst-case time bounds but
typically works much better in practice. Simplex is used as follows:
1. start with an LP that has only constraints (1) and (2)
2. run the simplex method on the current LP
3. find some violated subtour elimination constraints and add them to the LP;
if none terminate
4. repeat from 2
Observe that the initial LP describes the fractional 2-matching problem, so
concorde gets an initial solution by running a fractional 2-matching code rather
than by using the LP solver.
Second, it is important to pay attention to how cuts are added to the LP
before reoptimizing. There is overhead associated with a run of the LP solver, so
it would be inefficient to add only one cut at a time. On the other side, since not
many constraints will actually constrain the optimal solution, it would be foolish
to overwhelm the LP solver with too many constraints at one time. Notice also
that if a constraint is not playing an active role in the LP, it may be desirable
to remove it so that the LP solver does not have to deal with it in the future.
Thus concorde uses the following general process for adding constraints to the
LP, assuming that some have been found somehow and placed in a list:
1. go through the list, picking out constraints that are still violated until 250
are found or the end of the list is reached
2. add the above constraints to the LP and reoptimize
3. of the newly added constraints, only keep the ones that are in the basis
Thus at most 250 constraints are added at a time, and a constraint only
stays in the LP if it plays an active role in the optimum when it is added. After
a constraint is kept once, it is assumed to be sufficiently relevant that it is not
allowed to be thrown away for many iterations. In our case, for simplicity, we
never allowed a kept cut to leave again. (Solving this simple IP takes few enough
iterations that this change shouldn't have a large impact.)
Third, just as it is undesirable to work with all of the constraints at once, it
is also undesirable (in practice) to work with all of the variables at once, because
most of them will be 0 in the optimal solution. So there is a similar process of
selecting a few of the variables to work with, solving the LP with only those
variables, and later checking to see if some other variables might be needed, i.e.,
might be non-zero in an optimal solution. The initial sparse graph comes from a
greedy tour plus the 4 nearest neighbors with respect to the reduced costs from
the fractional 2-matching.
Finally, it is not necessary to find minimum cuts to find violated constraints.
If the graph is disconnected, then each connected component defines a violated
constraint. In fact, any set of connected components defines a violated con-
straint, giving a number of violated constraints exponential in the number of
components, so concorde only considers the constraints defined by one compo-
nent. This choice makes sense, because if each connected component is forced to
join with another one, we make good progress, at least halving the number of
components.
Another heuristic concorde uses is to consider the cuts defined by a segment
of a pretty good tour, i.e, a connected piece of a tour. concorde uses heuristics
to find a pretty good tour at the beginning, and the authors noticed that cuts
they found often corresponded to segments, so they inverted the observation
as a heuristic. We mention this heuristic because it is used in the original im-
plementation, which we compare against, but we do not use it in our modified
code.
Finally, a full pseudo-code description of what the starting version of concorde
does:
find an initial solution with a fractional 2-matching code
build the initial sparse graph, a greedy tour nearest in fractional
matching reduced costs
do
do
add connected component cuts (*)
add segment cuts (*)
if connected, add flow cuts (*)
else add connected component cuts
if no cuts added OR a fifth pass through loop,
check 50 nearest neighbor edges to see if they need to be added
while cuts added OR edges added
check all edges to see if they need to be added
while edges added
Note that the lines marked with (*) are where we make our changes, and the
adding of cuts on these lines is as above, which includes calling the LP solver.
2.2 Karger-Stein Minimum Cut Algorithm
The starting implementation of the Karger-Stein minimum cut algorithm (KS) is
the code written by Chekuri, Goldberg, Karger, Levine, and Stein [2]. Again, we
did not make large modifications to this code, but it already differs significantly
from the theoretical description of the algorithm. The original algorithm is easy
to state:
if the graph has less than 7 nodes, solve by brute force
repeat twice:
repeat until only n=
nodes remain:
randomly pick an edge with probability proportional to edge weight
and contract the endpoints
run recursively on the contracted graph
Contracting two vertices means merging them and combining the resulting parallel
edges by adding their weights. It is easy to see that contraction does not
create any cuts and does not destroy a cut unless nodes from opposite sides are
contracted.
The idea of the algorithm is that we are not so likely to destroy the minimum
cut, because by definition there are relatively few edges crossing it. In particular,
the random contractions to n=
nodes give at least a 50% chance of preserving
the minimum cut. Thus if we repeat the contraction procedure twice, there is a
reasonable chance that the minimum cut is preserved in one of the recursive calls,
so there is a moderate
(\Omega (1= log n)) chance that the minimum cut is preserved
in one of the base cases. By repeating the entire procedure O(log n) times, the
success probability can be improved to 1 \Gamma 1=n.
Of course we are not just interested in minimum cuts; we want all of the cuts
of value less than 2. We can find these by doing fewer contractions at a time,
that is, leaving more than n=
nodes. This modification makes cuts that are
near-minimum (which a cut of value 2 hopefully is) also have a good chance of
being found.
As KS is a Monte-Carlo algorithm (there is no easy way to be sure it has given
the right answer) and we did not want to affect the correctness of concorde,
whenever our implementation of KS found no cuts of value less than two, we always
double-checked with concorde's original flow-based cut finding algorithm.
Later, when we refer to implementations that use only KS to find cuts, we will
really mean that they always use KS, unless KS fails to find any cuts. Typically,
by the time KS failed to find any cuts, we were either done or very close to it,
so it is reasonable to ignore the fact that a flow algorithm is always still there.
An important thing to notice in KS is that we have two parameters to play
with. One is how many contractions we do at a time, which governs the depth
and success probability of the recursion. The other is how many times we run the
whole procedure. In order to achieve a specific success probability, we can only
choose one of these. If we are willing to do away with the theoretical analysis and
make a heuristic out of this algorithm, we can choose both. Since we do have a
correctness check in place, making KS a heuristic is a reasonable thing to do. In
particular, we started with the first parameter set so that we would find all cuts
of value less than two with
probability\Omega (1= log n), and the second parameter set
to three. We found that three iterations was sufficient to typically find a good
fraction (approximately two thirds) of the cuts, and this performance seemed
good enough for our purposes. Later, after we had gathered some information
about the cuts, we worried about reducing the time spent by KS and set the
first parameter such that we would only find cuts of value less than one with
probability\Omega (1= log n). Note that regardless of the setting of the first parameter,
the code will always report all the cuts of value less than two that it finds. So
the later version of the code does not disregard higher value cuts as a result of
changing the parameter, it merely has a lower chance of finding them.
The implemented version chooses edges for contraction in one pass, rather
than one at a time. This modification can allow more contractions under certain
good circumstances, but can cause trouble, because it is possible to get unlucky
and have the recursion depth get large. See [2] for a thorough discussion of the
implemented version. A change we made here was to repeat the contraction step
if nothing gets contracted; while this change is an obvious one to make, it likely
throws off the analysis a bit. Since we will make the algorithm a heuristic anyway,
we chose not to worry about exactly what this little change does. Note that
we had to disable many of the Padberg-Rinaldi heuristics used in the starting
implementation, because they only work if we are looking for minimum cuts, not
near-minimum cuts.
We also had to make some modifications so that we could run on disconnected
graphs. If the graph is disconnected, there can be exponentially many minimum
cuts, so we cannot hope to report them all. At first we worked around the problem
of disconnected graphs by forcing the graph to be connected, as the starting
implementation of concorde does. However, later in the study we wanted to try
running KS earlier, so we had to do something about disconnected graphs. Our
new workaround was to find the connected components, report those as cuts,
and run KS in each component. This modification ignores many cuts, because
a connected component can be added to any cut to form another cut of the
same value. We chose this approach because 1) we had to do something, and 2)
other aspects of our experiments, which we describe shortly, suggest that this
approach is appropriate.
One last modification that we made was to contract out paths of edges of
weight one at the beginning. The point of this heuristic is that if any edge on
a path of weight one is in a small cut, then every such edge is in a small cut.
So we would find many cuts that were very similar. Our experiments suggested
that it is more useful to find violated constraints that are very different, so we
used this heuristic to avoid finding some similar cuts.
3 Experiments and Results
3.1 Experimental Setup
Our experiments were run on an SGI multiprocessor (running IRIX 6.2) with
processors. The code was not parallelized, so it only
ran on one processor, which it hopefully had to itself. The machine had 6 Gb of
main memory and 1 Mb L2 cache. The code was compiled with SGI cc 7.2, with
the -O2 optimization option and set to produce 64 bit executables. CPLEX 5.0
was used as the LP solver.
Several processes were run at once, so there is some danger that contention
for the memory bus slowed the codes down, but there was nothing easy we could
do about it, and we do not have reason to believe it was a big problem. In any
case, all the codes were run under similar conditions, so the comparisons should
be fair.
We used two types of instances. One was random two dimensional Euclidean
instances generated by picking points randomly in a square. The running times
we report later are averages over 3 random seeds. The second type of instance
was "real-world", from TSPLIB. We tested on rl11849, usa13509, brd14051,
pla33810, and pla85900.
3.2 Observations and Modifications
We started our study by taking concorde, disabling the segment cuts, and substituting
KS for the flow algorithm. So the first time the algorithm's behavior
changed was after the graph was connected, when KS was first called. At this
point we gathered some statistics for a random 10000 node instance about the
cuts that were found and the cuts that were kept. Figure 1 shows two histograms
comparing cuts found to cuts kept. The first is a histogram of the size of the cuts
found and kept, that is, the number of nodes on the smaller side. The second
shows a similar histogram of the value of the cuts found and kept. Note that the
scaling on the Y-axis of these histograms is unusual.
These histograms show several interesting features. First, almost all of the
kept cuts are very small-fewer than 100 nodes. The found cuts are also very
biased towards small cuts, but not as much. For example, many cuts of size
approximately 2000 were found, but none were kept. A second interesting feature
is that the minimum cut is unique (of value approximately .3), but the smallest
kept cut is of value approximately .6, and most of the kept cuts have value
one. This observation immediately suggests that it is not worthwhile to consider
only minimum cuts, because they are few in number and not the cuts you want
anyway. Furthermore, it appears that there is something special about cuts of
value one, as a large fraction of them are kept.
To try to get a better idea of what was going on, we took a look at the
fractional solution. Figure 2 shows the fractional 2-matching solution for a 200
node instance, which is what the cut finding procedures are first applied to.
Not surprisingly, this picture has many small cycles, but the other structure
that appears several times is a path, with some funny edge weights at the end
that allow it to satisfy the constraints. The presence of these structures suggests
looking at biconnected components in the graph induced by non-zero weight
edges. A long path is in some sense good, because a tour looks locally like a
path, but it is important that the two ends meet, which is to say that the graph
must not only be connected but biconnected.
Cut Size2575Number
of
Cuts100030005000
Cut Size After First Connected
(random 10000 city instance)
Cut
Number
of
Cuts20006000
Cut Value After First Connected
(random 10000 city instance)
Fig. 1. Histograms showing properties of cuts found as compared to cuts kept. Gray
bars represent found cuts and black bars represent cuts. Note that there is unusual
scaling on the Y-axes.
Fig. 2. Picture of a fractional 2-matching (initial solution) for a 200 node instance.
Edge weights are indicated by shading, from white= 0 to black= 1.
We tried various ways of incorporating biconnected components before finding
a method that worked well. There are two issues. One is when to try to find
biconnected components. Should we wait until the graph is connected, or check
for biconnectivity in the connected components? The second issue is what cuts to
report. Given a long path, as above, there is a violated constraint corresponding
to every edge of the path. Or stated more generally, there is a violated constraint
corresponding to every articulation point (a node whose removal would
disconnect the graph). Our first attempt was to look for biconnected components
only once the graph was connected, and to report all the violated constraints.
This approach reduced the number of iterations of the main loop, but took more
time overall. Running biconnected components earlier reduced the number of
iterations further, but also took too long.
So to reduce the number of cuts found, we modified the biconnected components
code to report only constraints corresponding to biconnected components
that had one or zero articulation points. (Note that a biconnected component
with 0 articulation points is also a connected component.) The idea behind this
modification is the same idea that was used to report constraints based on the
connected components. In that context, we said that it made sense to consider
only the constraints corresponding to the individual components, thus picking
out small, disjoint constraints. Likewise, taking biconnected components with
one or zero articulation points picks out small, disjoint constraints. This use of
biconnected components proved valuable; it both reduced the number of iterations
of the outer loop and reduced the overall running time. Accordingly, it is
only this version that we give data for in the results section.
Our experience with KS was similar. Using it to find all of the violated
constraints turned up so many that even though we saved iterations, the total
running time was far worse. And it seemed to be faster to run KS right from the
beginning, not waiting for the graph to become connected. So we generalized the
idea above. We only report the smallest disjoint cuts; that is, we only report a
cut if no smaller (in number of nodes) cut shares any nodes with it. It should be
easy to see that the rules given above for selecting cuts from connected or biconnected
components are special cases of this rule. So our eventual implementation
with KS uses it right from the beginning, and always reports only the smallest
cuts. Note that our handling of disconnected graphs is consistent with finding
smallest cuts. Notice also that reporting only smallest cuts means we do not
introduce a constraint that will force a connected component to join the other
connected components until the component itself satisfies the subtour elimination
constraints. This choice may seem foolish, not introducing a constraint we
could easily find, but what often happens is that we connect the component to
another in the process of fixing violations inside the component, so it would have
been useless to introduce the connectivity constraint.
In this vein, we discovered that it could actually be harmful to force the
graph to be connected before running KS. It would not be surprising if the
time spent getting the graph connected was merely wasted, but we actually saw
instances where the cut problem that arose after the graph was connected was
much harder than anything KS would have had to deal with if it had been
run from the beginning. The result was that finding connected components first
actually cost a factor of two in running time.
Note that the implementation of selecting the smallest cuts was integrated
into KS. We could have had KS output all of the cuts and then looked through
them to pick out the small ones, but because KS can easily keep track of sizes
as it contracts nodes, it is possible to never consider many cuts and save time.
There is also one observation that we failed to exploit. We noticed that
the value histogram shows some preference for keeping cuts that have small
denominator value; most kept cuts had value one, then several more had value
3=2, a few more had 4=3 and 5=3, etc. Unfortunately, we did not come up with a
way to exploit this observation. We tried sorting the cuts by denominator before
adding them to the LP, hoping that we would then get the cuts we wanted first
and be able to quickly discard the others, but were unable to get a consistent
improvement this way. Even when there was an improvement, it was not clear
whether it was entirely due to the fact that cuts of value one got added first.
3.3 Results
We present our data in the form of plots, of which there are three types. One
reports total time, another reports the number of LPs solved, and the third
only considers the time to add cuts (as described above), which counts only the
time to process the lists of cuts and reoptimize, but not the time to find the
cuts. The total time includes everything: the time to add cuts, the time to find
them, the time to add edges, the time to get an initial solution, etc. We also
have two classes of plots for our two classes of inputs, random instances and
instances. All times are reported relative to the square of the number
of cities, as this function seems to be the approximate asymptotic behavior of
the implementations. More precisely, the Y-axes of the plots that report times
are always 1000000   (time in seconds)=n 2 . This scale allows us to see how the
algorithms compare at both large and small problem sizes. Note also that the
X-axes of the TSPLIB plots are categorical, that is, they have no scale. Table 1
summarizes the implementations that appear in the plots.
Short name Description
starting point original concorde implementation
w/o segments original with segment cuts disabled
biconnect using smallest biconnected components instead of connected
KS all cut finding done by KS
KS1 all cut finding done by KS, probabilities set for cuts of value

Table

1. Summary of the implementations for which we report data
There are several things to notice about the plots. First, looking at the time
to add cuts for random instances (Fig. 3), we see that using either biconnected
components or KS consistently improves the time a little bit. Furthermore, using
the version of KS with looser probabilities causes little damage. Unfortunately,
the gain looks like it may be disappearing as we move to larger instances. Looking
at the number of LPs that we had to solve shows a clearer version of the same
results (Fig. 4). Looking at the total time (Fig. 5), we see the difference made by
adjusting the probabilities in KS. The stricter version of KS is distinctly worse
than the original concorde, whereas the looser version of KS is, like the version
with biconnected components, a bit better. Looking at the total time is looks
even more like our gains are disappearing at larger sizes.
The story is similar on the TSPLIB instances (Figs. 6,8,7) Biconnected components
continue to give a consistent improvement. KS gives an improvement
on some instances, but not on the PLA instances.
Number of Cities0.71.11.51.9
Running
Time
squared
Random Instances: Add Cuts Running Time
starting point
w/o segments
biconnect
KS
KS1
Fig. 3.
The strategy of looking for the smallest cuts seems to be a reasonable idea, in
that it reduces the number of iterations and improves the running time a bit,
but the gain is not very big. It also makes some intuitive sense that by giving
Number of Cities50150Number
of
LPs
Solved
Random Instances: LPs Solved
starting point
w/o segments
biconnect
KS
KS1
Fig. 4.
Number of Cities1.52.5Running
Time
squared
Random Instances: Total Running Time
Instance0.51.5Running
Time
squared
Instances: Add Cuts Running Time
starting point
w/o segments
biconnect
KS
KS1
Fig. 6.
Number
of
LPs
Solved
Instances: LPs Solved
Instance0.51.52.5Running
Time
squared
Instances: Total Running Time
starting point
w/o segments
biconnect
KS
KS1
Fig. 8.
an LP solver a smallest region of the graph where a constraint is violated, it will
encourage the solver to really fix the violation, rather than move the violation
around.
It is worth noting that the right cuts are definitely not simply the ones that
are easiest to find. As mentioned above, it was possible to slow the implementation
down significantly by trying to use easy-to-find cuts first.
It is also interesting that it is possible to make any improvement with KS
over a flow based code, because experimental studies indicate that for finding
one minimum cut, it is generally much better to use the flow-based algorithm of
Hao and Orlin. So our study suggests a different result: KS's ability to find all
near-minimum cuts can in fact make it practical in situations where the extra
cuts might be useful.
For future work, it does not seem like it would be particularly helpful to
work harder at finding subtour elimination constraints for the TSP. However,
studies of which constraints to find in more complicated IPs for the TSP could
be more useful, and it might be interesting to investigate KS in other contexts
where minimum cuts are used.

Acknowledgements

Many thanks to David Johnson for several helpful discussions and suggestions,
including the suggestion that I do this work in the first place. Many thanks to
David Applegate for help with concorde and numerous helpful discussions and
suggestions.



--R

On the solution of traveling salesman problems.
Experimental study of minimum cut algorithms.

Geometric Algorithms and Combinatorial Optimization
The traveling-salesman problem and minimum spanning trees
The traveling-salesman problem and minimum spanning trees: Part ii
Asymptotic experimental analysis for the held-karp traveling salesman bound
Practical performance of efficient minimum cut algorithms.
Minimum cuts in near-linear time
A new approach to the minimum cut problem.
Rinooy Kan

Analyzing the held-karp tsp bound: A monotonicity property with applications
Suboptimal cuts: Their enumeration
Heuristic analysis
--TR
Analyzing the Held-Karp TSP bound: a monotonicity property with application
Minimum cuts in near-linear time
Asymptotic experimental analysis for the Held-Karp traveling salesman bound
Suboptimal Cuts
combinatorial optimization;performance;experimentation;algorithms;minimum cut;traveling salesman problem;cutting plane