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:
-
1. Problem of representatives (Mathematics, about since 1930)
References:
1. M. Hall, Combinatorial Theory, 2nd ed., New York, Wiley, 1986.
-
2. Morphological analysis (Engineering, since 1943)
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.
-
3. Problem of compatible representatives
(Mathematics & Computer Science)
References:
1. D. Knuth, A. Ratghunathan,
The problem of compatible representatives. SIAM J. on Discrete Mathematics, 5(3), 422-427, 1992.
-
4. Design Structure Matrix
(Engineering)
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.
-
5. Morphological tables
(Management)
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.
-
6. Clustering in multipartite graph
(Computer Science)
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.
-
7. Maximal clique in multipartite graph
(Computer Science)
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.
-
8. Transversal studies
(Mathematics)
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.
-
9. Method Engineering
(Information Engineering)
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.
-
10. Model Management
(Model Engineering, Management, Information Engineering)
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.
-
11. Combinatorial System Testing
(Systems Engineering, Software Engineering, Networking)
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.
-
12. OLAP systems
(Information Engineering)
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.
-
13. Coresets problems
(Mathematics, Computer Science)
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.
-
14. Mining of association rules
(Computer Science, Artificial Intelligence, Information Systems, Management, Economics)
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.
-
15. Modularity (network communities) in k-partite networks
(Computer Science, Clustering, Social networks, etc.)
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.