On the empirical scaling of running time for finding optimal solutions to the TSP

We study the empirical scaling of the running time required by state-of-the-art exact and inexact TSP algorithms for finding optimal solutions to Euclidean TSP instances as a function of instance size. In particular, we use a recently introduced statistical approach to obtain scaling models from observed performance data and to assess the accuracy of these models. For Concorde, the long-standing state-of-the-art exact TSP solver, we compare the scaling of the running time until an optimal solution is first encountered (the finding time) and that of the overall running time, which adds to the finding time the additional time needed to complete the proof of optimality. For two state-of-the-art inexact TSP solvers, LKH and EAX, we compare the scaling of their running time for finding an optimal solution to a given instance; we also compare the resulting models to that for the scaling of Concorde’s finding time, presenting evidence that both inexact TSP solvers show significantly better scaling behaviour than Concorde.     

On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem

The travelling salesman problem (TSP)   is one of the most prominent NP-hard combinatorial optimisation problems. After over fifty years of intense study, the TSP continues to be of broad theoretical and practical interest. Using a novel approach to empirical scaling analysis, which in principle is applicable to solvers for many other problems, we demonstrate that some of the most widely studied types of TSP instances tend to be much easier than expected from previous theoretical and empirical results. In particular, we show that the empirical median run-time required for finding optimal solutions to so-called random uniform Euclidean (RUE) instances – one of the most widely studied classes of TSP instances – scales substantially better than Θ(2ⁿ)$\Theta (2^n)$ with the number n of cities to be visited. The Concorde solver, for which we achieved this result, is the best-performing exact TSP solver we are aware of, and has been applied to a broad range of real-world problems. Furthermore, we show that even when applied to a broad range of instances from the prominent TSPLIB benchmark collection for the TSP, Concorde exhibits run-times that are surprisingly consistent with our empirical model of Concorde’s scaling behaviour on RUE instances. This result suggests that the behaviour observed for the simple random structure underlying RUE is very similar to that obtained on the structured instances arising in various applications.     

On the complexity of some Euclidean optimal summing problems

The complexity status of several discrete optimization problems concerning the search for a subset of a finite set of Euclidean points (vectors) is analyzed. In the considered problems, the aim is to minimize objective functions depending either only on the norm of the sum of the elements from the subset or on this norm and the cardinality of the subset. It is proved that, if the dimension of the space is part of the input, then all analyzed problems are strongly NP-hard and, if the space dimension is fixed, then these problems are NP-hard even for dimension 2 (on a plane). It is shown that, if the coordinates of the input points are integer, then all the problems can be solved in pseudopolynomial time in the case of a fixed space dimension.     

A framework for finding robust optimal solutions over time

Dynamic optimization problems (DOPs) are those whose specifications change over time, resulting in changing optima. Most research on DOPs has so far concentrated on tracking the moving optima (TMO) as closely as possible. In practice, however, it will be very costly, if not impossible to keep changing the design when the environment changes. To address DOPs more practically, we recently introduced a conceptually new problem formulation, which is referred to as robust optimization over time (ROOT). Based on ROOT, an optimization algorithm aims to find an acceptable (optimal or sub-optimal) solution that changes slowly over time, rather than the moving global optimum. In this paper, we propose a generic framework for solving DOPs using the ROOT concept, which searches for optimal solutions that are robust over time by means of local fitness approximation and prediction. Empirical investigations comparing a few representative TMO approaches with an instantiation of the proposed framework are conducted on a number of test problems to demonstrate the advantage of the proposed framework in the ROOT context.     

On the complexity and approximability of some Euclidean optimal summing problems

The complexity status of several well-known discrete optimization problems with the direction of optimization switching from maximum to minimum is analyzed. The task is to find a subset of a finite set of Euclidean points (vectors). In these problems, the objective functions depend either only on the norm of the sum of the elements from the subset or on this norm and the cardinality of the subset. It is proved that, if the dimension of the space is a part of the input, then all these problems are strongly NP-hard. Additionally, it is shown that, if the space dimension is fixed, then all the problems are NP-hard even for dimension 2 (on a plane) and there are no approximation algorithms with a guaranteed accuracy bound for them unless P = NP. It is shown that, if the coordinates of the input points are integer, then all the problems can be solved in pseudopolynomial time in the case of a fixed space dimension.     

