•Multiple knapsack problems with assignment-type side constraints.•Managerial applications in transportation logistics and emergency relocations.•Mathematical model and relaxations.•Constructive and ...meta-heuristic algorithms.•Computational experiments on benchmarks from the literature and on new test instances.
We consider a variant of the multiple knapsack problem in which some assignment-type side constraints have to be satisfied. The problem finds applications in logistics sectors related, e.g., to transportation and maritime shipping. We derive upper bounds from Lagrangian and surrogate relaxations of a mathematical model of the problem. We introduce a constructive heuristic and a metaheuristic refinement. We study the computational complexity of the proposed methods and evaluate their practical performance through extensive computational experiments on benchmarks from the literature and on new sets of randomly generated instances.
Two-dimensional packing problems: A survey Lodi, Andrea; Martello, Silvano; Monaci, Michele
European Journal of Operational Research,
09/2002, Letnik:
141, Številka:
2
Book Review, Journal Article
Recenzirano
We consider problems requiring to allocate a set of rectangular items to larger rectangular standardized units by minimizing the waste. In
two-dimensional bin packing problems these units are finite ...rectangles, and the objective is to pack all the items into the minimum number of units, while in
two-dimensional strip packing problems there is a single standardized unit of given width, and the objective is to pack all the items within the minimum height. We discuss mathematical models, and survey lower bounds, classical approximation algorithms, recent heuristic and metaheuristic methods and exact enumerative approaches. The relevant special cases where the items have to be packed into rows forming levels are also discussed in detail.
We consider a generalization of the 0–1 knapsack problem in which the profit of each item can take any value in a range characterized by a minimum and a maximum possible profit. A set of specific ...profits is called a scenario. Each feasible solution associated with a scenario has a
regret
, given by the difference between the optimal solution value for such scenario and the value of the considered solution. The interval min–max regret knapsack problem (MRKP) is then to find a feasible solution such that the maximum regret over all scenarios is minimized. The problem is extremely challenging both from a theoretical and a practical point of view. Its decision version is complete for the second level of the polynomial hierarchy hence it is most probably not in
. In addition, even computing the regret of a solution with respect to a scenario requires the solution of an
-hard problem. We examine the behavior of classical combinatorial optimization approaches when adapted to the solution of the MRKP. We introduce an iterated local search approach and a Lagrangian-based branch-and-cut algorithm and evaluate their performance through extensive computational experiments.
The problem addressed in this paper is that of orthogonally packing a given set of rectangular-shaped items into the minimum number of three-dimensional rectangular bins. The problem is strongly ...NP-hard and extremely difficult to solve in practice. Lower bounds are discussed, and it is proved that the asymptotic worst-case performance ratio of the continuous lower bound is 1/8. An exact algorithm for filling a single bin is developed, leading to the definition of an exact branch-and-bound algorithm for the three-dimensional bin packing problem, which also incorporates original approximation algorithms. Extensive computational results, involving instances with up to 90 items, are presented: It is shown that many instances can be solved to optimality within a reasonable time limit.
While the 1980s were focused on the solution of large sized “easy” knapsack problems (KPs), this decade has brought several new algorithms, which are able to solve “hard” large sized instances. We ...will give an overview of the recent techniques for solving hard KPs, with special emphasis on the addition of cardinality constraints, dynamic programming, and rudimentary divisibility. Computational results, comparing all recent algorithms, are presented.
We 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.
Transportation problems involving routing and loading at the same time are
currently a hot topic in combinatorial optimization. The interest of
researchers and practitioners is motivated by the ...intrinsic difficulty of
this research area, which combines two computationally hard problems, and by
its practical relevance in important real world applications. This annotated
bibliography aims at collecting, in a systematic way, the most relevant
results obtained in the area of vehicle routing with loading constraints,
with the objective of stimulating further research in this promising area.
nema
•Bin packing and cutting stock problems.•State of the art of mathematical models and exact approaches.•Software and computational experiments.
We 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.
PDF
