Explore the vast range of titles available.

Forecasting volumes of incoming calls is the first step of the workforce planning process in call centers and represents a prominent issue from both research and industry perspectives. We investigate the application of Neural Networks to predict incoming calls 24 hours ahead. In particular, a Machine Learning deep architecture known as Echo State Network, is compared with a completely different rolling horizon shallow Neural Network strategy, in which the lack of recurrent connections is compensated by a careful input selection. The comparison, carried out on three different real world datasets, reveals better predictive performance for the shallow approach. The latter appears also more robust and less demanding, reducing the inference time by a factor of 2.5 to 4.5 compared to Echo State Networks.

We introduce orbital branching , an effective branching method for integer programs containing a great deal of symmetry. The method is based on computing groups of variables that are equivalent with respect to the symmetry remaining in the problem after branching, including symmetry that is not present at the root node. These groups of equivalent variables, called orbits, are used to create a valid partitioning of the feasible region that significantly reduces the effects of symmetry while still allowing a flexible branching rule. We also show how to exploit the symmetries present in the problem to fix variables throughout the branch-and-bound tree. Orbital branching can easily be incorporated into standard integer programming software. Through an empirical study on a test suite of symmetric integer programs, the question as to the most effective orbit on which to base the branching decision is investigated. The resulting method is shown to be quite competitive with a similar method known as isomorphism pruning and significantly better than a state-of-the-art commercial solver on symmetric integer programs.

Clique inequalities appear in linear descriptions of many combinatorial optimisation problems. In general, they form an exponential family and, in addition, the associated separation problem is strongly NP-hard, being equivalent to a maximum weight clique problem. Therefore, most of the known (both exact and heuristic) separation procedures follow the decomposition scheme of a maximum clique algorithm. We introduce a new heuristic, aimed at constructing a collection of (violated) clique inequalities covering all the edges of the underlying graph. We present an extensive computational experience showing that this closely approximates the results of an exact separation oracle while being faster than standard heuristics.

We address some special cases of job shop and flow shop scheduling problems with s-precedence constraints. Unlike the classical setting, in which precedence constraints among the tasks of a job are finish–start, here the task of a job cannot start before the task preceding it has started. We give polynomial exact algorithms for the following problems: a two-machine job shop with two jobs when recirculation is allowed (i.e., jobs can visit the same machine many times), a two-machine flow shop, and an m-machine flow shop with two jobs. We also point out some special cases whose complexity status is open.

A great deal of research has been focusing, since the early seventies, on finding strong relaxations for the stable set problem. Polyhedral combinatorics techniques have been at first developed to strengthen the natural linear formulation. Afterward, strong semidefinite programming relaxations have been deeply investigated. Nevertheless, the resulting integer programming (IP) algorithms cannot be regarded as being quite successful in practice, as most of the relaxations give rise to one out of two extreme situations: either provide weak bounds at low computational cost or give good bounds (sometimes excellent) but too demanding to compute. In this paper we present a method to bridge such a gap. In particular, a new lift-and-project relaxation is obtained by a problem-specific variant of the lifting operator M ( K , K ) by Lovász and Schrijver, combined with Benders decomposition. This yields strong cutting planes, generated by solving a cut generating linear program. An extensive computational experience shows that embedding these cuts in a branch-and-cut framework significantly reduces the size of the enumeration trees as well as the CPU times with respect to state-of-the-art IP algorithms.

The introduction of digital terrestrial broadcasting all over Europe requires a complete and challenging replanning of in-place analog systems. However, an abrupt migration of resources (transmitters and frequencies) from analog to digital networks cannot be accomplished because the analog services must be preserved temporarily. Hence, a multiobjective problem arises, in which several networks sharing a common set of resources have to be designed. This problem is referred to as the network packing problem. In Italy, this problem is particularly challenging because of a large number of transmitters, orographical features, and strict requirements imposed by Italian law. In this paper, we report our experience in developing solution methods at the major Italian broadcaster Radiotelevisione Italiana (RAI S.p.A.). We propose a two-stage heuristic. In the first stage, emission powers are assigned to each network separately. In the second stage, frequencies are assigned to all networks so as to minimize the loss from mutual interference. A software tool incorporating our methodology is currently in use at RAI to help discover and select high-quality alternatives for the deployment of digital equipment.

Although the lift-and-project operators of Lovász and Schrijver have been the subject of intense study, their M ( K , K ) operator has received little attention. We consider an application of this operator to the stable set problem. We begin with an initial linear programming (LP) relaxation consisting of clique and non-negativity inequalities, and then apply the operator to obtain a stronger extended LP relaxation. We discuss theoretical properties of the resulting relaxation, describe the issues that must be overcome to obtain an effective practical implementation, and give extensive computational results. Remarkably, the upper bounds obtained are sometimes stronger than those obtained with semidefinite programming techniques.

Issue Title: Combinatorial Optimization and Application in Memory of Mario Lucertini, Guest Editors: Claudio Arbib, Fabrizio Rossi and Stefano Smriglio

The Lovász theta function \\(\\theta(G)\\) provides a very good upper bound on the stability number of a graph \\(G\\). It can be computed in polynomial time by solving a semidefinite program (SDP), which also turns out to be fairly tractable in practice. Consequently, \\(\\theta(G)\\) achieves a hard-to-beat trade-off between computational effort and strength of the bound. Indeed, several attempts to improve the theta bound are documented, mainly based on playing around the application of the \\(N_+(\\cdot)\\) lifting operator of Lovász and Schrijver to the classical formulation of the maximum stable set problem. Experience shows that solving such SDP-s often struggles against practical intractability and requires highly specialized methods. We investigate the application of such an operator to two different linear formulations based on clique and nodal inequalities, respectively. Fewer inequalities describe these two and yet guarantee that the resulting SDP bound is at least as strong as \\(\\theta(G)\\). Our computational experience, including larger graphs than those previously documented, shows that upper bounds stronger than \\(\\theta(G)\\) can be accessed by a reasonable additional effort using the clique-based formulation on sparse graphs and the nodal-based one on dense graphs.