×

Maximum cut in fuzzy nature: models and algorithms. (English) Zbl 1191.90051

Summary: The maximum cut (Max-Cut) problem has extensive applications in various real-world fields, such as network design and statistical physics. In this paper, a more practical version, the Max-Cut problem with fuzzy coefficients, is discussed. Specifically, based on credibility theory, the Max-Cut problem with fuzzy coefficients is formulated as an expected value model, a chance-constrained programming model and a dependent-chance programming model respectively according to different decision criteria. When these fuzzy coefficients are represented by special fuzzy variables like triangular fuzzy numbers and trapezoidal fuzzy numbers, the crisp equivalents of the fuzzy Max-Cut problem can be obtained. Finally, a genetic algorithm combined with fuzzy simulation techniques is designed for the general fuzzy Max-Cut problem under these models and numerical experiment confirms the effectiveness of the designed genetic algorithm.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
90C70 Fuzzy and other nonstochastic uncertainty mathematical programming
05C85 Graph algorithms (graph-theoretic aspects)
05C35 Extremal problems in graph theory

Software:

BiqMac; Biq Mac
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hadlock, F., Finding a maximum cut of a planar graph in polynomial time, SIAM J. Comput., 4, 221-225 (1975) · Zbl 0321.05120
[2] Barahona, F.; Grotschel, M.; Junger, M.; Reinelt, G., An application of combinatorial optimization to statistical physics and circuit layout design, Oper. Res., 36, 493-513 (1988) · Zbl 0646.90084
[3] Poland, J.; Zeugmann, T., Clustering pairwise distances with missing data: Maximum cuts versus normalized cuts, Lecture Notes in Comput. Sci., 4265, 197-208 (2006)
[4] Poljak, S.; Tuza, Zs., Maximum cuts and largest bipartite subgraphs, (Cook, W.; Lováz, L.; Seymour, P., Combinatorial Optimization (1995), American Mathematical Society: American Mathematical Society Providence), 20, R, l · Zbl 0834.05001
[5] Karp, R. M., Reducibility among combinatorial problems, (Miller, R.; Thatcher, J., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-103 · Zbl 0366.68041
[6] Delorme, C.; Poljak, S., Laplacian eigenvalues and the maximum cut problem, Math. Program., 62, 557-574 (1993) · Zbl 0797.90107
[7] Poljak, S.; Rendl, F., Solving the Max-cut problem using eigenvalue, Discrete Appl. Math., 62, 249-278 (1995) · Zbl 0838.90131
[8] Goemans, M. X.; Williamson, D. P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 1115-1145 (1995) · Zbl 0885.68088
[9] Duarte, A.; Fernández, F.; Sánchez, A.; Sanz, A., A hierarchical social metaheuristic for the max-cut problem, Lecture Notes in Comput. Sci., 3004, 84-94 (2004) · Zbl 1177.90417
[10] Xia, G.; Tang, Z.; Li, Y.; Wang, R., Hopfield neural network with hysteresis for maximum cut problem, Neural Inf. Process. Lett. Rev., 4, 2, 19-26 (2004)
[11] Liu, S. T.; Kao, C., Network flow problems with fuzzy arc lengths, IEEE Trans. Syst. Man Cybernet. — Part B: Cybernetics, 34, 1, 765-769 (2004)
[12] Ghateea, M.; Hashemia, S. M.; Hashemib, B.; Dehghanb, M., The solution and duality of imprecise network problems, Comput. Math. Appl., 55, 2767-2790 (2008) · Zbl 1142.90517
[13] Zeng, J.; An, M.; Smith, N. J., Application of a fuzzy based decision making methodology to construction project risk assessment, Int. J. Proj. Manag., 25, 6, 589-600 (2007)
[14] Zadeh, L. A., Fuzzy sets. Inform. Control, 8, 338-353 (1965) · Zbl 0139.24606
[15] Zadeh, L. A., Fuzzy sets as a basis for a theory of possibility, Fuzzy Sets and Systems, 1, 1, 3-28 (1978) · Zbl 0377.04002
[16] Buckley, J. J., Solving possibilistic linear programming problems, Fuzzy Sets and Systems, 31, 329-341 (1989) · Zbl 0671.90049
[17] Wang, H. F.; Wang, M. L., A fuzzy multi-objective linear programming, Fuzzy Sets and Systems, 86, 61-72 (1997)
[18] Okada, S., Fuzzy shortest path problems incorporating interactivity among paths, Fuzzy Sets and Systems, 142, 335-357 (2004) · Zbl 1045.90092
[19] Diamond, P., A fuzzy max-flow min-cut theorem, Fuzzy Sets and Systems, 119, 139-148 (2001) · Zbl 1044.90531
[20] Liu, B., Theory and Practice of Uncertain Programing (2002), Physica-Verlag: Physica-Verlag New York
[21] Liu, B., Uncertainty Theory (2007), Springer-Verlag: Springer-Verlag Berlin
[22] Liu, B.; Liu, Y. K., Expected value of fuzzy variable and fuzzy expected value models, IEEE Trans. Fuzzy Syst., 10, 445-450 (2002)
[23] Liu, B.; Iwamura, K., Chance constrained programming with fuzzy parameters, Fuzzy Sets and Systems, 94, 227-237 (1998) · Zbl 0923.90141
[24] Liu, B., Dependent-chance programming with fuzzy decisions, IEEE Trans. Fuzzy Syst., 7, 3, 354-360 (1999)
[25] Dubois, D.; Prade, H., Possibility Theory: An Approach to Computerized Processing of Uncertainty (1988), Plenum: Plenum New York
[26] Liu, B., A survey of credibility theory, Fuzzy Optim. Decis. Mak., 5, 387-408 (2006) · Zbl 1133.90426
[27] Das, B., A two warehouse supply-chain model under possibility/necessity/ credibility measures, Math. Comput. Modelling, 46, 398-409 (2007) · Zbl 1173.90323
[28] Maity, A. K., A production-recycling-inventory system with imprecise holding costs, Applied Mathematical Modelling, 32, 2241-2253 (2008) · Zbl 1156.90303
[29] Bortolan, G.; Degani, R., A review of some methods for ranking fuzzy subsets, Fuzzy Sets and Systems, 15, 1-19 (1985) · Zbl 0567.90056
[30] Charnes, A.; Cooper, W. W., Chance-constrained programming, Manage. Sci., 6, 1, 73-79 (1959) · Zbl 0995.90600
[31] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning (1989), Addison-Wesley · Zbl 0721.68056
[32] Ding, C.; He, X.; Zha, H.; Gu, M.; Simon, H. D., A min-max cut algorithm for graph partitioning and data clustering, (IEEE International Conference on Data Mining (2001)), 107-114
[33] Johnson, E. L.; Mehrotra, A.; Nemhauser, G. L., Min-cut clustering, Math. Program., 62, 133-151 (1993) · Zbl 0807.90117
[34] Brusco, M.; Stahl, S., Branch-and-Bound Applications in Combinatorial Data Analysis (2005), Spinger · Zbl 1093.62006
[36] Ling, A. F.; Xu, C. X.; Xu, F. M., A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems, European J. Oper. Res., 197, 519-531 (2009) · Zbl 1159.90475
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.