A cutting plane algorithm for a clustering problem

In this paper we consider a clustering problem that arises in qualitative data analysis. This problem can be transformed to a combinatorial optimization problem, the clique partitioning problem. We have studied the latter problem from a polyhedral point of view and determined large classes of facets of the associated polytope. These theoretical results are utilized in this paper. We describe a cutting plane algorithm that is based on the simplex method and uses exact and heuristic separation routines for some of the classes of facets mentioned before. We discuss some details of the implementation of our code and present our computational results. We mention applications from, e.g., zoology, economics, and the political sciences.     

Approximation of classes of analytic functions by algebraic polynomials and kolmogorov widths

We obtain estimates of the best polynomial approximations, uniform in the closure B of Faber domains of the complex plane ?, for functions continuous in B and defined by Cauchy-type integrals with densities possessing certain generalized differential properties. We establish estimates exact in order for the Kolmogorov widths of classes of such functions in relevant functional spaces.     

On a reconstruction algorithm for the trajectory and control in a delay system

We discuss a problem of the dynamic reconstruction of unmeasured coordinates of the phase vector and unknown controls in nonlinear vector equations with delay. A regularizing algorithm is proposed for the reconstruction of both controls and unmeasured coordinates simultaneously with the processes. The algorithm is stable with respect to information noises and computational errors.     

Shuffling algorithm for boxed plane partitions

We introduce discrete time Markov chains that preserve uniform measures on boxed plane partitions. Elementary Markov steps change the size of the box from a×b×c to (a−1)×(b+1)×c or (a+1)×(b−1)×c. Algorithmic realization of each step involves O((a+b)c) operations. One application is an efficient perfect random sampling algorithm for uniformly distributed boxed plane partitions.Trajectories of our Markov chains can be viewed as random point configurations in the three-dimensional lattice. We compute the bulk limits of the correlation functions of the resulting random point process on suitable two-dimensional sections. The limiting correlation functions define a two-dimensional determinantal point processes with certain Gibbs properties.     

Diffraction of a plane wave by a step discontinuity in an impedance plane

In the present paper, the high-frequency diffraction of a plane wave by a right-angle step discontinuity in an impedance plane is analyzed with the help of the uniform geometric theory of diffraction, beginning with the Maluzhenets solution. The principal term of an asymptotic solution of the problem, which is uniform with respect to the angle of incidence of the plane wave and the angle of observation, is derived. The excitation of primary and multiply diffracted fields radiated from the upper edge, as well as surface waves, is considered (the lower edge does not radiate cylindrical or surface waves owing to a right-angle step). For simplicity, the details of computation are given here for a right-angle step discontinuity. A similar procedure is applied to other examples with more complicated geometry. Bibliography: 7 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 250, 1998, pp. 97–108. Translated by V. V. Zalipaev.     

Packing Steiner trees: a cutting plane algorithm and computational results

In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory for the Steiner tree packing polyhedron developed in our companion paper (this issue) and meant to turn this theory into an algorithmic tool for the solution of practical problems.     

Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm

When solving the one-dimensional cutting stock problem (1D CSP) as an integer linear programming problem one has to overcome computational difficulties arising from the integrality condition and a huge number of variables. In the Gilmore–Gomory approach the corresponding continuous relaxation is solved via column generation techniques followed by an appropriate rounding of the in general non-integer solution. Obviously, there is no guarantee of obtaining an optimal solution in this way but it is extremely effective in practice. However, in two- and three-dimensional cutting stock problems the heuristics are not so good which necessitates the research of effective exact methods. In this paper we present an exact solution approach for the 1D CSP which is based on a combination of the cutting plane method and the column generation technique. Results of extensive computational experiments are reported.     

The integration of an interior-point cutting plane method within a branch-and-price algorithm

This paper presents a novel integration of interior point cutting plane methods within branch-and-price algorithms. Unlike the classical method, columns are generated at a central dual solution by applying the analytic centre cutting plane method (ACCPM) on the dual of the full master problem. First, we introduce some modifications to ACCPM. We propose a new procedure to recover primal feasibility after adding cuts and use, for the first time, a dual Newtons method to calculate the new analytic centre after branching. Second, we discuss the integration of ACCPM within the branch-and-price algorithm. We detail the use of ACCPM as the search goes deep in the branch and bound tree, making full utilization of past information as a warm start. We exploit dual information from ACCPM to generate incumbent feasible solutions and to guide branching. Finally, the overall approach is implemented and tested for the bin-packing problem and the capacitated facility location problem with single sourcing. We compare against Cplex-MIP 7.5 as well as a classical branch-and-price algorithm.Mathematics Subject Classification (1991): 20E28, 20G40, 20C20     

A cutting plane algorithm for graph coloring

We present an approach based on integer programming formulations of the graph coloring problem. Our goal is to develop models that remove some symmetrical solutions obtained by color permutations. We study the problem from a polyhedral point of view and determine some families of facets of the 0/1-polytope associated with one of these integer programming formulations. The theoretical results described here are used to design an efficient Cutting Plane algorithm.     

Positive periodic solutions of competitive kolmogorov diffusion systems with interference constants

In this paper, we consider the positive periodic solutions of multispecies patches connected by discrete diffusion with a within-patch dynamics of periodic Kolmogorov type. A new criterion for existence and globally asymptotic stability of positive periodic solution is established. The results in [1–4] are improved and extended.     

