98 research outputs found
Replication Data for: Exact decomposition approaches for a single container loading problem with stacking constraints and medium-sized weakly heterogeneous items
No full textThis repository contains the code for all algorithms discussed in the paper "Exact decomposition approaches for a single container loading problem with stacking constraints and medium-sized weakly heterogeneous items" by Maxence Delorme and Joris Wagenaar
Replication Data for "Bounds and heuristic algorithms for the bin packing problem with minimum color fragmentation"
No full textThis repository contains the tested instances and code for all algorithms discussed in the paper "Bounds and Heuristic Algorithms for the Bin Packing Problem with Minimum Color Fragmentation" by Mathijs Barkel, Maxence Delorme, Enrico Malaguti and Michele Monaci
Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems
Full text linkWe study pseudopolynomial formulations for the classical bin packing and cutting stock problems. We first propose an overview of dominance and equivalence relations among the main pattern-based and pseudopolynomial formulations from the literature. We then introduce reflect, a new formulation that uses just half of the bin capacity to model an instance and needs significantly fewer constraints and variables than the classical models. We propose upper- and lower-bounding techniques that make use of column generation and dual information to compensate reflect weaknesses when bin capacity is too high. We also present nontrivial adaptations of our techniques that solve two interesting problem variants, namely the variable-sized bin packing problem and the bin packing problem with item fragmentation. Extensive computational tests on benchmark instances show that our algorithms achieve state of the art results on all problems, improving on previous algorithms and finding several new proven optimal solutions
Mathematical models and decomposition methods for the multiple knapsack problem
Full text linkWe consider the multiple knapsack problem, that calls for the optimal assignment of a set of items, each having a profit and a weight, to a set of knapsacks, each having a maximum capacity. The problem has relevant managerial implications and is known to be very difficult to solve in practice for instances of realistic size. We review the main results from the literature, including a classical mathematical model and a number of improvement techniques. We then present two new pseudo-polynomial formulations, together with specifically tailored decomposition algorithms to tackle the practical difficulty of the problem. Extensive computational experiments show the effectiveness of the proposed approaches
Replication Data for: Exact algorithms for a parallel machine scheduling problem with workforce and contiguity constraints
No full textThis repository contains the instances used in the paper "Exact algorithms for a parallel machine scheduling problem with workforce and contiguity constraints" by Giulia Caselli, Maxence Delorme, Manuel Iori, and Carlo Alberto Magni
Bin packing and cutting stock problems: Mathematical models and exact algorithms
No full textWe review the most important mathematical models and algorithms developed for the exact solution of the one-dimensional bin packing and cutting stock problems, and experimentally evaluate, on state-of-the art computers, the performance of the main available software tools
Logic based Benders' decomposition for orthogonal stock cutting problems
Full text linkWe consider the problem of packing a set of rectangular items into a strip of fixed width, without overlapping, using minimum height. Items must be packed with their edges parallel to those of the strip, but rotation by 90° is allowed. The problem is usually solved through branch-and-bound algorithms. We propose an alternative method, based on Benders' decomposition. The master problem is solved through a new ILP model based on the arc flow formulation, while constraint programming is used to solve the slave problem. The resulting method is hybridized with a state-of-the-art branch-and-bound algorithm. Computational experiments on classical benchmarks from the literature show the effectiveness of the proposed approach. We additionally show that the algorithm can be successfully used to solve relevant related problems, like rectangle packing and pallet loading
Integer Linear Programming for the Tutor Allocation Problem: A practical case in a British University
Full text linkIn the Tutor Allocation Problem, the objective is to assign a set of tutors to a set of workshops in order to maximize tutors’ preferences. The problem is solved every year by many universities, each having its own specific set of constraints. In this work, we study the tutor allocation in the School of Mathematics at the University of Edinburgh, and solve it with an integer linear programming model. We tested the model on the 2019/2020 case, obtaining a significant improvement with respect to the manual assignment in use and we showed that such improvement could be maintained while optimizing other key metrics such as load balance among groups of tutors and total number of courses assigned. Further tests on randomly created instances show that the model can be used to address cases of broad interest. We also provide meaningful insights on how input parameters, such as the number of workshop locations and the length of the tutors’ preference list, might affect the performance of the model and the average number of preferences satisfied
Arcflow formulations and constraint generation frameworks for the two-bar charts packing problem
Full text linkWe consider the two-bar charts packing (2-BCPP), a recent combinatorial optimization problem whose aim is to pack a set of one-dimensional items into the minimum number of bins. As opposed to the well-known bin packing problem, pairs of items are grouped to form bar charts, and a solution is only feasible if the first and second items of every bar chart are packed in consecutive bins. After providing a complete picture of the connections between the 2-BCPP and other relevant packing problems, we show how we can use these connections to derive valid lower and upper bounds for the problem. We then introduce two new integer linear programming (ILP) models to solve the 2-BCPP based on a non-trivial extension of the arcflow formulation. Even though both models involve an exponential number of constraints, we show that they can be solved within a constraint generation framework. We then empirically evaluate the performance of our bounds and exact approaches against an ILP model from the literature and demonstrate the effectiveness of our techniques, both on benchmarks inspired by the literature and on new classes of instances that are specifically designed to be hard to solve. The outcomes of our experiments are important for the packing community because they indicate that arcflow formulations can be used to solve targeted packing problems with precedence constraints and also that some of these formulations can be solved with constraint generation
Exact algorithms for a parallel machine scheduling problem with workforce and contiguity constraints
Full text linkWe address a real-world scheduling problem where the objective is to allocate a set of tasks to a set of machines and to a set of workers in such a way that the total weighted tardiness is minimized. Our case study encompasses four types of constraints: precedence, resource, eligibility, and contiguity. While the first three constraints are common in the scheduling literature, contiguity constraints, which can be defined as a form of precedence constraints that requires both a predecessor and its successor to be processed on the same machine with no intermediate jobs in-between (but idle time is allowed), have never been studied in the literature. We present four exact methods to solve the problem: two methods use integer linear programming, one uses constraint programming, and one uses a combinatorial Benders’ decomposition. We introduce method-specific strategies to model the contiguity constraints for each of the proposed methods. We empirically evaluate, through an extensive set of computational experiments, the performance of the four methods on a heterogeneous dataset composed of real, realistic, and random instances, and outline that every method offers a competitive advantage on a targeted subset of instances. We also show that our algorithms can be generalized to solve related scheduling problems with contiguity constraints
- …
