Multicriteria combinatorial models in information-communication systems”

Mark Sh. Levin (Inst. for Information Transmission Problems; Febr. 17, 2011)    Email:  


Information-communication systems have modular nature (structure as network/graph, modular structure of network nodes, information servers, software, etc.).

Here the usage of combinatorial optimization problems has a long history (e.g., location of concentrators in network, routing, selection/assignment of frequencies/channels).

In recent several years, some publications are targeted to study of multicriteria combinatorial models in design and management of information-communication systems.

Generally, multicriteria method is a new approach (only the shortest path problem is examined as a multicriteria model since about 1989). Multicriteria approach is often based on a need to take into account many parameters/requirements/criteria (e.g., cost, reliability, effectiveness). In addition, it is reasonable to point out some properties of contemporary systems, for example:

(1)concurrent usage of many alternative technologies,

(2)multi-services modes.

It is necessary to note, that mainly applied domain specialists are considering application of multicriteria combinatorial models in information-communication systems. As a result, used models and algorithms are selected from well-known text-books or survey articles, which correspond to 1995…2000 years.


Our research project is targeted to examination and building advanced multicriteria combinatorial models which correspond to contemporary and perspective information-communication systems, including the following:

1.Multicirtieria spanning tree problems (extension of minimal spanning tree, Steiner tree) and usage of the problems for system design (e.g., design of network topology, routing, communication protocols).

2.Multicriteria hierarchical modular design (i.e., system configuration) of system  components (communication nodes, servers, software, networked control systems, etc.).

3.Multicriteria combinatorial evolution of components in information–communication systems (including standards, protocols).

4.Multicriteria redesign/improvement problems (system reconfiguration) for subsystems/components of information-communication systems (e.g., networks, communication nodes, servers).

5.Special classes of new combinatorial optimization problems as restructuring of combinatorial solutions while taking into account previous solutions.


Each research will consist of the following parts: applied problems, multicriteria combinatorial model (new model or combination of models), solving method, and applied example as a prototype.



List of authors basic publications (since 2005):

I.Journal articles (Web of Science, IEEE, Scopus, etc.):

1.M.Sh. Levin, Connection of user’s in last-mile problem. IEEE Trans. SMC-Part A, 41(2), 370-374, 2011.

2.M.Sh. Levin, M. Petukhov, Connection of users with a telecommunications network: multicriteria assignment problem. J. of Com. Technol. and Electronics, 55(12), 1532-1542, 2010.

3.M.Sh. Levin, Combinatorial optimization in system configuration design. Aut. & Remote Control, 70(3), 519-561, 2009.

4. M.Sh. Levin, S.Yu. Sharov, Hierarchical morphological composition of Web-hosting system. J. of Integrated Design & Process Science. 13(1), 1-14, 2009.

5. M.Sh. Levin, O. Kruchkov, O. Hadar, E. Kaminsky, Combinatorial System Evolution: Example of Standard for Multimedia Information. Informatica (Lith.), 20(4), 519-538, 2009.

6. M.Sh. Levin, A.V. Safonov, Heuristic for multicriteria multiple choice knapsack problem. Artificial Intelligence and Decision Making, 4, 53-64, 2009 (in Russian).

7. M.Sh. Levin, I.A. Khodakovskii, Structural Composition of the Telemetry System. Automation and Remote Control, 68(9), 1654-1661, 2007.

8. M.Sh. Levin, A.V. Safonov, Design and redesign of facility configuration in communication network. Inform. Technol. & Comput. Syst.,  4, 63-73, 2006 (in Russian).

9. M.Sh. Levin, Modular System Synthesis: Example for Composite Packaged Software. IEEE Tran. SMC – Part C, 35(4), 544-553, 2005.

II.Papers in Int. collections (LNCS Springer, IEEE, Scopus):

10. M.Sh. Levin, A. Andrushevich, A. Klapproth, Improvement of building automation system. Proc. of Int. Conf. IEA/AIE 2011, (accepted)

11. M.Sh. Levin, M.V. Petukhov, Multicriteria assignment problem (selection of access points). LNCS 6097, part II, Springer, 277-287, 2010.

12.M.Sh. Levin, A.V. Fimin, Configuration of alarm wireless sensor element. Int. Conf. on Ultra Modern Telecommunication ICUMT 2010, 924-928, 2010.

13. M.Sh. Levin, A.V. Safonov, Towards modular redesign of networked system. Int. Conf. on Ultra Modern Telecommunication ICUMT 2010, 109-114, 2010.

14. M.Sh. Levin, Towards communication system development (structural system issues, combinatorial models). 2010 IEEE Region 8 Int. Conf. Sibircon-2010, vol. 1, 204-208, 2010.

15. M.Sh. Levin, A. Andrushevich, R. Kistler, A. Klapproth, Combinatorial evolution of ZigBee protocol. 2010 IEEE Region 8 Int. conf. Sibircon-2010, vol. 1, 314-319, 2010.

16.M.Sh. Levin M.Sh., Leus A.V., Configuration of integrated security system. IEEE 7th. Int. Conf. on Industrial Informatics INDIN 2009, Cardiff, UK, pp. 101-105, 2009.

17. M.Sh. Levin, Morphological approach to electronic shopping. 2008 IEEE Region 8 Int. conf. Sibircon-2008, Novosibirsk, Russia, 280-285, 2008.

18. M.Sh. Levin, Towards Hierarchical Clustering. LNCS 4649, Springer, 205-215, 2007.

III.Papers in electronic sources:

19.M.Sh. Levin, Restructuring in combinatorial optimization. Electronic preprint. [cs.DS], 11 pp., Febr. 12, 2011

20. M.Sh. Levin, A.V. Safonov, Towards improvement of regional telecommunication network. “Information Processes”, 10(3), 212-223, 2010 (in Russian).

21.M.Sh. Levin, A. Andrushevich, A. Klapproth, Modular composition of management system for smart homes. “Information Processes”, 10(1), 78-86, 2010.

22.M..Sh. Levin, R.I. Nuriakhmetov, Multicriteria  Steiner tree problem for communication network. “Information Processes”, 9(3), 199-209, 2009.

23.M.Sh. Levin, R.O. Vishnitskiy, Towards Morphological Design of GSM Network.  “Information Processes”, 7(2), 183-190, 2007.

24. M.Sh. Levin, A.A. Zamkovoy, Multicriteria Steiner tree with cost of Steiner vertices. “Information Processes”, 11(1), 140-160, 2011 (in Russian).

IV.Conference papers:

25. M.Sh. Levin, A.A. Zamkovoy, Multicriteria Steiner tree with cost of vertices.
Proc. of X Int. Conf. CAD/CAM/PDM-2010, Moscow, Inst. of Control Problems (Russian Acad. of Sci.), 52-57, 2010 (in Russian)

26. M.Sh. Levin, R.I. Nuriahmetov, Towards multicriteria Steiner tree for communication network. 3rd Int. Conf. on System Analysis and Information Technologies SAIT-2009, Inst. for System Analysis, Zvenigorod/Moscow, Russia, pp. 304-312, 2009 (in Russian)