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]

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]

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

[4]

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

[5]

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

[6]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019102

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009

[20]

Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks & Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]