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.     

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.     

A general method for finding the optimal threshold in discrete time

We develop an approach for solving one-sided optimal stopping problems in discrete time for general underlying Markov processes on the real line. The main idea is to transform the problem into an auxiliary problem for the ladder height variables. In case that the original problem has a one-sided solution and the auxiliary problem has a monotone structure, the corresponding myopic stopping time is optimal for the original problem as well. This elementary line of argument directly leads to a characterization of the optimal boundary in the original problem. The optimal threshold is given by the threshold of the myopic stopping time in the auxiliary problem. Supplying also a sufficient condition for our approach to work, we obtain solutions for many prominent examples in the literature, among others the problems of Novikov-Shiryaev, Shepp-Shiryaev, and the American put in option pricing under general conditions. As a further application we show that for underlying random walks (and Lévy processes in continuous time), general monotone and log-concave reward functions g lead to one-sided stopping problems.     

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 the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances

We investigate the empirical performance of the long-standing state-of-the-art exact TSP solver Concorde on various classes of Euclidean TSP instances and show that, surprisingly, the time spent until the first optimal solution is found accounts for a large fraction of Concorde’s overall running time. This finding holds for the widely studied random uniform Euclidean (RUE) instances as well as for several other widely studied sets of Euclidean TSP instances. On RUE instances, the median fraction of Concorde’s total running time spent until an optimal solution is found ranges from 0.77 for \(n=500\) to 0.97 for \(n=3{,}500\); on TSPLIB, National and VLSI instances, we pegged it at 0.86, 0.74 and 0.61, respectively, with a tendency of even smaller values for larger instances.     

A robust approach for finding all well-separated solutions of sparse systems of nonlinear equations

Tearing is a long-established decomposition technique, widely adapted across many engineering fields. It reduces the task of solving a large and sparse nonlinear system of equations to that of solving a sequence of low-dimensional ones. The most serious weakness of this approach is well-known: It may suffer from severe numerical instability. The present paper resolves this flaw for the first time. The new approach requires reasonable bound constraints on the variables. The worst-case time complexity of the algorithm is exponential in the size of the largest subproblem of the decomposed system. Although there is no theoretical guarantee that all solutions will be found in the general case, increasing the so-called sample size parameter of the method improves robustness. This is demonstrated on two particularly challenging problems. Our first example is the steady-state simulation a challenging distillation column, belonging to an infamous class of problems where tearing often fails due to numerical instability. This column has three solutions, one of which is missed using tearing, but even with problem-specific methods that are not based on tearing. The other example is the Stewart–Gough platform with 40 real solutions, an extensively studied benchmark in the field of numerical algebraic geometry. For both examples, all solutions are found with a fairly small amount of sampling.     

Infeasibility spheres for finding robust solutions of blending problems with quadratic constraints

The blending problem is studied as a problem of finding cheap robust feasible solutions on the unit simplex fulfilling linear and quadratic inequalities. Properties of a regular grid over the unit simplex are discussed. Several tests based on spherical regions are described and evaluated to check the feasibility of subsets and robustness of products. These tests have been implemented into a Branch-and-Bound algorithm that reduces the set of points evaluated on the regular grid. The whole is illustrated numerically.     

Some characterizations of robust optimal solutions for uncertain convex optimization problems

In this paper, we consider robust optimal solutions for a convex optimization problem in the face of data uncertainty both in the objective and constraints. By using the properties of the subdifferential sum formulae, we first introduce a robust-type subdifferential constraint qualification, and then obtain some completely characterizations of the robust optimal solution of this uncertain convex optimization problem. We also investigate Wolfe type robust duality between the uncertain convex optimization problem and its uncertain dual problem by proving duality between the deterministic robust counterpart of the primal model and the optimistic counterpart of its dual problem. Moreover, we show that our results encompass as special cases some optimization problems considered in the recent literature.     

Martingale optimal transport and robust hedging in continuous time

The duality between the robust (or equivalently, model independent) hedging of path dependent European options and a martingale optimal transport problem is proved. The financial market is modeled through a risky asset whose price is only assumed to be a continuous function of time. The hedging problem is to construct a minimal super-hedging portfolio that consists of dynamically trading the underlying risky asset and a static position of vanilla options which can be exercised at the given, fixed maturity. The dual is a Monge–Kantorovich type martingale transport problem of maximizing the expected value of the option over all martingale measures that have a given marginal at maturity. In addition to duality, a family of simple, piecewise constant super-replication portfolios that asymptotically achieve the minimal super-replication cost is constructed.     

A linear-time algorithm for finding optimal vehicle refueling policies

We explore a fixed-route vehicle refueling problem as a special case of the inventory-capacitated lot-sizing problem, and present a linear-time greedy algorithm for finding optimal refueling policies.     

A recipe for finding good solutions to MINLPs

