XHSTT: an XML archive for high school timetabling problems in different countries

We present the progress on the benchmarking project for high school timetabling that was introduced at PATAT 2008. In particular, we announce the High School Timetabling Archive XHSTT-2011 with 21 instances from 8 countries and an evaluator capable of checking the syntax of instances and evaluating the solutions.     

Representation of Gaussian isotropic spin random fields

We develop a technique for the construction of random fields on algebraic structures. We deal with two general situations: random fields on homogeneous spaces of a compact group and in the spin line bundles of the 2$2$-sphere. In particular, every complex Gaussian isotropic spin random field can be represented in this way. Our construction extends P. Lévy’s original idea for the spherical Brownian motion.     

Classical and Sobolev orthogonality of the nonclassical Jacobi polynomials with parameters \alpha =\beta =-1

In this paper, we consider the second-order differential expression $$\begin{aligned} \ell [y](x)=(1-x^{2})(-(y^{\prime }(x))^{\prime }+k(1-x^{2})^{-1} y(x))\quad (x\in (-1,1)). \end{aligned}$$ This is the Jacobi differential expression with nonclassical parameters $\alpha =\beta =-1$ in contrast to the classical case when $\alpha ,\beta >-1$ . For fixed $k\ge 0$ and appropriate values of the spectral parameter $\lambda ,$ the equation $\ell [y]=\lambda y$ has, as in the classical case, a sequence of (Jacobi) polynomial solutions $\{P_{n}^{(-1,-1)} \}_{n=0}^{\infty }.$ These Jacobi polynomial solutions of degree $\ge 2$ form a complete orthogonal set in the Hilbert space $L^{2}((-1,1);(1-x^{2})^{-1})$ . Unlike the classical situation, every polynomial of degree one is a solution of this eigenvalue equation. Kwon and Littlejohn showed that, by careful selection of this first-degree solution, the set of polynomial solutions of degree $\ge 0$ are orthogonal with respect to a Sobolev inner product. Our main result in this paper is to construct a self-adjoint operator $T$ , generated by $\ell [\cdot ],$ in this Sobolev space that has these Jacobi polynomials as a complete orthogonal set of eigenfunctions. The classical Glazman–Krein–Naimark theory is essential in helping to construct $T$ in this Sobolev space as is the left-definite theory developed by Littlejohn and Wellman.     

Confidence-based optimisation for the newsvendor problem under binomial,Poisson and exponential demand

We introduce a novel strategy to address the issue of demand estimation in single-item single-period stochastic inventory optimisation problems. Our strategy analytically combines confidence interval analysis and inventory optimisation. We assume that the decision maker is given a set of past demand samples and we employ confidence interval analysis in order to identify a range of candidate order quantities that, with prescribed confidence probability, includes the real optimal order quantity for the underlying stochastic demand process with unknown stationary parameter(s). In addition, for each candidate order quantity that is identified, our approach produces an upper and a lower bound for the associated cost. We apply this approach to three demand distributions in the exponential family: binomial, Poisson, and exponential. For two of these distributions we also discuss the extension to the case of unobserved lost sales. Numerical examples are presented in which we show how our approach complements existing frequentist—e.g. based on maximum likelihood estimators—or Bayesian strategies.     

Local dimensions of measures on infinitely generated self-affine sets

We show the existence of the local dimension of an invariant probability measure on an infinitely generated self-affine set, for almost all translations. This implies that an ergodic probability measure is exactly dimensional. Furthermore the local dimension equals the minimum of the local Lyapunov dimension and the dimension of the space.     

Bilevel programming and the separation problem

In recent years, branch-and-cut algorithms have become firmly established as the most effective method for solving generic mixed integer linear programs (MILPs). Methods for automatically generating inequalities valid for the convex hull of solutions to such MILPs are a critical element of branch-and-cut. This paper examines the nature of the so-called separation problem, which is that of generating a valid inequality violated by a given real vector, usually arising as the solution to a relaxation of the original problem. We show that the problem of generating a maximally violated valid inequality often has a natural interpretation as a bilevel program. In some cases, this bilevel program can be easily reformulated as a simple single-level mathematical program, yielding a standard mathematical programming formulation for the separation problem. In other cases, no such polynomial-size single-level reformulation exists unless the polynomial hierarchy collapses to its first level (an event considered extremely unlikely in computational complexity theory). We illustrate our insights by considering the separation problem for two well-known classes of valid inequalities.     