On the integrality ratio of the subtour LP for Euclidean TSP

A long standing conjecture says that the integrality ratio of the subtour LP for metric TSP is 4/3$4/3$. A well known family of graphic TSP instances achieves this lower bound asymptotically. For Euclidean TSP the best known lower bound on the integrality ratio was 8/7$8/7$. We improve this value by presenting a family of Euclidean TSP instances for which the integrality ratio of the subtour LP converges to 4/3.     

Approximation algorithms for the Euclidean bipartite TSP

We study approximation results for the Euclidean bipartite traveling salesman problem (TSP). We present the first worst-case examples, proving that the approximation guarantees of two known polynomial-time algorithms are tight. Moreover, we propose a new algorithm which displays a superior average case behavior indicated by computational experiments.     

On the expected number of optimal and near-optimal solutions to the Euclidean travelling salesman problem

An algorithm for empirically calculating the expected number of optimal and near-optimal solutions in a random Euclidean travelling salesman problem is presented. The algorithm is based on well known geometric properties of the optimal tour. For problems involving up to 15 points uniformily distributed in the unit square, experiments show this expected number to be extremely small.     

On the complexity of finding multi-constrained spanning trees

In this paper we present some new results concerning the classification of undirected spanning tree problems from the viewpoint of their computational complexity. Specifically, we study some problems asking for the existence in an undirected, unweighted graph, of a spanning tree satisfying one or several constraints. Thus we extend to the multi-constrained, unweighted case, the analysis that we have already made in a previous work for the one-constrained, weighted case. The problems are classified as solvable in polynomial time or NP-complete.     

Asymptotics for the Euclidean TSP with power weighted edges

Summary LetU ₁,...,U_n denote i.i.d. random variables with the uniform distribution on [0, 1]², and letT ²T²(U₁,...,U_n) denote the shortest tour throughU ₁,...,U_n with square-weighted edges. By drawing on the quasi-additive structure ofT ² and the boundary rooted dual process, it is shown that lim _n E T ²(U ₁,...,U_n)= for some finite constant .This work was supported in part by NSF Grant DMS-9200656, Swiss National Foundation Grant 21-298333.90, and the US Army Research Office through the Mathematical Sciences Institute of Cornell University, whose assistance is gratefully acknowledged     

A new algorithm for finding numerical solutions of optimal feedback control

Bing Sun Department of Mathematics, Beijing Institute of Technology, Beijing 100081, People's Republic of China and School of Computational and Applied Mathematics, University of the Witwatersrand, Wits 2050, Johannesburg, South Africa Email: bzguo{at}iss.ac.cn Received on March 15, 2007; Revision received October 17, 2007. A new algorithm for finding numerical solutions of optimal feedbackcontrol based on dynamic programming is developed. The algorithmis based on two observations: (1) the value function of theoptimal control problem considered is the viscosity solutionof the associated Hamilton–Jacobi–Bellman (HJB)equation and (2) the appearance of the gradient of the valuefunction in the HJB equation is in the form of directional derivative.The algorithm proposes a discretization method for seeking optimalcontrol–trajectory pairs based on a finite-differencescheme in time through solving the HJB equation and state equation.We apply the algorithm to a simple optimal control problem,which can be solved analytically. The consistence of the numericalsolution obtained to its analytical counterpart indicates theeffectiveness of the algorithm.     

On the complexity of some quadratic Euclidean 2-clustering problems

