Adaptive beam search lookahead algorithms for the circular packing problem

This paper addresses the circular packing problem (CPP), which consists in packing n circles C_i, each of known radius r_i, i∈N={1, …, n}, into the smallest containing circle C. The objective is to determine the radius r of C as well as the coordinates (x_i, y_i) of the center of C_i, i∈N. CPP is solved using two adaptive algorithms that adopt a binary search to determine r, and a beam search to check the feasibility of packing n circles into C when the radius is fixed at r. A node of level ?, ?=1, …, n, of the beam search tree corresponds to a partial packing of ? circles of N into C. The potential of each node of the tree is assessed using a lookahead strategy that, starting with the partial packing of the current node, assigns each unpacked circle to its maximum hole degree position. The beam search stops either when the lookahead strategy identifies a feasible packing or when it has fathomed all nodes. The computational tests on a set of benchmark instances show the effectiveness of the proposed adaptive algorithms.     

An augmented beam search-based algorithm for the circular open dimension problem

In this paper, we discuss the circular open dimension problem (CODP); that is a problem of the cutting/packing family. In CODP, we are given an initial strip of fixed width W and unlimited length, as well as a finite set N of n circular pieces C_i of known radius r_i,i ∈ N. The objective is to search for a global optimum corresponding to the minimum length of the initial strip containing the n pieces. We propose an augmented algorithm for solving the CODP which combines a beam search, a binary search and the well-known multi-start strategy. In addition, in order to increase the efficiency of the algorithm, we incorporate a strategy based on the separate beams instead of the pooled ones. The performance of the proposed algorithm is evaluated on a set of benchmark instances composed of a group taken from the literature and another group of randomly generated instances. The results show that the proposed algorithm is able to improve several best known solutions of the literature and it remains competitive for the new generated ones.     

An iterative rounding search-based algorithm for the disjunctively constrained knapsack problem

This article proposes an iterative rounding search-based algorithm for approximately solving the disjunctively constrained knapsack problem. The problem can be viewed as a variant of the well-known knapsack problem with some sets of incompatible items. The algorithm considers two key features: a rounding strategy applied to the fractional variables of a linear relaxation and a neighbouring strategy used for improving the quality of the solutions at hand. Both strategies are iterated into a process based on adding a series of (i) valid cardinality constraints and (ii) lower bounds used for bounding the objective function. The proposed algorithm is analysed computationally on a set of benchmark instances of the literature. The proposed algorithm outperforms the Cplex solver and the results obtained improve on most existing solutions.     

Solving the circular open dimension problem by using separate beams and look-ahead strategies

In this paper, a constructive method is investigated for solving the circular open dimension problem (CODP), a problem of the Cutting and Packing family. CODP is a combinatorial optimization problem which is characterized by a set of circular pieces of known radii and a strip of fixed width W and unlimited length. The objective is to determine the smallest rectangle of dimensions (L, W), where L is the length of the rectangle, that will contain all the pieces such that there is no overlapping between the placed pieces and all the demand constraints are satisfied. The method combines the separate-beams search, look-ahead, and greedy procedures. A study concerning both restarting and look-ahead strategies is undertaken to determine the best tuning for the method. The performance of the method is computationally analyzed on a set of instances taken from the literature and for which optimal solutions are not known. Best-known solutions are obtained.     

A parallel algorithm for constrained two-staged two-dimensional cutting problems

In this paper, we solve the two-staged two-dimensional cutting problem using a parallel algorithm. The proposed approach combines two main features: beam search (BS) and strip generation solution procedures (SGSP). BS employs a truncated tree-search, where a selected subset of generated nodes are retuned for further search. SGSP, a constructive procedure, combines a (sub)set of strips for providing both partial lower and complementary upper bounds. The algorithm explores in parallel a subset of selected nodes following the master-slave paradigm. The master processor serves to guide the search-resolution and each slave processor develops its proper way, trying a global convergence. The aim of such an approach is to show how the parallelism is able to efficiently solve large-scale instances, by providing new solutions within a consistently reduced runtime. Extensive computational testing on instances, taken from the literature, shows the effectiveness of the proposed approach.     

Constrained two-dimensional cutting stock problems a best-first branch-and-bound algorithm

In this paper, we develop a new version of the algorithm proposed in Hifi (Computers and Operations Research 24/8 (1997) 727–736) for solving exactly some variants of (un)weighted constrained two-dimensional cutting stock problems. Performance of branch-and-bound procedure depends highly on particular implementation of that algorithm. Programs of this kind are often accelerated drastically by employing sophisticated techniques. In the new version of the algorithm, we start by enhancing the initial lower bound to limit initially the space search. This initial lower bound has already been used in Fayard et al. 1998 (Journal of the Operational Research Society, 49, 1270–1277), as a heuristic for solving the constrained and unconstrained cutting stock problems. Also, we try to improve the upper bound at each internal node of the developed tree, by applying some simple and effcient combinations. Finally, we introduce some new symmetric-strategies used for neglecting some unnecessary duplicate patterns . The performance of our algorithm is evaluated on some problem instances of the literature and other hard-randomly generated problem instances.     

Approximate algorithms for the container loading problem

In this paper we develop several algorithms for solving three–dimensional cutting/packing problems. We begin by proposing an adaptation of the approach proposed in Hifi and Ouafi (1997) for solving two–staged unconstrained two–dimensional cutting problems. We show how the algorithm can be polynomially solved for producing a constant approximation ratio. We then extend this algorithm for developing better approximate algorithms. By using hill–climbing strategies, we construct some heuristics which produce a good trade–off between the computational time and the solution quality. The performance of the proposed algorithms is evaluated on different problem instances of the literature, with different sizes and densities (a total of 144 problem instances).     

Hybrid greedy heuristics based on linear programming for the three‐dimensional single bin‐size bin packing problem

In this paper, we propose to solve the three‐dimensional single bin‐size bin packing problem (3D‐SBSBPP) using a simple strategy based on integer linear programming (ILP) heuristics, without using any improvement based on metaheuristics. We first propose an ILP that is converted into a series of three‐dimensional single knapsack problems (3D‐SKP). Then, the first tailored heuristic can be viewed as a hybrid approach in which both “selection” and “positioning” phases are combined. The first phase serves to select a subset of items where each of these items is susceptible to belonging to an active container. The positioning phase serves to pack a subset of items already preselected by the selection phase. Then, both phases cooperate till packing all items into their corresponding containers. The second heuristic can be viewed as an extended version of the first one. Indeed, before deciding whether the current container is closed or a new container is activated, “a local reoptimization phase” is considered. Finally, both proposed heuristics are evaluated on a set of random instances obtained by using the standard generator scheme of the literature. The provided results show that both proposed heuristics remain competitive when compared to the results obtained by one of the best methods of the literature.     

Algorithms for the circular two‐dimensional open dimension problem

In this paper, we propose three heuristics for the circular two‐dimensional open dimension problem, also known as the circular strip cutting/packing problem. We first propose an open strip generation solution procedure that uses the best local position rule into the open strip. Second, we propose a simple augmented version of the first heuristic by introducing an exchange‐order strategy. Third, we propose a hybrid heuristic that combines beam search and a series of target values belonging to a predetermined interval search. We evaluate the performance of these heuristics on several instances varying from small to large ones. Encouraging results have been obtained.