A backbone based TSP heuristic for large instances

We introduce a reduction technique for large instances of the traveling salesman problem (TSP). This approach is based on the observation that tours with good quality are likely to share many edges. We exploit this observation by neglecting the less important tour space defined by the shared edges, and searching the important tour subspace in more depth. More precisely, by using a basic TSP heuristic, we obtain a set of starting tours. We call the set of edges which are contained in each of these starting tours as pseudo-backbone edges. Then we compute the maximal paths consisting only of pseudo-backbone edges, and transform the TSP instance to another one with smaller size by contracting each such path to a single edge. This reduced TSP instance can be investigated more intensively, and each tour of the reduced instance can be expanded to a tour of the original instance. Combining our reduction technique with the currently leading TSP heuristic of Helsgaun, we experimentally investigate 32 difficult VLSI instances from the well-known TSP homepage. In our experimental results we set world records for seven VLSI instances, i.e., find better tours than the best tours known so far (two of these world records have since been improved upon by Keld Helsgaun and Yuichi Nagata, respectively). For the remaining instances we find tours that are equally good or only slightly worse than the world record tours.     

A characterization of ill-posed data instances for convex programming

Given a data instance of a convex program, we provide a collection of conic linear systems such that the data instance is ill-posed if and only if at least one of those systems is satisfied. This collection of conic linear systems is derived from a characterization of the boundary of the set of primal and dual feasible data instances associated with the given convex program. Received: September 1998 / Accepted: August 2000?Published online October 26, 2001     

A two-level network for recycling sand: A case study

In the Netherlands, the recycling of construction waste and in particular of sand creates an important logistic problem. New legislation ensures that disposal is reduced to a minimal level and this incentives recycling. Such measures cause an increase on the offer of sand (a subproduct of recycling construction waste) and create the need for establishing an efficient sand network. The sand problem falls into the field of reverse logistics management since it deals with processing returned goods (sieved sand). We propose a two-level location model for the sand problem and consider its optimization using heuristic procedures. The results obtained for the sand recycling network in the Netherlands are summarized.     

Computing statistics for Hamiltonian systems: A case study

We present the results of a set of numerical experiments designed to investigate the appropriateness of various integration schemes for molecular dynamics simulations. In particular, we wish to identify which numerical methods, when applied to an ergodic Hamiltonian system, sample the state-space in an unbiased manner. We do this by describing two Hamiltonian system for which we can analytically compute some of the important statistical features of its trajectories, and then applying various numerical integration schemes to them. We can then compare the results from the numerical simulation against the exact results for the system and see how closely they agree. The statistic we study is the empirical distribution of particle velocity over long trajectories of the systems. We apply four methods: one symplectic method (Störmer–Verlet) and three energy-conserving step-and-project methods. The symplectic method performs better on both test problems, accurately computing empirical distributions for all step-lengths consistent with stability. Depending on the test system and the method, the step-and-project methods are either no longer ergodic for any step length (thus giving the wrong empirical distribution) or give the correct distribution only in the limit of step-size going to zero.     

Hard satisfiable instances for DPLL-type algorithms

We address lower bounds on the time complexity of algorithms solving the propositional satisfiability problem. Namely, we consider two DPLL-type algorithms, enhanced with the unit clause and pure literal heuristics. Exponential lower bounds for solving satisfiability on provably satisfiable formulas are proven. Bibliography: 11 titles.Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 293, 2002, pp. 139–148.This revised version was published online in April 2005 with a corrected cover date and article title.     

Generating hard instances for robust combinatorial optimization

