A MIP approach for some practical packing problems: Balancing constraints and tetris-like items

This paper considers packing problems with balancing conditions and items consisting of clusters of parallelepipeds (mutually orthogonal, i.e. tetris-like items). This issue is quite frequent in space engineering and a real-world application deals with the Automated Transfer Vehicle project (funded by the European Space Agency), at present under development. A Mixed Integer Programming (MIP) approach is proposed. The three-dimensional single bin packing problem is considered. It consists of orthogonally placing, with possibility of rotation, the maximum number of parallelepipeds into a given parallelepiped. A MIP formulation of the problem is reported together with a MIP-based heuristic approach. Balancing conditions are furthermore examined, as well as the orthogonal placement (with rotation) of tetris-like items into a rectangular domain.Received: September 2003, Revised: February 2004, AMS classification: 90B99, 05B40, 90C90, 90C59Thanks are due to T. A. Ciriani for the important suggestions given for the whole paper and to S. Gliozzi (IBM, Business Consulting Services) for the significant support offered, in particular in discussing the topics presented in Sect. 2.1.     

The set union problem with dynamic weighted backtracking

We consider an extension of the set union problem, in which dynamic weighted backtracking over sequences of unions is permitted. We present a new data structure which can support each operation inO(logn) time in the worst case. We prove that this bound is tight for pointer based algorithms. Furthermore, we design a different data structure to achieve better amortized bounds. The space complexity of both our data structures isO(n). Motivations for studying this problem arise in logic programming memory management.Work partially supported by NSF Grant CCR-88-14977, by the ESPRIT II Basic Research Actions Program of the EC under contract No. 3075 (Project ALCOM), and by the Italian MURST Project Algoritmi e Strutture di Calcolo.Partially supported by an IBM Graduate Fellowship.     

On the convergence of solutions of degenerate elliptic equations in divergence form

It is studied the convergence of solutions of Dirichlet problems for sequences of monotone operators of the type — div (a_h (x, D·)), where the functions a_h verify the following degenerate coerciveness assumption

How to prove that a preconditioner cannot be superlinear

In the general case of multilevel Toeplitz matrices, we recently proved that any multilevel circulant preconditioner is not superlinear (a cluster it may provide cannot be proper). The proof was based on the concept of quasi-equimodular matrices, although this concept does not apply, for example, to the sine-transform matrices. In this paper, with a new concept of partially equimodular matrices, we cover all trigonometric matrix algebras widely used in the literature. We propose a technique for proving the non-superlinearity of certain frequently used preconditioners for some representative sample multilevel matrices. At the same time, we show that these preconditioners are, in a certain sense, the best among the sublinear preconditioners (with only a general cluster) for multilevel Toeplitz matrices.

     

A variational approach to chaotic dynamics in periodically forced nonlinear oscillators

We prove that a class of problems containing the classical periodically forced pendulum equation displays the main features of chaotic dynamics. The approach is based on the construction of multibump type heteroclinic solutions to periodic orbits by the use of global variational methods.     

Extreme value theory for singular measures

In this paper, we perform an analytical and numerical study of the extreme values of specific observables of dynamical systems possessing an invariant singular measure. Such observables are expressed as functions of the distance of the orbit of initial conditions with respect to a given point of the attractor. Using the block maxima approach, we show that the extremes are distributed according to the generalised extreme value distribution, where the parameters can be written as functions of the information dimension of the attractor. The numerical analysis is performed on a few low dimensional maps. For the Cantor ternary set and the Sierpinskij triangle, which can be constructed as iterated function systems, the inferred parameters show a very good agreement with the theoretical values. For strange attractors like those corresponding to the Lozi and He?non maps, a slower convergence to the generalised extreme value distribution is observed. Nevertheless, the results are in good statistical agreement with the theoretical estimates. It is apparent that the analysis of extremes allows for capturing fundamental information of the geometrical structure of the attractor of the underlying dynamical system, the basic reason being that the chosen observables act as magnifying glass in the neighborhood of the point from which the distance is computed.     

2,4‐Dibromo‐3‐methoxy‐6‐nitrobenz­aldeyde: effect of substituents on ring geometry

In the title compound, C₈H₅Br₂NO₄, the endocyclic angles of the ring deviate significantly from the ideal value of 120°. The substituents deviate from the plane of the ring, with large twist angles for the aldehyde, nitro and methoxy groups. The geometry of the mol­ecule in the crystal is compared with that of the isolated mol­ecule, as given by a self‐consistent field molecular‐orbital Hartree–Fock calculation. Only weak hydrogen bonds of the C—H?Br and C—H?O types are present in the crystal structure.