A restricted Lagrangean approach to the traveling salesman problem

We describe an algorithm for the asymmetric traveling salesman problem (TSP) using a new, restricted Lagrangean relaxation based on the assignment problem (AP). The Lagrange multipliers are constrained so as to guarantee the continued optimality of the initial AP solution, thus eliminating the need for repeatedly solving AP in the process of computing multipliers. We give several polynomially bounded procedures for generating valid inequalities and taking them into the Lagrangean function with a positive multiplier without violating the constraints, so as to strengthen the current lower bound. Upper bounds are generated by a fast tour-building heuristic. When the bound-strengthening techniques are exhausted without matching the upper with the lower bound, we branch by using two different rules, according to the situation: the usual subtour breaking disjunction, and a new disjunction based on conditional bounds. We discuss computational experience on 120 randomly generated asymmetric TSP's with up to 325 cities, the maximum time used for any single problem being 82 seconds. This is a considerable improvement upon earlier methods. Though the algorithm discussed here is for the asymmetric TSP, the approach can be adapted to the symmetric TSP by using the 2-matching problem instead of AP.Research supported by the National Science Foundation through grant no. MCS76-12026 A02 and the U.S. Office of Naval Research through contract no. N0014-75-C-0621 NR 047-048.     

Recursive lower and dual upper bounds for Bermudan-style options

Although Bermudan options are routinely priced by simulation and least-squares methods using lower and dual upper bounds, the latter are hardly optimized. In this paper, we optimize recursive upper bounds, which are more tractable than the original/nonrecursive ones, and derive two new results: (1) An upper bound based on (a martingale that depends on) stopping times is independent of the next-stage exercise decision and hence cannot be optimized. Instead, we optimize the recursive lower bound, and use its optimal recursive policy to evaluate the upper bound as well. (2) Less time-intensive upper bounds that are based on a continuation-value function only need this function in the continuation region, where this continuation value is less nonlinear and easier to fit (than in the entire support). In the numerical exercise, both upper bounds improve over state-of-the-art methods (including standard least-squares and pathwise optimization). Specifically, the very small gap between the lower and the upper bounds derived in (1) implies the recursive policy and the associated martingale are near optimal, so that these two specific lower/upper bounds are hard to improve, yet the upper bound is tighter than the lower bound.     

Steplengths in the extragradient type methods

The extragradient type methods are a class of efficient direct methods. For solving monotone variational inequalities, these methods only require function evaluation, and therefore are widely applied to black-box models. In this type of methods, the distance between the iterate and a fixed solution point decreases by iterations. Furthermore, in each iteration, the negative increment of such squared distance has a differentiable concave lower bound function without requiring any solution in its formula. In this paper, we investigate some properties for the lower bound. Our study reveals that the lower bound affords a steplength domain which guarantees the convergence of the entire algorithm. Based on these results, we present two new steplengths. One involves the projection onto the tangent cone without line search, while the other can be computed via searching the positive root of a one dimension concave lower bound function. Our preliminary numerical results confirm and illustrate the attractiveness of our contributions.     

Project Scheduling with Resource Constraints Using Branch and Bound Methods

The problem of minimising the overall duration of a project subject to constraints on the availability of resources is considered with particular reference to the use of branch and bound methods. A new resource based bound, new dominance rules and an innovatory network breakdown technique which preserves optimality are reported. Computational experience and comparisons with schedules obtained by decision rule methods are given.     

Experiments with a new selection criterion in a fast interval optimization algorithm

Usually, interval global optimization algorithms use local search methods to obtain a good upper (lower) bound of the solution. These local methods are based on point evaluations. This paper investigates a new local search method based on interval analysis information and on a new selection criterion to direct the search. When this new method is used alone, the guarantee to obtain a global solution is lost. To maintain this guarantee, the new local search method can be incorporated to a standard interval GO algorithm, not only to find a good upper bound of the solution, but also to simultaneously carry out part of the work of the interval B&B algorithm. Moreover, the new method permits improvement of the guaranteed upper bound of the solution with the memory requirements established by the user. Thus, the user can avoid the possible memory problems arising in interval GO algorithms, mainly when derivative information is not used. The chance of reaching the global solution with this algorithm may depend on the established memory limitations. The algorithm has been evaluated numerically using a wide set of test functions which includes easy and hard problems. The numerical results show that it is possible to obtain accurate solutions for all the easy functions and also for the investigated hard problems.     

混水平均匀设计的构造

