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 and 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.

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

show all references

References:
[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.

[1]

Tien-Fu Liang, Hung-Wen Cheng. Multi-objective aggregate production planning decisions using two-phase fuzzy goal programming method. Journal of Industrial and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Related Fields, 2016, 6 (2) : 335-362. doi: 10.3934/mcrf.2016006

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]