2013, 3(2): 203-206. doi: 10.3934/naco.2013.3.203

A two-phase method for multidimensional number partitioning problem

1. 

Institute of Communications Engineering, PLA University of Science and Technology, Nanjing, 210007, China, China

Received  October 2011 Revised  December 2012 Published  April 2013

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.
Citation: Feng Ma, Mingfang Ni. A two-phase method for multidimensional number partitioning problem. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 203-206. doi: 10.3934/naco.2013.3.203
References:
[1]

M. Diaby, Linear programming formulation of the set partitioning problem,, Int. J. Operational Research, 8 (2010), 399.   Google Scholar

[2]

M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness,", W. H. Freeman, (1979).   Google Scholar

[3]

N. Karmarkar and R. M. Karp, The differencing method of set partitioning,, Technical Report UCB/CSD 82/113, (1982).   Google Scholar

[4]

J. Kojić, Integer linear programming model for multidimensional two-way number partitioning problem,, Computer and Mathematics with Applications, 60 (2010), 2302.  doi: 10.1016/j.camwa.2010.08.024.  Google Scholar

[5]

R. E. Korf, Multi-way number partitioning,, in, (2009), 538.   Google Scholar

[6]

R. E. Korf, Objective functions for multi-way number partitioning,, in, (2010).   Google Scholar

[7]

R. E. Korf, A complete anytime algorithm for number partitioning,, Artificial Intelligence, 106 (1998), 181.  doi: 10.1016/S0004-3702(98)00086-1.  Google Scholar

[8]

R. E. Korf, From approximate to optimal solutions: A case study of number partitioning,, in, (1995), 266.   Google Scholar

[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.  doi: 10.1016/S0024-3795(98)10032-0.  Google Scholar

show all references

References:
[1]

M. Diaby, Linear programming formulation of the set partitioning problem,, Int. J. Operational Research, 8 (2010), 399.   Google Scholar

[2]

M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness,", W. H. Freeman, (1979).   Google Scholar

[3]

N. Karmarkar and R. M. Karp, The differencing method of set partitioning,, Technical Report UCB/CSD 82/113, (1982).   Google Scholar

[4]

J. Kojić, Integer linear programming model for multidimensional two-way number partitioning problem,, Computer and Mathematics with Applications, 60 (2010), 2302.  doi: 10.1016/j.camwa.2010.08.024.  Google Scholar

[5]

R. E. Korf, Multi-way number partitioning,, in, (2009), 538.   Google Scholar

[6]

R. E. Korf, Objective functions for multi-way number partitioning,, in, (2010).   Google Scholar

[7]

R. E. Korf, A complete anytime algorithm for number partitioning,, Artificial Intelligence, 106 (1998), 181.  doi: 10.1016/S0004-3702(98)00086-1.  Google Scholar

[8]

R. E. Korf, From approximate to optimal solutions: A case study of number partitioning,, in, (1995), 266.   Google Scholar

[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.  doi: 10.1016/S0024-3795(98)10032-0.  Google Scholar

[1]

Helmut Abels, Andreas Marquardt. On a linearized Mullins-Sekerka/Stokes system for two-phase flows. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020467

[2]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

[3]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[4]

Anton A. Kutsenko. Isomorphism between one-Dimensional and multidimensional finite difference operators. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020270

[5]

Tian Ma, Shouhong Wang. Topological phase transition III: Solar surface eruptions and sunspots. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020350

[6]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

[7]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[8]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020276

[9]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[10]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[11]

Nicolas Rougerie. On two properties of the Fisher information. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020049

[12]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014

[13]

Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[14]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[15]

Hua Qiu, Zheng-An Yao. The regularized Boussinesq equations with partial dissipations in dimension two. Electronic Research Archive, 2020, 28 (4) : 1375-1393. doi: 10.3934/era.2020073

[16]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169

[17]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[18]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078

[19]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[20]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250

 Impact Factor: 

Metrics

  • PDF downloads (61)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]