On asymptotically harmonic manifolds of negative curvature

We study asymptotically harmonic manifolds of negative curvature, without any cocompactness or homogeneity assumption. We show that asymptotic harmonicity provides a lot of information on the asymptotic geometry of these spaces: in particular, we determine the volume entropy, the spectrum and the relative densities of visual and harmonic measures on the ideal boundary. Then, we prove an asymptotic analogue of the classical mean value property of harmonic manifolds, and we characterize asymptotically harmonic manifolds, among Cartan–Hadamard spaces of strictly negative curvature, by the existence of an asymptotic equivalent \(\tau (u)\mathrm {e}^{Er}\) for the volume-density of geodesic spheres (with \(\tau \) constant in case \(DR_M\) is bounded). Finally, we show the existence of a Margulis function, and explicitly compute it, for all asymptotically harmonic manifolds.     

A parallel radix‐4 block cyclic reduction algorithm

A conventional block cyclic reduction algorithm operates by halving the size of the linear system at each reduction step, that is, the algorithm is a radix‐2 method. An algorithm analogous to the block cyclic reduction known as the radix‐q partial solution variant of the cyclic reduction (PSCR) method allows the use of higher radix numbers and is thus more suitable for parallel architectures as it requires fever reduction steps. This paper presents an alternative and more intuitive way of deriving a radix‐4 block cyclic reduction method for systems with a coefficient matrix of the form tridiag{ ? I,D, ? I}. This is performed by modifying an existing radix‐2 block cyclic reduction method. The resulting algorithm is then parallelized by using the partial fraction technique. The parallel variant is demonstrated to be less computationally expensive when compared to the radix‐2 block cyclic reduction method in the sense that the total number of emerging subproblems is reduced. The method is also shown to be numerically stable and equivalent to the radix‐4 PSCR method. The numerical results archived correspond to the theoretical expectations. Copyright © 2013 John Wiley & Sons, Ltd.     

A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows

The growing cost of transportation and distribution pushes companies, especially small and medium transportation enterprises, to form partnership and to exploit economies of scale. On the other hand, to increase their competitiveness on the market, companies are asked to consider preferences of the customers as well. Therefore, tools for logistics management need to manage collective resources, as many depots and heterogeneous fleets, providing flexible preference handling at the same time. In this paper we tackle a pickup and delivery vehicle routing problem involving such aspects; customers place preferences on visiting time (represented as soft time windows), and their violation is allowed at a price. Our interest in this problem stems from an ongoing industrial project. First we propose an exact branch-and-price algorithm, having as a core advanced dynamic programming techniques. Then we analyze through a computational campaign the impact of soft time windows management on the optimal solution in terms of both routing and overall distribution costs. Our experiments show that our approach can solve instances of real size, and clarify the practical usefulness of soft time windows management.     

Mass transport problems for the Euclidean distance obtained as limits of p-Laplacian type problems with obstacles

In this paper we analyze a mass transportation problem that consists in moving optimally (paying a transport cost given by the Euclidean distance) an amount of a commodity larger than or equal to a fixed one to fulfil a demand also larger than or equal to a fixed one, with the obligation of paying an extra cost of −_g1(x)$-g_1(x)$ for extra production of one unit at location x   and an extra cost of _g2(y)$g_2(y)$ for creating one unit of demand at y  . The extra amounts of mass (commodity/demand) are unknowns of the problem. Our approach to this problem is by taking the limit as p→∞$p\to \infty$ to a double obstacle problem (with obstacles _g1$g_1$, _g2$g_2$) for the p  -Laplacian. In fact, under a certain natural constraint on the extra costs (that is equivalent to impose that the total optimal cost is bounded) we prove that this limit gives the extra material and extra demand needed for optimality and a Kantorovich potential for the mass transport problem involved. We also show that this problem can be interpreted as an optimal mass transport problem in which one can make the transport directly (paying a cost given by the Euclidean distance) or may hire a courier that cost _g2(y)−_g1(x)$g_2(y)-g_1(x)$ to pick up a unit of mass at y and deliver it to x. For this different interpretation we provide examples and a decomposition of the optimal transport plan that shows when we have to use the courier.