Problem space local search for number partitioning

We show how simple and effective metaheuristics can be developed for the number partitioning problem using the problem space approach [1]. In a previous application of local search to number partitioning [2], it was found that the performance of simulated annealing used in conjunction with swap neighborhoods was disappointing relative to the differencing heuristic of Karmarkar and Karp [3]. Using problem space neighborhoods as an alternative to swapping, we empirically demonstrate several orders of magnitude improvement over the differencing algorithm, albeit with greater computation time. This improvement in performance comes as little surprise since a modified version of the differencing heuristic is explicitly embedded in the problem space algorithm.     

A branch and bound algorithm for bound constrained optimization problems without derivatives

In this paper, we give a new branch and bound algorithm for the global optimization problem with bound constraints. The algorithm is based on the use of inclusion functions. The bounds calculated for the global minimum value are proved to be correct, all rounding errors are rigorously estimated. Our scheme attempts to exclude most uninteresting parts of the search domain and concentrates on its promising subsets. This is done as fast as possible (by involving local descent methods), and uses little information as possible (no derivatives are required). Numerical results for many well-known problems as well as some comparisons with other methods are given.     

Замечания о порядке погрещности интерполяции

.      

Studying the Complexity of Global Verification for NP-Hard Discrete Optimization Problems

This paper examines the complexity of global verification for MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, and Traveling Salesman Problem. These results are obtained by adaptations of the transformations that prove such problems to be NP-complete. The class of problems PGS is defined to be those discrete optimization problems for which there exists a polynomial time algorithm such that given any solution , either a solution can be found with a better objective function value or it can be concluded that no such solution exists and is a global optimum. This paper demonstrates that if any one of MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, or Traveling Salesman Problem are in PGS, then P=NP.     

On affine scaling algorithms for nonconvex quadratic programming

We investigate the use of interior algorithms, especially the affine-scaling algorithm, to solve nonconvex — indefinite or negative definite — quadratic programming (QP) problems. Although the nonconvex QP with a polytope constraint is a hard problem, we show that the problem with an ellipsoidal constraint is easy. When the hard QP is solved by successively solving the easy QP, the sequence of points monotonically converge to a feasible point satisfying both the first and the second order optimality conditions.Research supported in part by NSF Grant DDM-8922636 and the College Summer Grant, College of Business Administration, The University of Iowa.     

On the convergence of “Threshold Accepting”

Simulated Annealing (SA) has become a very popular tool in combinatorial optimization since its introduction in 1982. Recently Dueck and Scheuer proposed another simple modification of local search which they called Threshold Accepting (TA). In this paper some convergence results for TA are presented. The proofs are not constructive and make use of the fact that in a certain sense SA belongs to the convex hull of TA.     

An algorithm for nondifferentiable optimization

In this paper, we give an implementable algorithm for minimizing a locally Lipschitz function without constraints, and prove the global convergence under the -acute angle condition.     

Über geschlossene affine Zwangläufe in der Ebene

We consider integral coverings y:{1,2,..,} of an affine plane which occur when is moved under a continuous periodic affine motion(t):. One can distinguish normal points × , i.e. is constant in a certain neighborhood of x, and singular points. If (x) is the number of times x passes through its orbit (t)x all normal points x have (x)=1, and the set of all singular points consists of a number of isolated points and lines. If (x) is the tangent rotation number of the orbit of x all singular points lie on the moving pole curve.     

Homogeneous grouping of nuclear fuel cans through simulated annealing and tabu search

Collections of cans containing nuclear fuel have to be grouped in batches that are as homogeneous as possible with respect to several criteria. This highly combinatorial problem, which can be described as grouping or clustering, is tackled using simulated annealing and tabu search. Both approaches are submitted to extensive experimentation on a real data set and several artificial ones. Two variants of the basic approaches called Locally optimized simulated annealing and Tabu search with variable offset are also tested. Sensitivity to parameter choice and to problem size are investigated. All four algorithms outperform a local search heuristic previously proposed in the literature; on the class of instances dealt with, a remarkably stable ranking of the four algorithms emerges.     

