Abstract
In this paper, we are interested in studying the maximum ratio clique problem (MRCP) that is a variant of the classical maximum weight clique problem. For a given graph, we suppose that each vertex of the graph is weighted by a pair of rational numbers. The objective of MRCP consists in finding a maximal clique with the largest ratio between two sets of weights that are assigned to its vertices. It has been proven that the decision version of this problem is NP-complete and it is hard to solve MRCP for large instances. Hence, this paper looks for introducing an efficient approach based on Difference of Convex functions (DC) programming and DC Algorithm (DCA) for solving MRCP. Then, we verify the performance of the proposed method. For this purpose, we compare the solutions of DCA with the previously published results. As a second objective of this paper, we identify some valid inequalities and evaluate empirically their influence in solving MRCP. According to the numerical experiments, DCA provides promising and competitive results. Furthermore, the introduction of the valid inequalities improves the computational time of the classical approaches.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Boginski, V., Butenko, S., Pardalos, P.: Mining market data: a network approach. Comput. Oper. Res. 33, 3171–3184 (2006)
Ibaraki, T.: Parametric approaches to fractional programs. Math. Prog. 26, 345–362 (1983)
Isbell, J.R., Marlow, W.H.: Attrition games. Naval Res. Logist. Q 3(1-2), 71–94 (1956)
Kröller, A., Moeini, M., Schmidt, C.: A Novel Efficient Approach for Solving the Art Gallery Problem. In: Ghosh, S.K., Tokuyama, T. (eds.) WALCOM 2013. LNCS, vol. 7748, pp. 5–16. Springer, Heidelberg (2013)
Lawler, E.L.: Combinatorial optimization: networks and matroids. Holt, Rinehart and Winston, New York (1976)
Le Thi, H.A.: Contribution à l’optimisation non convexe et l’optimisation globale: Théorie, Algorithmes et Applications. Habilitation à Diriger des Recherches, Université de Rouen (1997)
Le Thi, H.A., Pham Dinh, T.: A continuous approach for globally solving linearly constrained quadratic zero-one programming problems. Optimization 50(1-2), 93–120 (2001)
Le Thi, H.A., Pham Dinh, T.: The DC (difference of convex functions) Programming and DCA revisited with DC models of real world non convex optimization problems. Annals of Operations Research 133, 23–46 (2005)
Le Thi, H.A., Pham Dinh, T., Huynh, V.N.: Exact Penalty Techniques in DC Programming. Research Report, LMI, INSA-Rouen, France (2005)
Le Thi, H.A., Moeini, M.: Portfolio selection under buy-in threshold constraints using DC programming and DCA. In: International Conference on Service Systems and Service Management (IEEE/SSSM 2006), pp. 296–300 (2006)
Le Thi, H.A., Moeini, M., Pham Dinh, T.: Portfolio Selection under Downside Risk Measures and Cardinality Constraints based on DC Programming and DCA. Computational Management Science 6(4), 477–501 (2009)
Le Thi, H.A., Moeini, M., Pham Dinh, T.: DC Programming Approach for Portfolio Optimization under Step Increasing Transaction Costs. Optimization 58(3), 267–289 (2009)
Le Thi, H.A., Moeini, M., Pham Dinh, T., Judice, J.: A DC Programming Approach for Solving the Symmetric Eigenvalue Complementarity Problem. Computational Optimization and Applications 51, 1097–1117 (2012)
Le Thi, H.A., Moeini, M.: Long-Short Portfolio Optimization under Cardinality Constraints by Difference of Convex Functions Algorithm. Journal of Optimization Theory and Applications 161(1), 199–224 (2014)
Liu, Y., Shen, X., Doss, H.: Multicategory ψ-Learning and Support Vector Machine: Computational Tools. Journal of Computational and Graphical Statistics 14, 219–236 (2005)
Luce, R., Perry, A.: A method of matrix analysis of group structure. Psychometrika 14, 95–116 (1949)
Nalan, G., Le Thi, H.A., Moeini, M.: Robust investment strategies with discrete asset choice constraints using DC programming. Optimization 59(1), 45–62 (2010)
Pham Dinh, T., Le Thi, H.A.: Convex analysis approach to d.c. programming: Theory, Algorithms and Applications. Acta Mathematica Vietnamica, dedicated to Professor Hoang Tuy on the occasion of his 70th birthday 22(1), 289–355 (1997)
Pham Dinh, T., Le Thi, H.A.: DC optimization algorithms for solving the trust region subproblem. SIAM J. Optimization 8, 476–505 (1998)
Prokopyev, O.A., Huang, H., Pardalos, P.M.: On complexity of unconstrained hyperbolic 0-1 programming problems. Oper. Res. Lett. 3(3), 312–318 (2005)
Sethuraman, S., Butenko, S.: The Maximum Ratio Clique Problem. Comp. Man. Sci. 12(1), 197–218 (2015)
Wu, T.: A note on a global approach for general 0–1 fractional programming. Eur. J. Oper. Res. 101(1), 220–223 (1997)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Moeini, M. (2015). The Maximum Ratio Clique Problem: A Continuous Optimization Approach and Some New Results. In: Le Thi, H., Pham Dinh, T., Nguyen, N. (eds) Modelling, Computation and Optimization in Information Systems and Management Sciences. Advances in Intelligent Systems and Computing, vol 359. Springer, Cham. https://doi.org/10.1007/978-3-319-18161-5_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-18161-5_19
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18160-8
Online ISBN: 978-3-319-18161-5
eBook Packages: EngineeringEngineering (R0)