我们用离散偏差来度量部分因子设计的均匀性,本文的目的在于寻找一些构造混水平均匀设计的方法,这些方法比文献中已有的方法更简单且计算成本更低.我们得到了离散偏差的一个下界,如果一个U 型设计的离散偏差值达到这个下界,那么该设计是—个均匀设计.我们建立了均匀设计与组合设计理论中一致可分解设计之间的联系.通过一致可分解设计,我们提出了一些构造均匀设计的新方法,同时也给出了许多均匀设计存在的无穷类.     

On the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems

New observations are made about two lower bound schemes for single-machine min-sum scheduling problems. We find that the strongest bound of those provided by transportation problem relaxations can be computed by solving a linear program. We show the equivalence of this strongest bound and the bound provided by the LP relaxation of the time-indexed integer programming formulation. These observations lead to a new lower bound scheme that yields fast approximation of the time-indexed bound. Several techniques are developed to facilitate the effective use of the new lower bound in branch-and-bound. Numerical experiments are conducted on 375 benchmark problems of the total weighted tardiness problem from OR-Library. Results obtained with our new method are spectacular; we are able to solve all 125 open problems to optimality.     

Strong solutions and weak-strong uniqueness for the nonhomogeneous Navier-Stokes system

This article is devoted to the study of the nonhomogeneous incompressible Navier-Stokes system in dimension d ≥ 3. We use new a priori estimates, which enable us to deal with low-regularity data and vanishing density. In particular, we prove new well-posedness results which improve the results of Danchin [6] by considering a less regular initial density, without a lower bound. Also, we obtain the first uniqueness criterion for weak solutions which is at the scaling of the equation.     

Fractal methods and the problem of estimating scaling exponents: A new approach based on upper and lower linear bounds

The characterization of irregular objects with fractal methods often leads to the estimation of the slope of a function which is plotted versus a scale parameter. The slope is usually obtained with a linear regression. The problem is that the fit is usually not acceptable from the statistical standpoint. We propose a new approach in which we use two straight lines to bound the data from above and from below. We call these lines the upper and lower linear bounds. We propose to define these bounds as the solution of an optimization problem. We discuss the solution of this problem and we give an algorithm to obtain its solution. We use the difference between the upper and lower linear bounds to define a measure of the degree of linearity in the scaling range. We illustrate our method by analyzing the fluctuations of the variogram in a microresistivity well log from an oil reservoir in the North Sea.     

Inequalities for the capacity of non-contractible annuli on cylinders of constant and variable negative curvature

We give elementary estimates for the capacity of non-contractible annuli on cylinders and provide examples, where these inequalities are sharp. Here the lower bound depends only on the area of the annulus. To obtain this result we use projection of gradients on curves to obtain a lower bound on the capacity, which we call directional capacity. In the case of constant curvature we then apply a symmetrization process that results in an annulus of minimal directional capacity. For this annulus the lower bound on the capacity is sharp. In the case of variable negative curvature we obtain the lower bound by constructing a comparison annulus with the same area but lower directional capacity on a cylinder of constant curvature. The methods developed here have been applied to estimate the energy of harmonic forms on Riemann surfaces in Muetzel (Math Zeitschrift, 2012, arXiv:1202.0782).     

O the volume growth of the hyperbolic regular $$\varvec{}$$-simplex

In this paper we give lower and upper bounds for the volume growth of a regular hyperbolic simplex, namely for the ratio of the n-dimensional volume of a regular simplex and the \((n-1)\)-dimensional volume of its facets. In addition to the methods of U. Haagerup and M. Munkholm we use a third volume form based on the hyperbolic orthogonal coordinates of a body. In the case of the ideal, regular simplex our upper bound gives the best known upper bound. On the other hand, also in the ideal case our general lower bound, improved the best known one for \(n=3\).     

Irregularities of distribution with respect to strips

Summary A lower bound is established for the strip discrepancy of a broad class of point distributions. The bound implies unbounded strip discrepancy for equally weighted point distributions under favorable conditions. The methods of proof use notions from integral geometry.     

New convergent heuristics for 0–1 mixed integer programming

Several hybrid methods have recently been proposed for solving 0–1 mixed integer programming problems. Some of these methods are based on the complete exploration of small neighborhoods. In this paper, we present several convergent algorithms that solve a series of small sub-problems generated by exploiting information obtained from a series of relaxations. These algorithms generate a sequence of upper bounds and a sequence of lower bounds around the optimal value. First, the principle of a linear programming-based algorithm is summarized, and several enhancements of this algorithm are presented. Next, new hybrid heuristics that use linear programming and/or mixed integer programming relaxations are proposed. The mixed integer programming (MIP) relaxation diversifies the search process and introduces new constraints in the problem. This MIP relaxation also helps to reduce the gap between the final upper bound and lower bound. Our algorithms improved 14 best-known solutions from a set of 108 available and correlated instances of the 0–1 multidimensional Knapsack problem. Other encouraging results obtained for 0–1 MIP problems are also presented.     