While research in robust optimization has attracted considerable interest over the last decades, its algorithmic development has been hindered by several factors. One of them is a missing set of benchmark instances that make algorithm performance better comparable, and makes reproducing instances unnecessary. Such a benchmark set should contain hard instances in particular, but so far, the standard approach to produce instances has been to sample values randomly from a uniform distribution.In this paper we introduce a new method to produce hard instances for min-max combinatorial optimization problems, which is based on an optimization model itself. Our approach does not make any assumptions on the problem structure and can thus be applied to any combinatorial problem. Using the Selection and Traveling Salesman problems as examples, we show that it is possible to produce instances which are up to 500 times harder to solve for a mixed-integer programming solver than the current state-of-the-art instances.     

Structuring decision problems: A case study and reflections for practitioners

This article reviews several approaches to problem structuring and, in particular, the three-step structuring process for decision analysis proposed by von Winterfeldt and Edwards: (1) identifying the problem; (2) selecting an appropriate analytical approach; (3) developing the a detailed analytic structure. This three-step process is re-examined in the context of a decision analysis of alternative policies to reduce electromagnetic field exposure from electric power lines. This decision analysis was conducted for a public health organization funded by the California Public Utilities Commission and it was scrutinized throughout by interested stakeholders. As a result a significant effort went into structuring this problem appropriately, with some successes and some missteps. The article extracts lessons from this experience, updating existing guidance on structuring problems for decision analysis, and concluding with some general insights for problem structuring.     

Universal graphs without instances of CH: Revisited

We give a complete proof of the consistency of the existence of a universal graph of powerλ, whereκ =κ ^<κ <λ = cfλ < 2 ^κ are arbitrary. The author would like to thank the NSF for partially supporting this research, Alice Leonhardt for the beautiful typing, and M. Kojman for proofreading. Publication No. 175A. The proof in the second section of [9] is flawed.     

Hypoelliptic random heat kernels: A case study

We consider the fundamental solution of a simple hypoelliptic stochastic partial differential equation in which the first-order term is modulated by white noise. We derive some short-time asymptotic formulæ. We discover that the form of the dominant short-time asymptotics depends nontrivially upon the interplay between the geometry of the noisy first-order term and the geometry defined by the hypoelliptic operator.

     

Tanker chartering: A system dynamics case study

This paper describes a practical system dynamics case study. It attempts to show how this OR technique can be applied to a practical problem and the results which it can, and cannot, be expected to give.Although the paper is based on a real project, the details have been altered for commercial secrecy, and the emphasis in this paper is, for the same reason, rather different from that of the original work. The aim of the paper is, therefore, to give enough of a “real” background to contrast the industrial application of SD with some of its other applications.For the sake of reasonable brevity, the emphasis in this paper is on the managerial viewpoint, and the extent to which an SD model provides helpful answers to managerial questions. The model paper is described only briefly as full details, and a model listing are given by Coyle. Some other aspects of the system are treated by Winch.     

A methodology for sensitivity analysis in three-criteria problems: A case study in municipal management

This paper describes part of an on-going research project studying the issues of the application of Multicriteria Decision Aid Methodologies in real case-studies at the local level of the Portuguese Public Administration.In a first part, it address the complexity of decision situations in municipal management in general and the significance of decision analysis, namely multicriteria evaluation procedures, in conducting decision aid processes in that environment (Section 1).In a second part, a case study is described (Section 2), followed by its discussion in the ‘space of the weights’ in the context of different particular types of possible problem formulations (Section 3). For this purpose, an extension of Triangular Decision Technique is first proposed, followed by the presentation of a new Outranking approach, designated by ‘Outweigh’ analysis, which will permit the enrichment of the discussion.     

An optimization approach for communal home meal delivery service: A case study

This paper is the first to discuss the communal home meal delivery problem. The problem can be modelled as a multiple travelling salesman problem with time windows, that is closely related to the well-studied vehicle routing problem with time windows. Experimental results are reported for a real-life case study from Central Finland over several alternative scenarios using the SPIDER commercial solver. The comparison with current practice reveals that a significant savings potential can be obtained using off-the-shelf optimization tools. As such, the potential for supporting real-life communal routing problems can be considered to be important for VRP practitioners.     

