Given a set of triangles and a rectangle container, the triangle packing problem is to determine if these triangles can be placed into the container without overlapping. Triangle packing problem is a special case of p...Given a set of triangles and a rectangle container, the triangle packing problem is to determine if these triangles can be placed into the container without overlapping. Triangle packing problem is a special case of polygon packing problem and also NP-hard, so it is unlikely that an efficient and exact algorithm can be developed to solve this problem. In this paper, a new concept of rigid placement is proposed, based on which a discrete solution space called rigid solution space is constructed. Each solution in the rigid solution space can be built by continuously applying legal rigid placements one by one until all the triangles are placed into the rectangle container without overlapping. The proposed Least-Destruction-First (LDF) strategy determines which rigid placement has the privilege to go into the rectangle container. Based on this, a heuristic algorithm is proposed to solve the problem. Combining Least-Destruction-First strategy with backtracking, the corresponding backtracking algorithm is proposed. Computa- tional results show that our proposed algorithms are efficient and robust. With slight modification, these techniques can be con- veniently used for solving polygon packing problem.展开更多
Circles packing problem is an NP-hard problem and is di?cult to solve. In this paper, ahybrid search strategy for circles packing problem is discussed. A way of generating new configurationis presented by simulating t...Circles packing problem is an NP-hard problem and is di?cult to solve. In this paper, ahybrid search strategy for circles packing problem is discussed. A way of generating new configurationis presented by simulating the moving of elastic objects, which can avoid the blindness of simulatedannealing search and make iteration process converge fast. Inspired by the life experiences of people,an e?ective personified strategy to jump out of local minima is given. Based on the simulatedannealing idea and personification strategy, an e?ective personified annealing algorithm for circlespacking problem is developed. Numerical experiments on benchmark problem instances show thatthe proposed algorithm outperforms the best algorithm in the literature.展开更多
Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing probl...Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing problem is NP-hard. In this paper, it is shown for even graphs that if such a collection satisfies the condition that it minimizes the quantityon the set of all edge-disjoint cycle collections, then it is a maximum cycle packing. The paper shows that the determination of such a packing can be solved by a dynamic programming approach. For its solution, an-shortest path procedure on an appropriate acyclic networkis presented. It uses a particular monotonous node potential.展开更多
This paper formulates a two-dimensional strip packing problem as a non- linear programming （NLP） problem and establishes the first-order optimality conditions for the NLP problem. A numerical algorithm for solving t...This paper formulates a two-dimensional strip packing problem as a non- linear programming （NLP） problem and establishes the first-order optimality conditions for the NLP problem. A numerical algorithm for solving this NLP problem is given to find exact solutions to strip-packing problems involving up to 10 items. Approximate solutions can be found for big-sized problems by decomposing the set of items into small-sized blocks of which each block adopts the proposed numerical algorithm. Numerical results show that the approximate solutions to big-sized problems obtained by this method are superior to those by NFDH, FFDH and BFDH approaches.展开更多
文摘Given a set of triangles and a rectangle container, the triangle packing problem is to determine if these triangles can be placed into the container without overlapping. Triangle packing problem is a special case of polygon packing problem and also NP-hard, so it is unlikely that an efficient and exact algorithm can be developed to solve this problem. In this paper, a new concept of rigid placement is proposed, based on which a discrete solution space called rigid solution space is constructed. Each solution in the rigid solution space can be built by continuously applying legal rigid placements one by one until all the triangles are placed into the rectangle container without overlapping. The proposed Least-Destruction-First (LDF) strategy determines which rigid placement has the privilege to go into the rectangle container. Based on this, a heuristic algorithm is proposed to solve the problem. Combining Least-Destruction-First strategy with backtracking, the corresponding backtracking algorithm is proposed. Computa- tional results show that our proposed algorithms are efficient and robust. With slight modification, these techniques can be con- veniently used for solving polygon packing problem.
文摘Circles packing problem is an NP-hard problem and is di?cult to solve. In this paper, ahybrid search strategy for circles packing problem is discussed. A way of generating new configurationis presented by simulating the moving of elastic objects, which can avoid the blindness of simulatedannealing search and make iteration process converge fast. Inspired by the life experiences of people,an e?ective personified strategy to jump out of local minima is given. Based on the simulatedannealing idea and personification strategy, an e?ective personified annealing algorithm for circlespacking problem is developed. Numerical experiments on benchmark problem instances show thatthe proposed algorithm outperforms the best algorithm in the literature.
文摘Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing problem is NP-hard. In this paper, it is shown for even graphs that if such a collection satisfies the condition that it minimizes the quantityon the set of all edge-disjoint cycle collections, then it is a maximum cycle packing. The paper shows that the determination of such a packing can be solved by a dynamic programming approach. For its solution, an-shortest path procedure on an appropriate acyclic networkis presented. It uses a particular monotonous node potential.
基金State Foundstion of Ph.D Units of China(2003-05)under Grant 20020141013the NNSF(10471015)of Liaoning Province,China.
文摘This paper formulates a two-dimensional strip packing problem as a non- linear programming （NLP） problem and establishes the first-order optimality conditions for the NLP problem. A numerical algorithm for solving this NLP problem is given to find exact solutions to strip-packing problems involving up to 10 items. Approximate solutions can be found for big-sized problems by decomposing the set of items into small-sized blocks of which each block adopts the proposed numerical algorithm. Numerical results show that the approximate solutions to big-sized problems obtained by this method are superior to those by NFDH, FFDH and BFDH approaches.
