Abstract A novel sphere packing problem is introduced. A maximum number of spheres of different radii should be placed such that the spheres do not overlap and their centers fulfill a quasi-containment condition. The latter allows the spheres to lie partially outside the given cuboidal container. Moreover, specified ratios between the placed spheres of different radii must be satisfied. A corresponding mixed-integer nonlinear programming model is formulated. It enables the exact solution of small instances. For larger instances, a heuristic strategy is proposed, which relies on techniques for the generation of feasible points and the decomposition of open dimension problems. Numerical results are presented to demonstrate the viability of the approach.

Data centres and similar server clusters consume a large amount of energy. However, not all consumed energy produces useful work. Servers consume a disproportional amount of energy when they are idle, underutilised, or overloaded. The effect of these conditions can be minimised by attempting to balance the demand for and the supply of resources through a careful prediction of future workloads and their efficient consolidation. In this paper we extend the cutting stock problem for consolidating workloads having stochastic characteristics. Hence, we employ the aggregate probability density function of co-located and simultaneously executing services to establish valid patterns. A valid pattern is one yielding an overall resource utilisation below a set threshold. We tested the scope and usefulness of our approach on a 16-core server with 29 different benchmarks. The workloads of these benchmarks have been generated based on the CPU utilisation traces of 100 real-world virtual machines which we obtained from a Google data centre hosting more than 32000 virtual machines. Altogether, we considered 600 different consolidation scenarios during our experiment. We compared the performance of our approach-system overload probability, job completion time, and energy consumption-with four existing/proposed scheduling strategies. In each category, our approach incurred a modest penalty with respect to the best performing approach in that category, but overall resulted in a remarkable performance clearly demonstrating its capacity to achieve the best trade-off between resource consumption and performance.

We present a new approach for analog receive beamforming if phase shifters and amplifiers have finite resolution only. Then, the maximization of the signal-to-interference-plus-noise ratio (SINR) is a discrete optimization problem with a nonconcave objective function. The discrete maximization problem is solved exactly by means of a branch-and-bound algorithm. Based on the Capon method, we derive a new and efficient way of computing upper SINR-bounds for the subproblems occurring at the nodes of the branch-and-bound tree. Results of numerical simulations are provided and compared to an earlier approximate approach.

Using CDMA technology, one has to contend with interference in frequency-selective channels caused by multipath propagation and fading. Transmitter-based methods such as zero forcing joint transmission and transmit Wiener filter only reduce the bit error rate indirectly and do not exploit the knowledge of the transmit data symbols. Nonlinear optimization strategies, e.g., the Constrained Minimum BER MUT approach, outperform such methods while the computational complexity prevents their implementation. In this paper, a spread-spectrum TDD-CDMA downlink transmission system with 4-QAM modulation is considered, whereas perfect channel knowledge both in the transmitter and the receiver is assumed. Deriving a convex optimization problem, an alternative solution method with considerable decrease of the complexity is proposed.

Complementarity solvers are continually being challenged by modelers demanding improved reliability and scalability. Building upon a strong theoretical background, the semismooth algorithm has the potential to meet both of these requirements. We discuss relevant theory associated with the algorithm and then describe a sophisticated implementation in detail. Particular emphasis is given to the use of preconditioned iterative methods to solve the (nonsymmetric) systems of linear equations generated at each iteration and robust methods for dealing with singularity. Results on the MCPLIB test suite indicate that the code is reliable and efficient and scales well to very large problems.