1,721,138 research outputs found
Algorithms for packing and scheduling problems
No full textWe survey the main result presented in the author’s Ph.D Thesis (Monaci 2001), discussed on January 2002 at the University of Bologna (Italy) and supervised by Paolo Toth and Silvano Martello. The thesis deals with exact and heuristic approaches for solving a class of combinatorial optimization problems, with particular emphasis on Two-Dimensional Packing problems and Scheduling problems
Proximity search heuristics for wind farm optimal layout
Full text linkA heuristic framework for turbine layout optimization in a wind farm is proposed that combines ad-hoc heuristics and mixed-integer linear programming. In our framework, large-scale mixed-integer programming models are used to iteratively refine the current best solution according to the recently-proposed proximity search paradigm. Computational results on very large scale instances involving up to 20,000 potential turbine sites prove the practical viability of the overall approach
On the Robust Knapsack Problem
No full textWe consider an uncertain variant of the knapsack problem that arises when the exact weight of each item is not exactly known in advance but belongs to a given interval, and the number of items whose weight differs from the nominal value is bounded by a constant. We analyze the worsening of the optimal solution value with respect to the classical problem, and exactly determine its worst-case performance depending on uncertainty for all parameter configurations. We perform the same analysis for the fractional version of the problem in which one is allowed to pack any fraction of the items. In addition, we derive the worst-case performance ratio with respect to the optimal solution value, for both the fractional problem and for a variant of the well-known greedy algorithm. Finally, we consider a relevant special case and provide a combinatorial algorithm for solving the fractional problem in an efficient way
Partial enumeration algorithms for Two-Dimensional Bin Packing Problem with guillotine constraints
No full textWe consider the variant of the Two-Dimensional Bin Packing Problem in which items have to be obtained by a series of guillotine cuts and cannot be rotated. We present a heuristic algorithm based on partial enumeration, and computationally evaluate its performance on a large set of instances from the literature. Computational experiments show that the algorithm is able to produce proven optimal solutions for a large number of problems, and gives a tight approximation of the optimum in the remaining cases
On the 2-Dimensional Knapsack Problem
No full textWe address the two-dimensional Knapsack Problem (2KP), aimed at packing a maximum-prot subset of rectangles selected from a given set into another rectangle. We consider the natural relaxation of 2KP given by the one-dimensional KP with item weights equal to the rectangle areas, proving the worst-case performance of the associated upper bound, and present and compare computationally four exact algorithms based on the above relaxation, showing their eectiveness
An Exact Approach to the Strip Packing Problem
No full textWe consider the problem of orthogonally packing a given set of rectangular items into a given strip, by minimizing the overall height of the packing. The problem is NP-hard in the strong sense, and finds several applications in cutting and packing. We propose a new relaxation that produces good lower bounds and gives information to obtain effective heuristic algorithms. These results are used in a branch-and-bound algorithm, which was able to solve test instances from the literature involving up to 200 items
Models and algorithms for packing rectangles into the smallest square
No full textWe consider the problem of determining the smallest square into which a given set of rectangular items can be packed without overlapping. We present an ILP model, an exact approach based on the iterated execution of a two-dimensional packing algorithm, and a randomized metaheuristic. Such approaches are valid both for the case where the rectangles have fixed orientation and the case where they can be rotated by 90°. We computationally evaluate the performance and the limits of the proposed approaches on a large set of instances, including a number of classical benchmarks from the literature, for both cases above, and for the special case where the items are squares
Airport Ground Service Equipment Allocation
No full textThe development of air traffic during the last years has greatly increased the density of aircraft in the airspace and the congestion on major airports. Indeed, sensible delays may be caused by ground operations and it is crucial to develop decision support tools helping increasing the efficiency and the safety of the apron area. This is the purpose of the recently launched European sponsored project “Integrated Airport Apron Safety Fleet Management – AAS”. In this paper, we consider the problem of efficiently providing the necessary ground service equipment and staff to aircraft on the apron. We propose a mathematical formulation for the problem and prove that the problem is NP-hard. A fast sequential heuristic is then suggested, to integrate the already existing real time dispatching decision support system. The procedure has been preliminary tested with data from one major airport, showing to be able to improve efficiency and reduce delays caused by handling operations
Branching on nonchimerical fractionalities
No full textWe address methods for selecting the branching variable in an enumerative algorithm for Mixed-Integer Programs, providing heuristics to speed-up strong branching computation and to reduce the set of variables candidate for branching. Extensive computational results on instances from the literature show that, even in our proof-of-concept implementation, a certain speedup can be achieved with respect to state-of-the-art branching strategies
- …