Diffraction of a plane wave by a narrow cone

The problem of diffraction of a plane scalar wave by a narrow cone is considered. The shape of the cone is arbitrary. The boundary condition is the Dirichlet or Neumann one. The wave scattered by the cone vertex arises as a result of the diffraction process. The subject of this paper is to calculate the wave amplitude. If the cone is narrow, it is possible to obtain simpler approximate formulas in comparison with Smyshlayev's one. The exactness of the approximate formulas is checked numerically. The etalon is a solution in explicit form in the axially symmetric case. The calculation shows that our formula is more exact in the case of the Dirichlet boundary condition than Felsen's formula. The approximate formula is a generalization of Felsen's one for circular cone to an arbitrary narrow cone in the case of the Neumann boundary condition. Bibliography: 6 titles. Dedicated to N. N. Uraltseva on her jubilee Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 221, 1995, pp. 67–74. Translated by D. B. Dement'ev.     

Stochastic optimal control and algorithm of the trajectory of horizontal wells

This paper presents a nonlinear, multi-phase and stochastic dynamical system according to engineering background. We show that the stochastic dynamical system exists a unique solution for every initial state. A stochastic optimal control model is constructed and the sufficient and necessary conditions for optimality are proved via dynamic programming principle. This model can be converted into a parametric nonlinear stochastic programming by integrating the state equation. It is discussed here that the local optimal solution depends in a continuous way on the parameters. A revised Hooke–Jeeves algorithm based on this property has been developed. Computer simulation is used for this paper, and the numerical results illustrate the validity and efficiency of the algorithm.     

Diffraction of a plane wave by a circular disk

In this paper we solve the problem of diffraction of a normally incident plane wave by a circular disk. We treat both the hard and soft disk. In each case we obtain the solution as a series which converges when the product of the wave number and the radius of the disk is large. Our construction leads directly to asymptotic approximations to the solution for large wave number.     

A cutting plane algorithm for solving bilinear programs

This paper addresses itself to a special class of nonconvex quadratic program referred to as a bilinear program in the literature. We will propose here a cutting plane algorithm to solve this class of problems. The algorithm is along the lines of H. Tui and K. Ritter, but it differs in its exploitation of the special structure of the problem. Though the algorithm is not guaranteed at this stage of the research to converge to a global optimum, the preliminary results of numerical experiments are encouraging.This research was partially supported by the Office of Naval Research under Contract N-00014-67-A-0112-0011; and U.S. Atomic Energy Commission Contract AT(04-3)-326-PA # 18.     

Monte Carlo algorithm for trajectory optimization based on Markovian readings

This paper describes an efficient algorithm to find a smooth trajectory joining two points A and B with minimum length constrained to avoid fixed subsets. The basic assumption is that the locations of the obstacles are measured several times through a mechanism that corrects the sensors at each reading using the previous observation. The proposed algorithm is based on the penalized nonparametric method previously introduced that uses confidence ellipses as a fattening of the avoidance set. In this paper we obtain consistent estimates of the best trajectory using Monte Carlo construction of the confidence ellipse.     

An algorithm for constructing star-shaped drawings of plane graphs

A straight-line planar drawing of a plane graph is called a convex drawing if every facial cycle is drawn as a convex polygon. Convex drawings of graphs is a well-established aesthetic in graph drawing, however not all planar graphs admit a convex drawing. Tutte [W.T. Tutte, Convex representations of graphs, Proc. of London Math. Soc. 10 (3) (1960) 304–320] showed that every triconnected plane graph admits a convex drawing for any given boundary drawn as a convex polygon. Thomassen [C. Thomassen, Plane representations of graphs, in: Progress in Graph Theory, Academic Press, 1984, pp. 43–69] gave a necessary and sufficient condition for a biconnected plane graph with a prescribed convex boundary to have a convex drawing.In this paper, we initiate a new notion of star-shaped drawing of a plane graph as a straight-line planar drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. A star-shaped drawing is a natural extension of a convex drawing, and a new aesthetic criteria for drawing planar graphs in a convex way as much as possible. We give a sufficient condition for a given set A of corners of a plane graph to admit a star-shaped drawing whose concave corners are given by the corners in A, and present a linear time algorithm for constructing such a star-shaped drawing.     

An exact algorithm for kinodynamic planning in the plane

Planning time-optimal motions has been a major focus of research in robotics. In this paper we consider the following problem: given an object in two-dimensional physical space, an initial point, and a final point, plan a time-optimal obstacle-avoiding motion for this object subject to bounds on the velocity and acceleration of the object. We give the first algorithm which solves the problem exactly in the case where the velocity and acceleration bounds are given in theL _∞ norm. We further prove the following important results: a tracking lemma and a loop-elimination theorem, both of which are applicable to the case of arbitrary norms. The latter result implies that, with or without obstacles, a path which intersects itself can be replaced by one which does not do so and which takes time less than or equal to that taken by the original path. The work of J. Canny and A. Rege was supported by NSF Grants IRI-89-58577 and IRI-90-14490 and by a David and Lucile Packard Fellowship. J. Reif's work was supported in part by DARPA/ARO Contract DAAL03-88-K-0185, Air Force Contract AFSOR-87-0386, ONR Contract N00014-K-0310, and DARPA/ISTO Contract N00014-88-K-0458.