Approximation in the mean by bounded analytic functions

Let 1<p< and . LetC _q denote the Bessel capacity in the plane. Let be the set of homomorphisms ofH (G) such that (z)= and letNP denote the set of points in G for which is not a peak set forH (G). In this note, we show that ifC _q (NP)=0, thenH (G) is dense inL _a ^p (G), the Bergman space overG.Partially supported by NSF DMS-9401234     

Diagonal Bases in Orlik-Solomon Type Algebras

To encode an important property of the no broken circuit bases of the Orlik- Solomon-Terao algebras, Szenes has introduced a particular type of bases, the so called diagonal basis. We prove that this definition extends naturally to a large class of algebras, the so called - algebras. Our definitions make also use of an iterative residue formula based on the matroidal operation of contraction. This formula can be seen as the combinatorial analogue of an iterative residue formula introduced by Szenes. As an application we deduce nice formulas to express a pure element in a diagonal basis.AMS Subject Classification: 52C35, 05B35, 14F40.     

Multi-stage stochastic optimization applied to energy planning

This paper presents a methodology for the solution of multistage stochastic optimization problems, based on the approximation of the expected-cost-to-go functions of stochastic dynamic programming by piecewise linear functions. No state discretization is necessary, and the combinatorial explosion with the number of states (the well known curse of dimensionality of dynamic programming) is avoided. The piecewise functions are obtained from the dual solutions of the optimization problem at each stage and correspond to Benders cuts in a stochastic, multistage decomposition framework. A case study of optimal stochastic scheduling for a 39-reservoir system is presented and discussed.     

Large transversals to small families of unit disks

Summary It is proved that if the nonempty intersection of bounded closed convex sets AnB is contained in (A + F)U(B+F) and one of the following holds true: (i) the space X is less-than-three dimensional, (ii) AUB is convex, (iii) F is a one-point set, then AnBCA+F or AnBCB+F (Theorems 2 and 3). Moreover, under some hypotheses the characterization of A and B such that AnB is a summand of AUB is given (Theorem 3).     

Moduli of smoothness and best approximation in the spacesL p , 0<p<1

L ^p , 0<<1, .     

Martingale Hardy spaces,BMO and VMO spaces with nonlinearly ordered stochastic basis

VMO. , ⁺, «» VMO . « » .     

Worst case asymptotics for some classical optimization problems

We provide a simple and natural method for obtaining the worst case asymptotics of some of the classical problems in combinatorial optimization and operations research. Worst case asymptotics for the minimal spanning tree, shortest tour, and minimal matching onn points are found. The key simplifying idea involves consideration of the associated boundary processes. The general approach considered here also handles the case of power weighted edges.Research supported in part by NSA grant MDA904-95-H-1005.     

Some functional inequalities and their Baire category properties

Summary In the paper we consider, from a topological point of view, the set of all continuous functionsf:I I for which the unique continuous solution:I – [0, ) of(f(x)) (x, (x)) and(x, (x)) (f(x)) (x, (x)), respectively, is the zero function. We obtain also some corollaries on the qualitative theory of the functional equation(f(x)) = g(x, (x)). No assumption on the iterative behaviour off is imposed.     

On the solution of a generalized Schrödinger-type equation

Lu(t)+(u,F)g(t)=f(t), tS. , ( F, g). .

---

---

The authors wish to thank Professor Yu. A. Rozanov for his help and discussions.     

Tritronquée Solutions of Perturbed First Painlevé Equations

We consider solutions of the class of ODEs y=6y ²–x , which contains the first Painlevé equation (PI) for =1. It is well known that PI has a unique real solution (called a tritronquée solution) asymptotic to and decaying monotonically on the positive real line. We prove the existence and uniqueness of a corresponding solution for each real nonnegative 1.     

Topology optimization of multi-purpose structures

Whilst most of the literature on topology optimization of structures deals with so-called selfadjoint problems involving highly idealized, single-purpose structures, this paper discusses topology optimization of multi-purpose structures which concerns nonselfadjoint problems. General methods based on the so-called layout theory, application to trusses and perforated plates and computational difficulties are discussed.