MORPHOLOGICAL CLIQUE MODEL

Brief Description

Morphological clique model (problem - MCM) is a new generalized combinatorial optimization model for morpological analysis
with vectror-like objective function which consists of the following two parts:
(1) quality (effectiveness, excelence) of selected elements; and
(2) quality of interconnection (compatibility) of selected elements.
This model generalizes some versions of well-known combinatorial problems, for example:
(i) multiple-choice problem;
(ii) assignment/allocation; and
(iii) graph coloring problem.
Morphological clique problem is a basis for "partitioning / synthesis macroheuristic" to solve some
combinatorial problems (e.g., TSP, Minimal Steinter Tree problem, scheduling problem).
Morphological clique model is NP-hard.
The problem is targeted to search for Pareto-efficient decisions.
Solving schemes can be based on the following:
(a) backtracking techniques, (b) dynamic programming, (c) heuristics, (d) enumenative algorithms, (e) approximation approaches.
Morphological clique model can be used to design series-parallel solving strategies (method engineering, model management, etc.).

Basic Levin's References (Morphological Clique Model and Hierarchical Morphological Design approach):
I. Articles:
1.1. M.Sh. Levin, Hierarchical design of user interfaces. In: LNCS, Vol. 876, Springer, pp. 140-151, 1994.
1.2. M.Sh. Levin, Hierarchical morphological multicriteria design of decomposable systems.
Concurrent Engineering: Research and Applications, 4(2), pp. 111-117, 1996.
( journal site )
1.3. M.Sh. Levin, System synthesis with morphological clique problem: Fusion of subsystem evaluation decisions. Information Fusion, 2(3), 225-237, 2001.
( sciencedirect )
( journal site )
1.4. M.Sh. Levin, Towards combinatorial analysis, adaptation, and planning of human-computer systems, Applied Intelligence, 16(3), 235-247, 2002.
( journal site )
1.5. M.Sh. Levin, Modular system synthesis: Example for composite packaged software IEEE Trans. on SMC, Part C, 35(4), 544-553, 2005.
( journal site: IEEE Xplore )
1.6. M.Sh. Levin, Combinatorial optimization in system configuration design. Autom. and Remote Control, vol. 70, no. 3, pp. 519-561, 2009.
( journal site )
II. Books:
2.1. M.Sh. Levin, Combinatorial Engineering of Decomposable Systems, Kluwer (now: Springer), 1998.
( in Amazon )
2.2. M.Sh. Levin, Composite Systems Decisions. Springer, 2006.
( in Amazon )
2.3. M.Sh. Levin, Decision Support Technology for Modular Systems. Electronic book. 341 pp. (in Russian). 2013.
http://www.mslevin.iitp.ru/Levin-bk-Nov2013-071.pdf
(pdf-file)
2.4. M.Sh. Levin, Modular System Design and Evaluation. Springer, 473 p., 2015 (Due: Sep. 2014).
III. Electronic Preprints:
3.1. M.Sh. Levin, Morphological methods for design of modular systems (a survey). Electronic preprint. 20 pp., Jan. 9, 2012.
http://arxiv.org/abs/1201.1712 [cs.SE]
3.2. M.Sh. Levin, Multiset estimates and combinatorial synthesis. Electronic preprint. 30 pp., May 9, 2012.
http://arxiv.org/abs/1205.2046 [cs.SY]

Close optimization problems:

(i) problem of representatives;
(ii) problem of compatible representatives;
(iii) knapsack-like problems;
(iv) maximal clique problem;
(v) quadratic assignment problem;
(vi) multidimensional assignment problem;
(vii) multipartite clique, and
(viii) mixed integer non-linear programming.

Main Engineering Applications (i.e., morphological approach):

(1) design of modular systems;
(2) design/planning of problem solving processes (including test strategies);
(3) coordination of digraphs (searching for a largest common part of digraphs
which are defined at the same set of vertices, etc.);
(4) transformation (improvement, adaptation, reengineering) of systems;
(5) design and adaptation of systems (e.g., human-computer systems);
(6) design of educational plans and processes for "transformation" of specialists;
(7) information synthesis; and
(8) strategic design/technological forecasting.


History & Close Research/Application Directions:

References:
1. M. Hall, Combinatorial Theory, 2nd ed., New York, Wiley, 1986.
References:
1. R.U. Ayres, Technological Forecasting and Long-Time Planning. New York, McGraw-Hill, 1969.
2. J.C. Jones, Design Methods. New York, Wiley, 1981.
3. F. Zwicky, Discovery Invention, Research Through the Morphological Approach. New York, McMillan, 1969.
4. T. Ritchey, Problem strucutring using computer-aided morphological analysis. J. of the ORS, 57(7), 792-801, 2006.
5. T. Ritchey, Wicked Problems - Social Messes. Decision Support Modelling with Morphological Analysis. Springer, 2011.
References:
1. D. Knuth, A. Ratghunathan, The problem of compatible representatives. SIAM J. on Discrete Mathematics, 5(3), 422-427, 1992.
References:
1. T.P. Browning, Applying the design structure matrix to system decomposition and integration problems. IEEE Trans. on Engineering Management, 48(3), 292-306, 2001.
2. A.P. Kusiak, Interface strcuture matrix for analysis of products and processes. Proc. of the 15th CIRP Int. Conf. on Life Cycle Engineeirng LCE 2008, Sydney, Australia, 444-448, 2008.
3. D.V. Steward, The design structure system: A method for managing the design of complex systems. IEEE Trans. on Eng. Management, 28, 71-74, 1981.
4. D.V. Steward, Systems Analysis and management Strcuture, Startegy and Design. Princeton, NJ, Petrocelli Books, 1981.
5. T.P. Sule, P. Mustafa, Modelling detailed information flows in building design with the parameterbased design structure matrix. Design Studies, 27(1), 99-122, 2006.
References:
1. R.A. Howard, Decision analysis: Practice and promise. Management Science, 34(6), 679-696, 1988.
2. J. Singhal, J.L. Katz, A branch-and-fathom algorithm for the long range process design problem. Management Science, 36(4), 513-516, 1990.
References:
1. I. Charon, O. Hundry, Optimal clustering in multipartite graph. Discrete Applied Mathematics, 156(8), 1330-1347, 2008.
2. N. Lytkin, S. Streltsov, L. Perlovsky, I. Muchnik, S. Petrov, Improving representation of search results by multipartite graph clustering of multiple reformulated queries and a novel document representation. Manuscript, 2005; http://company.yandex.ru/grant/205/02_Lytkin__110104.pdf
3. A. Vashist, C.A. Kulikowsky, I. Muchnik, Ortholog clustering on a multipartite graph. IEEE/ACM Trans. on Comput. Biology and Bioinformatics (TCBB), 4(1), 17-27, 2007.
References:
1. M. Dawande, P. Keskinocak, J.M. Swaminathan, S. Teyur, On bipartite and multipartite clique problems. J. of Algorithms, 41(2), 388-403, 2001.
References:
1. L. Mirsky, Transversal Theory. Academic Press, 1971.
2. M. Middendorf, V.G. Timkovsky, Transversal graphs for partially ordered sets: Sequencing, merging and scheduling. J. of Combinatorial Optimization, 3(4), 417-435, 1999.
References:
1. S. Brinkkemper, Method engineering: Engineering of information systems development methods and tools. Informaiton & Software Technology, 38(4), 275-280, 1996.
2. P.J. Agerfalk, S. Brinkkemper, C. Gonzalez, B. Henderson-Seller, F. Karlsson, S. Kelly, J. Ralyte, Modularization constructs in method engineering: Towards common ground? IFIP International Federation for Information Processing, vol. 244, 359-368, 2007.
References:
1. W.A. Muhanna, R.A. Pick, Meta-modeling concepts and tools for model management: A systems approach. Management Science, 40(9), 1093-1123, 1994.
2. R. Blanning, Model management systems: An overview. Decision Support Systems, 9(1), 9-18, 1993.
3. D. Grosh, R. Agarwal, Model selection and sequensing in decision support systems. OMEGA, 19(2-3), 157-167, 1991.
References:
1. D.M. Cohen, S.R. Dalal, J. Parelius, G.C. Patton, The combinatorial design approach to automatic test generation. IEEE Software, 13(5), 83-88, 1996
2. D.M. Cohen, S.R. Dalal, M.L. Fredman, G.C. Patton, The AETG system: An approach to testing based on combinatorial design. IEEE Trans. on Software Engineering, 23(7), 437-444, 1997.
3. Y. Lei, R. Kacker, D.R. Kuhn, V. Okun, J. Lawrence, IPOG/IPOG-D efficient test generation of multi-way combinatorial testing. Softw. Test., Verif. Reliab., 18(3), 125-148, 2008.
4. R. Kuhn, R. Kasker, Y. Lei, J. Hunter, Combinatorial software testing, IEEE Computer, 42(8), 94-96, 2009.
5. M.Sh. Levin, M. Last, Design of test inputs and their sequences in multi-funciton system testing. Applied Intelligence, 25(1), 105-124, 2006.
6. L. Shi, B. Xu, C. Nie, Combinatorial design approach for automatic test generation. J. of Electronics (China), 22(2), 205-208, 2005.
References:
1. E. Thompsen, OLAP Solutions: Building Multidimensional Information Systems. 2nd ed., New York, Wiley, 2002.
2. R. Wrembel, C. Koncila, Data Warehouses and OLAP: Concepts, Architectures and Solutions. IGI Global, Hershey, PA, 2006.
References:
1. H. Zarrabi-Zadeh, An almost space-optimal streaming algorithm for coresets in fixed dimensions. Algorithmica, 60(5), 46-59, 2011.
2. D. Feldman, M. Langberg, A unified framework for approximating and clustering data. Proc. of 43th Annual ACM Symp. on Theory of Computing STOC 2011, 2011.
3. D. Feldman, A. Fiat, M. Sharir, Coresets for weighted facilities and their applications. Proc. of 47th Symp. on Foundations of Computer Science FOCS 2006, 2006.
4. S. Har-Peled, S. Mazumdar, On coresets for k-mean and k-median clujstering. Proc. of 36th Annual ACM Symp. on Theory of Computing STOC 2004, Chicago, 291-300, 2004.
5.M. Badoiu, K.L. Clarkson, Optimal core-sets for balls. Proc. of 14th ACM-SIAM Symp. Discrete Algorithms, 801-802, 2003.
6. G. Frahling, C. Sohler, Coresets in dynamic geometric data streams. Proc. of 37th Annual ACM Symp. on Theory of Computing STOC 2005, Baltimore, 2005.
7. P.K. Agrarwal, H. Yu, A space-optimal data-stream algorithm for ņoresets in the plane. Proc. of the 23rd Annual Symp. on Computational Geometry, South Korea, 2007.
References:
1. R. Agrawal, T. Imielinski, A. Swami, Mining association rules between sets of items in large databases. Proc. of the ACM SIGMID Conf. on Management of Data, Washington, DC, 207-216, 1993.
2. R. Aghrawal, J.C. Shafer, Parallel mining of association rules. IEEE Trans KDE, 8(6), 962-969, 1996.
3. D.W.-L. Cheung, V.T. Ng, A.W.-C. Fu, Y. Fu, Efficient mining of association rules in distributed databases. IEEE Trans. KDE, 8(6), 911-922, 1996.
4. K. Kopetski, J. Han, Discovery of spatial association rules in geographic informaiton systems. LNCS 951, Springer, 47-66, 1995.
5. B. Liu, W. Hsu, Y. Ma, Integrating classification and association rule mining. American Association of Artificial Intelligence, KDD1998, 80-86, 1998.
6. T. Srikant, R. Agrawal, Mining generalized association rules. Proc. of the 21st Int. Conf. on Very Large Databases, Zurich, 407-419, 1995.
7. S. Tsur, J.D. Ullman, S. Abiteboul, C. Clifton, R. Motwani, S. Nestorov, A. Rosenthal, Query Flocks: A generalization of association-rule mining. Proc. SIGMOD Conf. 1998, 1-12, 1998.
8. R. Srikant, R. Agrawal, Mining generalized association rules. Future Generation Computer Systems, 13(2-3), 161-180, 1997.
9. A.E. Fiferman, V.G. Timkovsky, Basket problems in margin calculation: Modelling and algorithms. EJOR, 129(1), 209-223, 2001.
10. A. Evfimievski, R. Srikant, R. Agrawal, J. Gehrke, Privacy preserving mining of association rules. Information Systems, 29(4), 343-364, 2004.
References:
1. X. Liu, T. Murata, Detecting communities in k-partite k-uniform (hyper)networks. J. of Computer Science and Technology 26(5), 778--791, 2011.
2. T. Murata, Detecting communities from tripartite networks. In: World Wide Web Conf. (WWW'2010), 1159--1160, 2010.
3. T. Murata, Modularity for heterogeneous networks. In: Proc. of the 21th ACM Conf. on Hypertext and Hypermedia (HyperText2010), 129--134, 2010.