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-427.  Google Scholar

[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. Google Scholar

[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). Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. 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-228. 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-427.  Google Scholar

[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. Google Scholar

[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). Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

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

[1]

Tien-Fu Liang, Hung-Wen Cheng. Multi-objective aggregate production planning decisions using two-phase fuzzy goal programming method. Journal of Industrial & Management Optimization, 2011, 7 (2) : 365-383. doi: 10.3934/jimo.2011.7.365

[2]

M. S. Lee, B. S. Goh, H. G. Harno, K. H. Lim. On a two-phase approximate greatest descent method for nonlinear optimization with equality constraints. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 315-326. doi: 10.3934/naco.2018020

[3]

Mahdi Roozbeh, Saman Babaie–Kafaki, Zohre Aminifard. Two penalized mixed–integer nonlinear programming approaches to tackle multicollinearity and outliers effects in linear regression models. Journal of Industrial & Management Optimization, 2021, 17 (6) : 3475-3491. doi: 10.3934/jimo.2020128

[4]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

[5]

Massimo Lanza de Cristoforis, aolo Musolino. A quasi-linear heat transmission problem in a periodic two-phase dilute composite. A functional analytic approach. Communications on Pure & Applied Analysis, 2014, 13 (6) : 2509-2542. doi: 10.3934/cpaa.2014.13.2509

[6]

Stefan Berres, Ricardo Ruiz-Baier, Hartmut Schwandt, Elmer M. Tory. An adaptive finite-volume method for a model of two-phase pedestrian flow. Networks & Heterogeneous Media, 2011, 6 (3) : 401-423. doi: 10.3934/nhm.2011.6.401

[7]

G. Deugoué, B. Jidjou Moghomye, T. Tachim Medjo. Approximation of a stochastic two-phase flow model by a splitting-up method. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1135-1170. doi: 10.3934/cpaa.2021010

[8]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102

[9]

Jan Prüss, Jürgen Saal, Gieri Simonett. Singular limits for the two-phase Stefan problem. Discrete & Continuous Dynamical Systems, 2013, 33 (11&12) : 5379-5405. doi: 10.3934/dcds.2013.33.5379

[10]

Theodore Tachim Medjo. A two-phase flow model with delays. Discrete & Continuous Dynamical Systems - B, 2017, 22 (9) : 3273-3294. doi: 10.3934/dcdsb.2017137

[11]

Marianne Korten, Charles N. Moore. Regularity for solutions of the two-phase Stefan problem. Communications on Pure & Applied Analysis, 2008, 7 (3) : 591-600. doi: 10.3934/cpaa.2008.7.591

[12]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557

[13]

T. Tachim Medjo. Averaging of an homogeneous two-phase flow model with oscillating external forces. Discrete & Continuous Dynamical Systems, 2012, 32 (10) : 3665-3690. doi: 10.3934/dcds.2012.32.3665

[14]

Eberhard Bänsch, Steffen Basting, Rolf Krahl. Numerical simulation of two-phase flows with heat and mass transfer. Discrete & Continuous Dynamical Systems, 2015, 35 (6) : 2325-2347. doi: 10.3934/dcds.2015.35.2325

[15]

Ciprian G. Gal, Maurizio Grasselli. Longtime behavior for a model of homogeneous incompressible two-phase flows. Discrete & Continuous Dynamical Systems, 2010, 28 (1) : 1-39. doi: 10.3934/dcds.2010.28.1

[16]

Daniela De Silva, Fausto Ferrari, Sandro Salsa. Recent progresses on elliptic two-phase free boundary problems. Discrete & Continuous Dynamical Systems, 2019, 39 (12) : 6961-6978. doi: 10.3934/dcds.2019239

[17]

Jie Jiang, Yinghua Li, Chun Liu. Two-phase incompressible flows with variable density: An energetic variational approach. Discrete & Continuous Dynamical Systems, 2017, 37 (6) : 3243-3284. doi: 10.3934/dcds.2017138

[18]

V. S. Manoranjan, Hong-Ming Yin, R. Showalter. On two-phase Stefan problem arising from a microwave heating process. Discrete & Continuous Dynamical Systems, 2006, 15 (4) : 1155-1168. doi: 10.3934/dcds.2006.15.1155

[19]

Esther S. Daus, Josipa-Pina Milišić, Nicola Zamponi. Global existence for a two-phase flow model with cross-diffusion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 957-979. doi: 10.3934/dcdsb.2019198

[20]

Theodore Tachim-Medjo. Optimal control of a two-phase flow model with state constraints. Mathematical Control & Related Fields, 2016, 6 (2) : 335-362. doi: 10.3934/mcrf.2016006

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]