Complexity of One Packing Optimization Problem
- PDF / 135,136 Bytes
- 9 Pages / 594 x 792 pts Page_size
- 21 Downloads / 182 Views
COMPLEXITY OF ONE PACKING OPTIMIZATION PROBLEM O. M. Trofymchuk,1† V. A. Vasyanin,1‡ and V. N. Kuzmenko2
UDC 519.854.2:004.023
Abstract. The authors consider packing optimization for elements of a square matrix, which are given by positive integers, into blocks of fixed size. The problem is formulated and its combinatorial intractability is discussed. The problem is proved to be NP-complete. This is done by polynomial reduction of an NP-complete minimum-cost integer multicommodity flow problem to this problem. Keywords: packing optimization, integer multicommodity flow, labor input of exhaustive search, polynomial reducibility, NP-complete problems. INTRODUCTION The packing optimization problem considered below (in which elements of rows and columns of a square matrix, specified by positive integer numbers, are packed in a certain way into fixed-size blocks) arises in formalization and optimization of processes of sorting and packing of small-consignment correspondence (loads or messages) into transportation blocks (physical or virtual containers) in transportation networks or in data transmission networks [1, 2]. The essence of the applied problem is to find a rational combination scheme for small-consignment flows (emerging from network nodes) of homogeneous loads (messages) with different destination addresses and their package into transportation blocks (containers) of prescribed size in order to minimize the number of the latter to transport small-consignment correspondence in the whole network under certain conditions of its operation. In the paper, we will consider the statement of “pure” packing problem without cost functions, which can be introduced to estimate the cost of processes of handling and transportation of small-consignment correspondence in real applications. This applied problem is reduced to the problem over elements of a square matrix. The exhaustive search complexity of the problem is analyzed and the problem is proved to be NP-complete. The experimental data are presented, which show the dependence of problem solution on the range of variation of input data and schemes of exhaustive search of candidate solutions. PROBLEM STATEMENT Let there be given a matrix A = || a ij || n ´n with zero diagonal and positive integer elements out of the diagonal. Some operation of union can be executed over matrix elements, with certain constraints being observed. To perform separate operation, element a ij > 0 and a nonempty subset of disjoint indices {k1 , k 2 , K , k m }, distinct from i and j (I nm-=21 k m = Æ, n ³ 3) are chosen. As a result, elements a ik1 , a k1k2 , K , a km j are increased by a ij and element a ij is set to zero. Each transformed a ik1 , a k1k2 , ¼, a km j or not transformed element a ij (when {k1 , k 2 , K , k m } = Æ) is placed 1
Institute of Telecommunications and Global Information Space, National Academy of Sciences of Ukraine, Kyiv, Ukraine, †[email protected]; ‡[email protected]. 2V. M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukrai
Data Loading...
