Search

International audience; In this paper, we propose to solve the circular packing problem (CPP) whose objective is to pack n different circles Ci of known radius View the MathML source, into the smallest containing circle C. The objective is to determine the radius r of C as well as the coordinates (xi,yi) of the center of the packed circles View the MathML source. CPP is solved by using an adaptive beam search algorithm that combines the beam search, the local position distance and the dichotomous search strategy. Decisions at each node of the developed tree are based on the well-known maximum hole degree that uses the local minimum distance. The computational results, on a set of instances taken from the literature, show the effectiveness of the proposed algorithm.

ED EPS; International audience; In this paper, we propose approximate and exact algorithms for the double constrained two-dimensional guillotine cutting stock problem (DCTDC). The approximate algorithm is a two-stage procedure. The first stage attempts to produce a starting feasible solution to DCTDC by solving a single constrained two dimensional cutting problem, CDTC. If the solution to CTDC is not feasible to DCTDC, the second stage is used to eliminate non-feasibility. The exact algorithm is a branch-and-bound that uses efficient lower and upper bounding schemes. It starts with a lower bound reached by the approximate two-stage algorithm. At each internal node of the branching tree, a tailored upper bound is obtained by solving (relaxed) knapsack problems. To speed up the branch and bound, we implement, in addition to ordered data structures of lists, symmetry, duplicate, and non-feasibility detection strategies which fathom some unnecessary branches. We evaluate the performance of the algorithm on different problem instances which can become benchmark problems for the cutting and packing literature.

International audience; In this paper, we study the circular packing problem (CPP) which consists of packing a set of non-identical circles of known radii into the smallest circle with no overlap of any pair of circles. To solve CPP, we propose a three-phase approximate algorithm. During its first phase, the algorithm successively packs the ordered set of circles. It searches for each circle's "best" position given the positions of the already packed circles where the best position minimizes the radius of the current containing circle. During its second phase, the algorithm tries to reduce the radius of the containing circle by applying (i) an intensified search, based on a reduction search interval, and (ii) a diversified search, based on the application of a number of layout techniques. Finally, during its third phase, the algorithm introduces a restarting procedure that explores the neighborhood of the current solution in search for a better ordering of the circles. The performance of the proposed algorithm is evaluated on several problem instances taken from the literature.

The constrained two-dimensional cutting (C_TDC) problem consists of determining a cutting pattern of a set of n small rectangular piece types on a rectangular stock plate of length L and width W , as to maximize the sum of the profits of the pieces to be cut. Each piece type i , i = 1, …, n , is characterized by a length l i , a width w i , a profit (or weight) c i and an upper demand value b i . The upper demand value is the maximum number of pieces of type i which can be cut on rectangle ( L , W ). In this paper, we study the two-staged fixed orientation C_TDC, noted FC_2TDC. It is a classical variant of the C_TDC where each piece is produced, in the final cutting pattern, by at most two guillotine cuts, and each piece has a fixed orientation. We solve the FC_2TDC problem using several approximate algorithms, that are mainly based upon a strip generation procedure . We evaluate the performance of these algorithms on instances extracted from the literature.

International audience; Learning agents have to deal with the exploration-exploitation dilemma. The choice between exploration and exploitation is very difficult in dynamic systems; in particular in large scale ones such as economic systems. Recent research shows that there is neither an optimal nor a unique solution for this problem. In this paper, we propose an adaptive approach based on meta-rules to adapt the choice between exploration and exploitation. This new adaptive approach relies on the variations of the performance of the agents. To validate the approach, we apply it to economic systems and compare it to two adaptive methods originally proposed by Wilson: one local and one global. Moreover, we compare different exploration strategies and focus on their influence on the performance of the agents.

International audience; Learning agents have to deal with the exploration-exploitation dilemma. The choice between exploration and exploitation is very difficult in dynamic systems; in particular in large scale ones such as economic systems. Recent research shows that there is neither an optimal nor a unique solution for this problem. In this paper, we propose an adaptive approach based on meta-rules to adapt the choice between exploration and exploitation. This new adaptive approach relies on the variations of the performance of the agents. To validate the approach, we apply it to economic systems and compare it to two adaptive methods: one local and one global. Herein, we adapt these two methods, which were originally proposed by Wilson, to economic systems. Moreover, we compare different exploration strategies and focus on their influence on the performance of the agents.

The constrained two-dimensional cutting (C_TDC) problem consists of determining a cutting pattern of a set of n small rectangular piece types on a rectangular stock plate S with length L and width W, to maximize the sum of the profits of the pieces to be cut. Each piece type i, i=1,…,n, is characterized by a length li, a width wi, a profit (or weight) ci, and an upper demand value bi. The upper demand value is the maximum number of pieces of type i that can be cut on S. In this paper, we study the two-staged C_TDC problem, noted C_2TDC. It is a classical variant of the C_TDC where each piece is produced, in the final cutting pattern, by at most two cuts. We solve the C_2TDC problem using an exact algorithm that is mainly based on a bottom-up strategy. We introduce new lower and upper bounds and propose new strategies that eliminate several duplicate patterns. We evaluate the performance of the proposed exact algorithm on problem instances extracted from the literature and compare it to the performance of an existing exact algorithm.