Interval methods for verifying structural optimality of circle packing configurations in the unit square

The paper is dealing with the problem of finding the densest packings of equal circles in the unit square. Recently, a global optimization method based exclusively on interval arithmetic calculations has been designed for this problem. With this method it became possible to solve the previously open problems of packing 28, 29, and 30 circles in the numerical sense: tight guaranteed enclosures were given for all the optimal solutions and for the optimum value. The present paper completes the optimality proofs for these cases by determining all the optimal solutions in the geometric sense. Namely, it is proved that the currently best-known packing structures result in optimal packings, and moreover, apart from symmetric configurations and the movement of well-identified free circles, these are the only optimal packings. The required statements are verified with mathematical rigor using interval arithmetic tools.     

Principles of scatter search

Scatter search is an evolutionary method that has been successfully applied to hard optimization problems. The fundamental concepts and principles of the method were first proposed in the 1970s, based on formulations dating back to the 1960s for combining decision rules and problem constraints. In contrast to other evolutionary methods like genetic algorithms, scatter search is founded on the premise that systematic designs and methods for creating new solutions afford significant benefits beyond those derived from recourse to randomization. It uses strategies for search diversification and intensification that have proved effective in a variety of optimization problems.This paper provides the main principles and ideas of scatter search and its generalized form path relinking. We first describe a basic design to give the reader the tools to create relatively simple implementations. More advanced designs derive from the fact that scatter search and path relinking are also intimately related to the tabu search (TS) metaheuristic, and gain additional advantage by making use of TS adaptive memory and associated memory-exploiting mechanisms capable of being tailored to particular contexts. These and other advanced processes described in the paper facilitate the creation of sophisticated implementations for hard problems that often arise in practical settings. Due to their flexibility and proven effectiveness, scatter search and path relinking can be successfully adapted to tackle optimization problems spanning a wide range of applications and a diverse collection of structures, as shown in the papers of this volume.     

Electrostatics of a point charge between intersecting planes: exact solutions and method of images

In this work, the authors present a commonly used example in electrostatics that could be solved exactly in a conventional manner, yet expressed in a compact form, and simultaneously work out special cases using the method of images. Then, by plotting the potentials and electric fields obtained from these two methods, the authors demonstrate that these two methods provide identical solutions. Furthermore, a number of sum rules are deduced based on the arguments that these two methods should also give the same induced charge, and force.     

Quasicrystals and the Wulff-Shape

Infinite sphere packings give information about the structure but not about the shape of large dense sphere packings. For periodic sphere packings a new method was introduced in [W2], [W3], [Sc], and [BB], which gave a direct relation between dense periodic sphere packings and the Wulff-shape, which describes the shape of ideal crystals. In this paper we show for the classical Penrose tiling that dense finite quasiperiodic circle packings also lead to a Wulff-shape. This indicates that the shape of quasicrystals might be explained in terms of a finite packing density. Here we prove an isoperimetric inequality for unions of Penrose rhombs, which shows that the regular decagon is, in a sense, optimal among these sets. Motivated by the analysis of linear densities in the Penrose plane we introduce a surface energy for a class of polygons, which is analogous to the Gibbs—Curie surface energy for periodic crystals. This energy is minimized by the Wulff-shape, which is always a polygon and in certain cases it is the regular decagon, in accordance with the fivefold symmetry of quasicrystals. Received June 1, 1997, and in revised form November 3, 1997.     

On Remainder Equations

The remainder equations were introduced by S. O. Hansson. In this paper, we will give an exhaustive characterization of the set of solutions for remainder equations. Moreover, solutions to some unsolved problems proposed by Hansson are reported.     

Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming

In exact arithmetic, the simplex method applied to a particular linear programming problem instance with real data either shows that it is infeasible, shows that its dual is infeasible, or generates optimal solutions to both problems. Most interior-point methods, on the other hand, do not provide such clear-cut information. If the primal and dual problems have bounded nonempty sets of optimal solutions, they usually generate a sequence of primal or primaldual iterates that approach feasibility and optimality. But if the primal or dual instance is infeasible, most methods give less precise diagnostics. There are methods with finite convergence to an exact solution even with real data. Unfortunately, bounds on the required number of iterations for such methods applied to instances with real data are very hard to calculate and often quite large. Our concern is with obtaining information from inexact solutions after a moderate number of iterations. We provide general tools (extensions of the Farkas lemma) for concluding that a problem or its dual is likely (in a certain well-defined sense) to be infeasible, and apply them to develop stopping rules for a homogeneous self-dual algorithm and for a generic infeasible-interior-point method for linear programming. These rules allow precise conclusions to be drawn about the linear programming problem and its dual: either near-optimal solutions are produced, or we obtain certificates that all optimal solutions, or all feasible solutions to the primal or dual, must have large norm. Our rules thus allow more definitive interpretation of the output of such an algorithm than previous termination criteria. We give bounds on the number of iterations required before these rules apply. Our tools may also be useful for other iterative methods for linear programming. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Exact and heuristic approaches for the index tracking problem with UCITS constraints

Index tracking aims at determining an optimal portfolio that replicates the performance of an index or benchmark by investing in a smaller number of constituents or assets. The tracking portfolio should be cheap to maintain and update, i.e., invest in a smaller number of constituents than the index, have low turnover and low transaction costs, and should avoid large positions in few assets, as required by the European Union Directive UCITS (Undertaking for Collective Investments in Transferable Securities) rules. The UCITS rules make the problem hard to be satisfactorily modeled and solved to optimality: no exact methods but only heuristics have been proposed so far. The aim of this paper is twofold. First, we present the first Mixed Integer Quadratic Programming (MIQP) formulation for the constrained index tracking problem with the UCITS rules compliance. This allows us to obtain exact solutions for small- and medium-size problems based on real-world datasets. Second, we compare these solutions with the ones provided by the state-of-art heuristic Differential Evolution and Combinatorial Search for Index Tracking (DECS-IT), obtaining information about the heuristic performance and its reliability for the solution of large-size problems that cannot be solved with the exact approach. Empirical results show that DECS-IT is indeed appropriate to tackle the index tracking problem in such cases. Furthermore, we propose a method that combines the good characteristics of the exact and of the heuristic approaches.     

A computational analysis of lower bounds for big bucket production planning problems

In this paper, we analyze a variety of approaches to obtain lower bounds for multi-level production planning problems with big bucket capacities, i.e., problems in which multiple items compete for the same resources. We give an extensive survey of both known and new methods, and also establish relationships between some of these methods that, to our knowledge, have not been presented before. As will be highlighted, understanding the substructures of difficult problems provide crucial insights on why these problems are hard to solve, and this is addressed by a thorough analysis in the paper. We conclude with computational results on a variety of widely used test sets, and a discussion of future research.     

NUMERICAL SOLUTIONS OF DISCONTINUOUS BOUNDARY VALUE PROBLEMS FOR GENERAL ELLIPTIC COMPLEX EQUATIONS OF FIRST ORDER

1Formulati0nofDiscontinuousBoundaryValueProblemsLetDbeanN 1-connectedb0undeddomaininthez=x iy-planeCwiththeboundaryFEC:(0相似文献   

Discrete Solutions of Dirichlet Problems, Finite Volumes, and Circle Packings

Convergence results for discrete solutions of Dirichlet problems for Poisson equations are obtained, where discrete solutions are constructed for triangular grids using finite volumes with sides perpendicular to, but not necessarily bisecting, corresponding edges in underlying triangulations. A method, based on properties of circle packings, is described for generating triangular meshes and associated volumes. Also, the approximation of exit probabilities of the Brownian motion by exit probabilities of random walks on circle packings is discussed. Received July 24, 1997, and in revised form November 8, 1998.