Some problems of partitioning a finite set of points of Euclidean space into two clusters are considered. In these problems, the following criteria are minimized: (1) the sum over both clusters of the sums of squared pairwise distances between the elements of the cluster and (2) the sum of the (multiplied by the cardinalities of the clusters) sums of squared distances from the elements of the cluster to its geometric center, where the geometric center (or centroid) of a cluster is defined as the mean value of the elements in that cluster. Additionally, another problem close to (2) is considered, where the desired center of one of the clusters is given as input, while the center of the other cluster is unknown (is the variable to be optimized) as in problem (2). Two variants of the problems are analyzed, in which the cardinalities of the clusters are (1) parts of the input or (2) optimization variables. It is proved that all the considered problems are strongly NP-hard and that, in general, there is no fully polynomial-time approximation scheme for them (unless P = NP).     

A time expanded matroid algorithm for finding optimal dynamic matroid intersections

The problems of finding a maximal cardinality or a maximal weight matroid intersection problem are well solved. We introduce dynamic versions of these problems and present a simple algorithm to solve them. The main idea of the solution procedure is to replace the dynamic problems by corresponding (static!) matroid intersection problems in larger matroids — the time expanded matroids. As an example we solve a dynamic spanning forest problem.

---

Zusammenfassung Die Probleme, Schnitte von Matroiden mit maximaler Kardinalität oder mit maximalem Gewicht zu finden, sind klassische Probleme der kombinatorischen Optimierung. In dieser Arbeit betrachten wir dynamische Versionen dieser Probleme und stellen einen einfachen Algorithmus zu deren Lösung vor. Die Idee dieses Lösungsverfahrens ist, die dynamischen Probleme durch entsprechende (statische!) Probleme in größeren Matroiden (time expanded matroids) zu ersetzen. Als Beispiel lösen wir die dynamische Version eines spanning forest Problems.

     

On a method for proving exact bounds on derivational complexity in thue systems

In this paper, the following system of substitutions in a 3-letter alphabet $$\sum { = \left\langle {\left. {a,b,c} \right|a^2 \to bc,b^2 \to ac,c^2 \to ab} \right\rangle }$$ is considered. A detailed proof of results that were described briefly in the author’s paper [1] is presented. They give an answer to the specific question on the possibility of giving a polynomial upper bound for the lengths of derivations from a given word in the system Σ stated in the literature. The maximal possible number of steps in derivation sequences starting from a given word W is denoted by D(W). The maximum of D(W) for all words of length |W| = l is denoted by D(l). It is proved that the function D(W) on wordsW of given length |W| = m+2 reaches its maximum only on words of the form W = c ² b ^m and W = b ^m a ². For these words, the following precise estimate is established: where ?3m ²/2? for odd |m| is the round-up of 3m ²/2 to the nearest integer.     

On complexity of optimal recombination for flowshop scheduling problems

Under study is the complexity of optimal recombination for various flowshop scheduling problems with the makespan criterion and the criterion of maximum lateness. The problems are proved to be NP-hard, and a solution algorithm is proposed. In the case of a flowshop problem on permutations, the algorithm is shown to have polynomial complexity for “almost all” pairs of parent solutions as the number of jobs tends to infinity.     

On the $${\mathcal {}}$$-free extension complexity of the TSP

It is known that the extension complexity of the TSP polytope for the complete graph \(K_n\) is exponential in n even if the subtour inequalities are excluded. In this article we study the polytopes formed by removing other subsets \({\mathcal {H}}\) of facet-defining inequalities of the TSP polytope. In particular, we consider the case when \({\mathcal {H}}\) is either the set of blossom inequalities or the simple comb inequalities. These inequalities are routinely used in cutting plane algorithms for the TSP. We show that the extension complexity remains exponential even if we exclude these inequalities. In addition we show that the extension complexity of polytope formed by all comb inequalities is exponential. For our proofs, we introduce a subclass of comb inequalities, called (h, t)-uniform inequalities, which may be of independent interest.     

On optimality conditions for quasi-relative efficient solutions in set-valued optimization

In the paper, we establish necessary and sufficient optimality conditions for quasi-relative efficient solutions of a constrained set-valued optimization problem using the Lagrange multipliers. Many examples are given to show that our results and their applications are more advantageous than some existing ones in the literature.