A Complementary Column Generation Approach for the Graph Equipartition Problem

Al-Ykoob, Salem M.; Sherali, Hanif D.

doi:10.15388/20-INFOR391

Informatica

A Complementary Column Generation Approach for the Graph Equipartition Problem

Volume 31, Issue 1 (2020), pp. 1–20

Salem M. Al-Ykoob Hanif D. Sherali

https://doi.org/10.15388/20-INFOR391

Pub. online: 23 March 2020 Type: Research Article

Open Access

Received
1 May 2019

Accepted
1 September 2019

Published
23 March 2020

Abstract

This paper investigates the problem of partitioning a complete weighted graph into complete subgraphs, each having the same number of vertices, with the objective of minimizing the sum of edge weights of the resulting subgraphs. This NP-complete problem arises in many applications such as assignment and scheduling-related group partitioning problems and micro-aggregation techniques. In this paper, we present a mathematical programming model and propose a complementary column generation approach to solve the resulting model. A dual based lower bounding feature is also introduced to curtail the notorious tailing-off effects often induced when using column generation methods. Computational results are presented for a wide range of test problems.

References

Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W., Vance, P.H. (1998). Branch-and-price column generation for solving huge integer programs. Operation Research, 46(3), 316–329.

Bazaraa, M.S., Jarvis, J.J., Sherali, H.D. (2010). Linear Programming and Network Flows. 4th ed. John Wiley and Sons, Hoboken, New Jersey.

Carlson, R.C., Nemhauser, G.L. (1966). Scheduling to minimize interaction costs. Operations Research, 14, 52–58.

Chlebikova, J. (1996). Approximating the maximally balanced connected partition problem in graphs. Information Processing Letters, 60, 225–230.

Conforti, M., Rao, M.R. (1990a). The equipartition polytope. I: formulations, dimension and basic facets. Mathematical Programming, 49, 49–70.

Conforti, M., Rao, M.R. (1990b). The equipartition polytope. II: valid inequalities and facets. Mathematical Programming, 49, 71–90.

Domingo-Ferrer, J., Mateo-Sanz, J.M. (2002). Practical data oriented microaggregation for statistical disclosure control. IEEE Transactions on Knowledge and Data Engineering, 14(1), 189–201.

Donath, W.E., Hoffman, A.J. (1973). Lower bounds for the partitioning of graphs. IBM Journal of Research and Development, 17(5), 420–425.

Fan, N., Pardalos, P.M. (2010). Linear and quadratic programming approaches for the general graph partitioning problem. Journal of Global Optimization, 48, 57–71.

Fan, N., Pardalos, P.M. (2012). Multi-way clustering and biclustering by the ratio cut and normalized cut in graphs. Journal of Combinatorial Optimization, 23, 224–251.

Fan, N., Pardalos, P.M., Chinchuluun, A., Pistikopoulos, E.N. (2009). Graph partitioning approaches for analyzing biological networks. In: BIOMAT 2009 – International Symposium on Mathematical and Computational Biology.

Garey, M.R., Johnson, D.S., Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1, 237–267.

Ghoniem, A., Sherali, H.D. (2009). Complementary column generation and bounding approaches for set partitioning formulations. Optimization Letters, 3(1), 123–136.

Goldschmidt, O., Hochbaum, D. (1988). Polynomial algorithm for the k-cut problem. In: 29th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society.

Grotschel, M., Wakabayashi, Y. (1989). A cutting plane algorithm for a clustering problem. Mathematical Programming, 45, 59–96.

Grotschel, M., Wakabayashi, Y. (1990). Facets of the clique partitioning polytope. Mathematical Programming, 47, 367–387.

Hager, W., Krylyuk, Y. (1999). Graph partitioning and continuous quadratic programming. SIAM J. Discret. Math, 12(4), 500–523.

Hager, W., Krylyuk, Y. (2002). Multiset graph partitioning. Math. Meth. Oper Res, 55, 1–10.

Ji, X. (2004). Graph partitioning problem with minimum weight constraints. Technical Report, Rensselaer Polytechnic Institute, Graduate Faculty, New York, NY.

Karisch, S.E., Rendl, F. (1998). Semidefinite programming and graph equipartition. In: Pardalos, P.M., Wolkowicz, H. (Eds.), Topics in Semidefinite and Interior-Point Methods. American Mathematical Society, USA, pp. 77–95.

