Article Contents
Article Contents

# A two-phase method for multidimensional number partitioning problem

• The multidimensional number partitioning problem is to split a given set of integer vectors into two disjoint subsets, such that the sums of the elements in the two subsets are equal or nearly equal on every coordinate. This partitioning problem is in fact NP-hard. In this paper, we propose an optimization method for this problem. The proposed method involves recasting the original problem as a two-phase optimization problem. First, candidate partitions are obtained by using the method proposed in [4]. Then the optimal one is selected from the obtained candidate partitions. An example is given to illustrate the method.
Mathematics Subject Classification: Primary: 90C10, 05A18; Secondary: 65K05.

 Citation:

•  [1] M. Diaby, Linear programming formulation of the set partitioning problem, Int. J. Operational Research, 8 (2010), 399-427. [2] M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness," W. H. Freeman, New York, 1979. [3] N. Karmarkar and R. M. Karp, The differencing method of set partitioning, Technical Report UCB/CSD 82/113, Computer Science Division, University of California, Berkeley, (1982). [4] J. Kojić, Integer linear programming model for multidimensional two-way number partitioning problem, Computer and Mathematics with Applications, 60 (2010), 2302-2308.doi: 10.1016/j.camwa.2010.08.024. [5] R. E. Korf, Multi-way number partitioning, in "Proceedings of Proceedings of the International Joint Conference on Artificial Intelligence," Pasadena, California, USA, (2009), 538-543. [6] R. E. Korf, Objective functions for multi-way number partitioning, in "Proceedings of the Third Annual Symposium on Combinatorial Search," Atlanta, Georgia, USA, 2010, Available from: http://www.aaai.org/ocs/index.php/SOCS/SOCS10/paper/view/2098. [7] R. E. Korf, A complete anytime algorithm for number partitioning, Artificial Intelligence, 106 (1998), 181-203.doi: 10.1016/S0004-3702(98)00086-1. [8] R. E. Korf, From approximate to optimal solutions: A case study of number partitioning, in "Proceedings of Proceedings of the International Joint Conference on Artificial Intelligence," Montreal, Canada, (1995), 266-272. [9] M. S. Lobo, L. Vandenberghe, S. Boyd and H. Lebret, Applications of second-order cone programming, Linear Algebra and its Applications, 284 (1998), 193-228.doi: 10.1016/S0024-3795(98)10032-0.