Abstract
We present an exact method, based on an arc-flow formulation with side constraints, for solving bin packing and cutting stock problems-including multi-constraint variants-by simply representing all the patterns in a very compact graph. Our method includes a graph compression algorithm that usually reduces the size of the underlying graph substantially without weakening the model. Our formulation is equivalent to Gilmore and Gomory's, thus providing a very strong linear relaxation. However, instead of using column-generation in an iterative process, the method constructs a graph, where paths from the source to the target node represent every valid packing pattern. The same method, without any problem-specific parameterization, was used to solve a large variety of instances from several different cutting and packing problems. In this paper, we deal with vector packing, bin packing, cutting stock, cardinality constrained bin packing, cutting stock with cutting knife limitation, bin packing with conflicts, and other problems. We report computational results obtained with many benchmark test datasets, some of them showing a large advantage of this formulation with respect to the traditional ones.

Abstract

Abstract

Abstract
The traveling tournament problem is a sports scheduling problem that includes two major issues in creating timetables: home/away pattern feasibility and travel distance. In this problem, the schedule must be compact: every team plays in every time slot. However, there are some sports leagues that have both home/away pattern restrictions and distance limits, but do not require a compact schedule. In such schedules, one or more teams can have a bye in any time slot. This leads us to a variant of the problem: the relaxed traveling tournament problem. We present a complete search method to solve this problem based on branch-and-bound, metaheuristics and dynamic programming. © 2013, Springer-Verlag Berlin Heidelberg and EURO - The Association of European Operational Research Societies.

Abstract
The uncapacitated facility location problem (UFLP) is a popular combinatorial optimization problem with practical applications in different areas, from logistics to telecommunication networks. While most of the existing work in the literature focuses on minimizing total cost for the deterministic version of the problem, some degree of uncertainty (e.g., in the customers' demands or in the service costs) should be expected in real-life applications. Accordingly, this paper proposes a simheuristic algorithm for solving the stochastic UFLP (SUFLP), where optimization goals other than the minimum expected cost can be considered. The development of this simheuristic is structured in three stages: (i) first, an extremely fast savings-based heuristic is introduced; (ii) next, the heuristic is integrated into a metaheuristic framework, and the resulting algorithm is tested against the optimal values for the UFLP; and (iii) finally, the algorithm is extended by integrating it with simulation techniques, and the resulting simheuristic is employed to solve the SUFLP. Some numerical experiments contribute to illustrate the potential uses of each of these solving methods, depending on the version of the problem (deterministic or stochastic) as well as on whether or not a real-time solution is required.

Abstract
This paper presents a class of packing problems where circles may be placed either inside or outside other circles, the whole set being packed in a rectangle. This corresponds to a practical problem of packing tubes in a container. Before being inserted in the container, tubes may be put inside other tubes in a recursive fashion. A variant of the greedy randomized adaptive search procedure is proposed for tackling this problem, and its performance is assessed in a set of benchmark instances.