Karypis, G., Aggarwal, R., Kumar, V., Shekhar, S. (1999). Multilevel hypergraph partitioning: applications in VLSI domain. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 7(1), 69–79.

Laguna, M. (1994). Clustering for the design of SONET rings in interoffice telecommunications. Management Science, 40(11), 1533–1541.

Lisser, A., Rendl, F. (2003). Graph partitioning using linear and semidefinite programming. Mathematical Programming Series B, 95, 91–101.

Mehrotra, A., Trick, M.A. (1998). Cliques and clustering: a combinatorial approach. Operation Research Letters, 22, 1–12.

Mehrotra, A., Johnson, E.L., Nemhauser, G.L. (1998). An optimization based heuristic for political districting. Management Science, 44(8), 1100–1114.

Mitchell, J.E. (2001). Branch-and-cut for the k-way equipartition problem. Technical Report, Rensselaer Polytechnic Institute Troy, NY.

Mitchell, J.E. (2003). Realignment in the National Football League: did they do it right? Naval Research Logistics, 50(7), 683–701.

Park, K., Lee, K., Park, S., Lee, H. (2000). Telecomunication node clustering with node compatibility and network survivability requirements. Management Science, 46(3), 363–374.

Salgado, L.R., Wakabayashi, Y. (2004). Approximation results on balanced connected partitions of graphs. Electronic Notes in Discrete Mathematics, 18, 207–212.

Salido, M.A., Abril, M., Barber, F., Ingolotti, L., Tormos, P., Lova, A. (2007). Domain-dependent distributed models for railway scheduling. Knowledge Based Systems, 20, 186–194.

Schaeffer, S.E. (2007). Survey: graph clustering. Computer Science Review, 1, 27–64.

Sherali, H., Warren, A. (1998). Reformulation-linearization techniques for discrete optimization problems. In: Du, D.Z., Pardalos, P.M. (Eds.), Handbook of Combinatorial Optimization. Springer, Boston, MA, pp. 479–532.

Tan, Y.P., Lu, H. (2003). Video scene clustering by graph partitioning. Electronics Letters, 39(11), 841–842.

Wolkowicz, H., Zhao, Q. (1996). Semidefinite programming relaxations for the graph partitioning problem. Discrete Applied Mathematics, 96–97, 461–479.

Xiao, B., Cao, J., Shao, Z., Zhuge, Q., Shao, E.H.M. (2007). Analysis and algorithms design for the partition of large-scale adaptive mobile wireless networks. Computer Communications, 30, 1899–1912.

Xiaoyun, J., Mitchell, J. (2005). Finding optimal realighment in sports leagues using a branch-and-cut-and-price approach. International Journal of Operational Research, 1(1–2), 101–122.

Zha, H., He, X., Ding, C., Simon, H., Gu, M. (2001). Bipartite graph partitioning and data clustering. In: CIKM’01: Proceedings of the Tenth International Conference on Information and Knowledge Management. ACM Press, New York, NY, pp. 25–32.

Biographies

Al-Ykoob Salem M.

smalyakoob@gmail.com

S.M. Al-Yakoob is an associate professor at the Department of Mathematics, Kuwait University. His research interests include mathematical programming and optimization with applications to real world problems such as location, transportation, scheduling, and timetabling problems.

Sherali Hanif D.

hanifs@vt.edu

H.D. Sherali is a University Distinguished Professor Emeritus at the Industrial and Systems Engineering Department, Virginia Polytechnic Institute and State University. His areas of research interest are in mathematical optimization modelling, analysis, and design of algorithms for specially structured linear, nonlinear, and continuous and discrete nonconvex programs, with applications to transportation, location, engineering and network design, production, economics, and energy systems. He has published over 351 refereed articles in various operations research journals and has (co-)authored nine books, with a total Google Scholar citation count of over 35,700 and an H-index of 75. He is an elected member of the National Academy of Engineering, a fellow of both INFORMS and IIE, and a member of the Virginia Academy of Science Engineering and Medicine.

Full article Related articles Cited by

Open access article under the CC BY license.

Keywords

graph partitioning column generation complementary column generation mixed-integer programming

Funding

This work was supported by Kuwait University under Research Grant No. [SM03/14].

Metrics

since January 2020

1410 Article info views	711 Full article views
767 PDF downloads	234 XML downloads

RSS

Authors

Abstract

References

Biographies

Export citation

Copy and paste formatted citation

Download citation in file