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.     

Semistrictly quasiconvex mappings and non-convex vector optimization

This paper introduces a new class of non-convex vector functions strictly larger than that of P-quasiconvexity, with P ^m being the underlying ordering cone, called semistrictly ( ^m\ –int P)-quasiconvex functions. This notion allows us to unify various results on existence of weakly efficient (weakly Pareto) optima. By imposing a coercivity condition we establish also the compactness of the set of weakly Pareto solutions. In addition, we provide various characterizations for the non-emptiness, convexity and compactness of the solution set for a subclass of quasiconvex vector optimization problems on the real-line. Finally, it is also introduced the notion of explicit ( ^m\ –int P)-quasiconvexity (equivalently explicit (int P)-quasiconvexity) which plays the role of explicit quasiconvexity (quasiconvexity and semistrict quasiconvexity) of real-valued functions.Acknowldegements.The author wishes to thank both referees for their careful reading of the paper, their comments, remarks, helped to improve the presentation of some results. One of the referee provided the references [5, 6] and indirectly [20].     

More About 4-Isosceles Planar Sets

A finite planar set is k-isosceles for k 3 if every k-point subset of the set contains a point equidistant from the other two. In [1] Fishburn obtains several important results about isosceles planar sets and poses a series of conjectures and open questions. We disprove Conjecture 1 in [1] and provide another 34 nonsimilar 4-isosceles 8-point planar sets which answer one of the open questions in [1] negatively.     

The Brownian loop soup

We define a natural conformally invariant measure on unrooted Brownian loops in the plane and study some of its properties. We relate this measure to a measure on loops rooted at a boundary point of a domain and show how this relation gives a way to chronologically add Brownian loops to simple curves in the plane.Cornell University; Research supported in part by the National Science FoundationUniversité Paris-Sud and IUFMathematics Subject Classification (2000):60J65, 81T40     

Representations of twisted Yangians associated with skew Young diagrams

Let $G_M$ be either the orthogonal group $O_M$ or the symplectic group $Sp_M$ over the complex field; in the latter case the non-negative integer $M$ has to be even. Classically, the irreducible polynomial representations of the group $G_M$ are labeled by partitions $\mu=(\mu_{1},\mu_{2},\,\ldots)$ such that $\mu^{\prime}_1+\mu^{\prime}_2\le M$ in the case $G_M=O_M$, or $2\mu^{\prime}_1\le M$ in the case $G_M=Sp_M$. Here $\mu^{\prime}=(\mu^{\prime}_{1},\mu^{\prime}_{2},\,\ldots)$ is the partition conjugate to $\mu$. Let $W_\mu$ be the irreducible polynomial representation of the group $G_M$ corresponding to $\mu$. Regard $G_N\times G_M$ as a subgroup of $G_{N+M}$. Then take any irreducible polynomial representation $W_\lambda$ of the group $G_{N+M}$. The vector space $W_{\lambda}(\mu)={\rm Hom}_{\,G_M}( W_\mu, W_\lambda)$ comes with a natural action of the group $G_N$. Put $n=\lambda_1-\mu_1+\lambda_2-\mu_2+\ldots\,$. In this article, for any standard Young tableau $\varOmega$ of skew shape $\lm$ we give a realization of $W_{\lambda}(\mu)$ as a subspace in the $n$-fold tensor product $(\mathbb{C}^N)^{\bigotimes n}$, compatible with the action of the group $G_N$. This subspace is determined as the image of a certain linear operator $F_\varOmega (M)$ on $(\mathbb{C}^N)^{\bigotimes n}$, given by an explicit formula. When $M=0$ and $W_{\lambda}(\mu)=W_\lambda$ is an irreducible representation of the group $G_N$, we recover the classical realization of $W_\lambda$ as a subspace in the space of all traceless tensors in $(\mathbb{C}^N)^{\bigotimes n}$. Then the operator $F_\varOmega\(0)$ may be regarded as the analogue for $G_N$ of the Young symmetrizer, corresponding to the standard tableau $\varOmega$ of shape $\lambda$. This symmetrizer is a certain linear operator on $\CNn$$(\mathbb{C}^N)^{\bigotimes n} $ with the image equivalent to the irreducible polynomial representation of the complex general linear group $GL_N$, corresponding to the partition $\lambda$. Even in the case $M=0$, our formula for the operator $F_\varOmega(M)$ is new. Our results are applications of the representation theory of the twisted Yangian, corresponding to the subgroup $G_N$ of $GL_N$. This twisted Yangian is a certain one-sided coideal subalgebra of the Yangian corresponding to $GL_N$. In particular, $F_\varOmega(M)$ is an intertwining operator between certain representations of the twisted Yangian in $(\mathbb{C}^N)^{\bigotimes n}$.     

LP formulations of the shortest path tree problem

Based on a pair of primal-dual LP formulations of the shortest path tree problem, the first algorithmic approach to reoptimizing the shortest paths subject to changes in the edge weights was proposed by S. Pallottino and M.G. Scutellá in 2003. We shall here focus solely on their introductory sections, propose some simplifications of the models considered, and finally relate the resulting models to the presentation of single-source shortest path problems in textbooks treating this subject with but limited or no reference to LP.Received: April 2004, Revised: August 2004, MSC classification: 90C05, 90C35, 90B10 Dedicated to the memory of Stefano Pallottino     

Taylor polynomials and non-homogeneous blow-ups

The graph of a function f is subjected to non-homogeneous dilatations around (x₀;f(x₀)), related to the Taylor expansion of f at x₀. Some natural questions about convergence are considered and answered. Finally, it is provided a counterexample to a statement which was presumed to be true in former literature.Mathematics Subject Classification (1991): Primary 41A10, 49Q15, 53A05, 54G20; Secondary 28A75, 28A78, 28A33, 54C20     

String Jacobi Matrices with Very Fast Decreasing Weights

In this work we investigate a class of string, compact Jacobi matrices with very rapidly decreasing weights. In particular, we have found Hellinger-Weyls function representation as ratio of two entire functions with known Taylor series representation. The asymptotical estimations of zeroes of this entire functions and of eigenvalues of a corresponding operator are found. The application of this theory to Rogers-Ramanujans functions is considered.Submitted: November 18, 2002 Revised: October 30, 2003     

Two-Wavelet Localization Operators on $$ L^p(\mathbb{R}^n) $$ for the Weyl-Heisenberg Group

We give results on the boundedness and compactness of localization operators with two admissible wavelets on for the Weyl-Heisenberg group.     

Existence theory for nonclassical entropy solutions of scalar conservation laws

We establish a general existence theory for the Cauchy problem associated with a scalar conservation law in one-space dimension. The flux-function is assumed to be nonconvex and we consider nonclassical entropy solutions selected by a kinetic relation. To solve the Cauchy problem, we construct a sequence of approximate solutions using a wave-front tracking scheme. The main difficulty is deriving a uniform estimate on the total variation of the approximate solutions. This is achieved here by introducing a generalized total variation functional, which is decreasing in time and, additionally, reduces to the standard total variation functional when the solutions contain only classical shocks. This functional seems sufficiently robust to be useful for systems as well.Received: June 3, 2002; revised: November 12, 2002