SpeeDP: an algorithm to compute SDP bounds for very large Max-Cut instances

We consider low-rank semidefinite programming (LRSDP) relaxations of unconstrained $\{-1,1\}$ quadratic problems (or, equivalently, of Max-Cut problems) that can be formulated as the non-convex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function and we define an efficient and globally convergent algorithm, called SpeeDP, for finding critical points of the LRSDP problem. We provide evidence of the effectiveness of SpeeDP by comparing it with other existing codes on an extended set of instances of the Max-Cut problem. We further include SpeeDP within a simply modified version of the Goemans?CWilliamson algorithm and we show that the corresponding heuristic SpeeDP-MC can generate high-quality cuts for very large, sparse graphs of size up to a million nodes in a few hours.     

Forecasting demand for single-period products: A case study in the apparel industry

The problem considered is that of forecasting demand for single-period products before the period starts. We study this problem for the case of a mail order apparel company that needs to order its products pre-season. The lack of historical demand data implies that other sources of data are needed. Advance order data can be obtained by allowing a selected group of customers to pre-order at a discount from a preview catalogue. Judgments can be obtained from purchase managers or other company experts. In this paper, we compare several existing and new forecasting methods for both sources of data. The methods are generic and can be used in any single-period problem in the apparel or fashion industries. Among the pre-order based methods, a novel ‘top-flop’ approach provides promising results. For a small group of products from the case company, expert judgment methods perform better than the methods based on advance demand information. The comparative results are obviously restricted to the specific case study, and additional testing is required to determine whether they are valid in general.     

Velocity inversion: A case study in infinite-dimensional optimization

The goal of seismic velocity inversion is the estimation of seismic wave velocities inside the earth by attempting to predict, in a least-error sense, seismic waveforms measured at its surface. We present velocity inversion as a case study in the various infinite-dimensional pathologies which may afflict practically important problems of distributed parameter identification, treated as optimization problems in function spaces. These features differentiate various problem formulations far beyond the degree one would expect for finite- (small-) dimensional problems. We illustrate this differentiation by comparing the characteristics of three different least-squares formulations of velocity inversion.     

Aligning simulation models: A case study and results

This paper develops the concepts and methods of a process we will call “alignment of computational models” or “docking” for short. Alignment is needed to determine whether two models can produce the same results, which in turn is the basis for critical experiments and for tests of whether one model can subsume another. We illustrate our concepts and methods using as a target a model of cultural transmission built by Axelrod. For comparison we use the Sugarscape model developed by Epstein and Axtell. The two models differ in many ways and, to date, have been employed with quite different aims. The Axelrod model has been used principally for intensive experimentation with parameter variation, and includes only one mechanism. In contrast, the Sugarscape model has been used primarily to generate rich “artificial histories”, scenarios that display stylized facts of interest, such as cultural differentiation driven by many different mechansims including resource availability, migration, trade, and combat. The Sugarscape model was modified so as to reproduce the results of the Axelrod cultural model. Among the questions we address are: what does it mean for two models to be equivalent, how can different standards of equivalence be statistically evaluated, and how do subtle differences in model design affect the results? After attaining a “docking” of the two models, the richer set of mechanisms of the Sugarscape model is used to provide two experiments in sensitivity analysis for the cultural rule of Axelrod's model. Our generally positive experience in this enterprise has suggested that it could be beneficial if alignment and equivalence testing were more widely practiced among computational modelers.     

Truncation error in grid generation: A case study

Theoretical proofs state that the planar Winslow or homogenous Thompson–Thames–Mastin (hTTM) map is a diffeomorphism, yet numerical solutions to the hTTM equations produce folded grids on the so-called “horseshoe” domain. A quasi-analytic solution to the horseshoe problem is constructed to demonstrate that folding is due to truncation error effects. Higher-order difference methods are also explored. © 1995 John Wiley & Sons, Inc.