Finding good (or even just feasible) solutions for Mixed-Integer Nonlinear Programming problems independently of the specific problem structure is a very hard but practically important task, especially when the objective and/or the constraints are nonconvex. With this goal in mind, we present a general-purpose heuristic based on Variable Neighborhood Search, Local Branching, a local Nonlinear Programming algorithm and Branch-and-Bound. We test the proposed approach on MINLPLib, comparing with several existing heuristic and exact methods. An implementation of the proposed heuristic is freely available and can employ all NLP/MINLP solvers with an AMPL interface as the main search tools.     

A framework for robust and flexible optimisation using metaheuristics

This is a summary of the most important results presented in the authors PhD thesis. This thesis, written in English, was defended on 13 June 2003 and supervised by Johan Springael and Gerrit K. Janssens. A copy is available from the author upon request. This PhD thesis focuses on stochastic problems and develops a framework to find robust and flexible solutions of such problems. The framework is applied to several well-known problems in the realm of supply chain design. Besides this framework, the thesis contains several other important contributions. A new type of robustness and flexibility is proposed, that expresses the need for solutions to remain approximately the same when changes occur in the problem data. Several distance measures are developed to calculate the distance (or similarity) between solutions of different permutation type problems. A new type of genetic algorithm is also proposed, that uses a distance measure to maintain a diverse population of high-quality solutions.Received: June 2003     

An optimal time algorithm for finding a maximum weight independent set in a tree

The maximum weight independent set problem for a general graph is NP-hard. But for some special classes of graphs, polynomial time algorithms do exist for solving it. Based on the divide-and-conquer strategy, Pawagi has presented anO(|V|log|V|) time algorithm for solving this problem on a tree. In this paper, we propose anO(|V|) time algorithm to improve Pawagi's result. The proposed algorithm is based on the dynamic programming strategy and is time optimal within a constant factor.     

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.     

Bilevel problems over polyhedra with extreme point optimal solutions

Bilevel programming involves two optimization problems where the constraint region of the upper level problem is implicitly determined by another optimization problem. In this paper we focus on bilevel problems over polyhedra with upper level constraints involving lower level variables. On the one hand, under the uniqueness of the optimal solution of the lower level problem, we prove that the fact that the objective functions of both levels are quasiconcave characterizes the property of the existence of an extreme point of the polyhedron defined by the whole set of constraints which is an optimal solution of the bilevel problem. An example is used to show that this property is in general violated if the optimal solution of the lower level problem is not unique. On the other hand, if the lower level objective function is not quasiconcave but convex quadratic, assuming the optimistic approach we prove that the optimal solution is attained at an extreme point of an ??enlarged?? polyhedron.     

A robust structured preconditioner for time-harmonic parabolic optimal control problems

We consider the iterative solution of optimal control problems constrained by the time-harmonic parabolic equations. Due to the time-harmonic property of the control equations, a suitable discretization of the corresponding optimality systems leads to a large complex linear system with special two-by-two block matrix of saddle point form. For this algebraic system, an efficient preconditioner is constructed, which results in a fast Krylov subspace solver, that is robust with respect to the mesh size, frequency, and regularization parameters. Furthermore, the implementation is straightforward and the computational complexity is of optimal order, linear in the number of degrees of freedom. We show that the eigenvalue distribution of the corresponding preconditioned matrix leads to a condition number bounded above by 2. Numerical experiments confirming the theoretical derivations are presented, including comparisons with some other existing preconditioners.     

A constructive method for finding periodic solutions of differential systems

Coefficient conditions for the existence of periodic solutions of degenerate systems of differential equations are obtained. Iterative algorithms for finding these solutions are developed.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 47, No. 4, pp. 468–476, April, 1995.     

A cubic time algorithm for finding the principal solution to Sylvester matrix equations over (max, +)

We propose an algorithm for finding the so-called principal solution of the Sylvester matrix equation over max-plus algebra. The derivation of our algorithm is based on the concept of tropical tensor product introduced by Butkovi? and Fiedler. Our algorithm reduces the computational cost of finding the principal solution from quartic to cubic. It also reduces the space complexity from quartic to quadratic. Since matrix–matrix multiplication is the most important ingredient of our proposed technique, we show how to use column-oriented matrix multiplications in order to speed-up MATLAB implementation of our algorithm. Finally, we illustrate our results and discuss the connection with the residuation theory.     

On finding robust approximate inverses for large sparse matrices

This paper presents a method based on matrix-matrix multiplication concepts for determining the approximate (sparse) inverses of sparse matrices. The suggested method is a development on the well-known Schulz iteration and it can successfully be combined with iterative solvers and sparse approximation techniques as well. A detailed discussion on the convergence rate of this scheme is furnished. Results of numerical experiments are also reported to illustrate the performance of the proposed method.