A New Estimate on the Two-Dimensional Indirect Coulomb Energy

We prove a new lower bound on the indirect Coulomb energy in two-dimensional quantum mechanics in terms of the single particle density of the system. The new universal lower bound is an alternative to the Lieb–Solovej–Yngvason bound with a smaller constant, ${C = (4/3)^{3/2} \sqrt{5 \pi -1} \approx 5.90 < C_{\rm LSY} = 192 \sqrt{2 \pi} \approx 481.27}$ , which also involves an additive gradient energy term of the single particle density.     

Error bounds for quadrature methods involving lower order derivatives

Quadrature methods for approximating the definite integral of a function f(t) over an interval [a,b] are in common use. Examples of such methods are the Newton–Cotes formulas (midpoint, trapezoidal and Simpson methods etc.) and the Gauss–Legendre quadrature rules, to name two types of quadrature. Error bounds for these approximations involve higher order derivatives. For the Simpson method, in particular, the error bound involves a fourth-order derivative. Discounting the fact that calculating a fourth-order derivative requires a lot of differentiation, the main concern is that an error bound for the Simpson method, for example, is only relevant for a function that is four times differentiable, a rather stringent condition. This paper caters for functions for which derivatives exist only of order lower than normally required. A number of quadrature methods are considered and error bounds derived involving only lower order derivatives that can be used depending on the smoothness of the function.     

On the average‐case complexity of Shellsort

We prove a lower bound expressed in the increment sequence on the average‐case complexity of the number of inversions of Shellsort. This lower bound is sharp in every case where it could be checked. A special case of this lower bound yields the general Jiang‐Li‐Vitányi lower bound. We obtain new results, for example, determining the average‐case complexity precisely in the Yao‐Janson‐Knuth 3‐pass case.     

NEW LOWER BOUNDS FOR LEE DISCREPANCY ON TWO AND THREE MIXED LEVELS FACTORIALS

The objective of this paper is to study the issue of uniformity on asymmetrical designs with two and three mixed levels in terms of Lee discrepancy.Based on the known formulation,we present a new lower bound of Lee discrepancy of fractional factorial designs with two and three mixed levels.Our new lower bound is sharper and more valid than other existing lower bounds in literature,which is a useful complement to the lower bound theory of discrepancies.     

Multi-dimensional pruning from the Baumann point in an Interval Global Optimization Algorithm

A new pruning method for interval branch and bound algorithms is presented. In reliable global optimization methods there are several approaches to make the algorithms faster. In minimization problems, interval B&B methods use a good upper bound of the function at the global minimum and good lower bounds of the function at the subproblems to discard most of them, but they need efficient pruning methods to discard regions of the subproblems that do not contain global minimizer points. The new pruning method presented here is based on the application of derivative information from the Baumann point. Numerical results were obtained by incorporating this new technique into a basic Interval B&B Algorithm in order to evaluate the achieved improvements. This work has been supported by the Ministry of Education and Science of Spain through grants TIC 2002-00228, TIN2005-00447, and research project SEJ2005-06273 and by the Integral Action between Spain and Hungary by grant HH2004-0014. Boglárka Tóth: On leave from the Research Group on Artificial Intelligence of the Hungarian Academy of Sciences and the University of Szeged, H-6720 Szeged, Aradi vértanúk tere 1., Hungary.     

Remarks on the lower bounds for the average genus

Let G be a graph of maximum degree at most four. By using the overlap matrix method which is introduced by B. Mohar, we show that the average genus of G is not less than 1/3 of its maximum genus, and the bound is best possible. Also, a new lower bound of average genus in terms of girth is derived.     

Sequential change-point detection for mixing random sequences under composite hypotheses

The problem of sequential detection of a change-point in the density function of one-dimensional distribution of observations from a mixing random sequence is considered when both before and after a change-point this density function belongs to a certain family of distributions, i.e. in the situation of composite hypotheses. A new quality criterion for change-point detection is proposed. The asymptotic a priori lower bound for this criterion is proved for wide class of methods of change-point detection. An asymptotically optimal method of change-point detection is proposed for which this lower bound is attained asymptotically. In particular, for the case of a simple hypothesis before a change-point, this method coincides with the generalized cumulative sums (CUSUM) method.