COURSE:
COMBINATORIAL OPTIMIZATION MODELS AND SYSTEM CONFIGURATIONS

(preliminary version: June 2012)

Dr. Mark Sh. Levin ( Inst. for Information Transmission Problems, Russian Acad. of Sci. ).
http://www.mslevin.iitp.ru/
email: mslevin@acm.org

Dept. 'Technologies of Complex Systems Modeling',
School of Applied Mathematics and Information Science,
Faculty of Business Informatics,
National Research University 'Higher School of Economics'

Lecture 1.
Combinatorial optimizaiton models. Knapsack problem. Algorithmic complexity. Types of algorithms.

Lecture 2.
Multicriteria decision making. Multicriteria ranking / sorting problem.

Lecture 3.
Multiple choice problem.

Lecture 4.
System configuration design: (1) selection of system components, (2) selection of system components with taking into account compatibility of the selected components, (3) building of hierarchical structures (representative problem, path in multi-partite graph, clique, etc.).

Lecture 5.
Clustering. Assignment problem (location/allocation problems).

Lecture 6.
Clique, clique in multipartite graph. Combinatorial synthesis of system configuration.

Lecture 7.
Composite combinatorial schemes for system configuration. Connection of users and access points in communication systems.

Lecture 8.
Graph coloring problems.

Lecture 9.
Building of hierarchies (including hotlink assignment problem).

Lecture 10.
Aggregation of hierarchical structures/configurations.

Lecture 11.
Combinatorial synthesis with interval multiset estimates.

Lecture 12.
Restructuring in combinatorial optimization problems (reoptimizaiton).

Lecture 13.
System reconfiguration. Examples of applied systems.

Lecture 14.
Satisfiability problem (SAT problem).

Lecture 15.
Composite problems: timetabling problems (scheduling in universities, sport, hospitals).

Lecture 16.
Discussion of student works.

In the course, models for system configuration are studied.
For each combinatorial model / family of combninatorial models, the following is examined:
(1) simplified versions of the model(s) (polynomial solvable),
(2) complex models (NP-hard),
(3) approximation schemes / heuristics,
(4) examples for configuration of real-world systems.
The course is targeted to the following:
(1) knowledge transfer to student (traditional educational approach),
(2) joint generation of knowledge (advanced educational approach).

Course student work
(report as a preliminary material for publication and conference presentation):
  • Version 1 (application-based): selection of a model from the course and preparation of an applied system configuration example
    (e.g., configuration for hierarchical network for group of bank users).
  • Version 2 (model-based): selection of a model from the course and design of model modification (including an applied example).
  • Version 3 (algorithm-based): selection of a model from the course and design of algorithm (algorithm scheme) modification for the model (including computational experiment).

    Some prepared programs (in MATLAB) can be used:
    (a) selection of Pareto-efficient points,
    (b) outrankling technique (Electre),
    (c) greedy algorithm for knapsack problem,
    (d) greedy algorithm for multiple choice problem,
    (e) agglomerative algorithm for hierarchical clustering.


    BIBLIOGRAPHY FOR COURSE:

    For lecture 1:
    1. Garey M.R., Johnson D.S., Computers and Intractability. The Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco, 1979.

    For lecture 2:
    1. Simon H.A., Newell A., Heuristic problem solving: the next advance in operations research. Operations Research, 6(1), 1-10, 1958.
    2. Zoponidis N., Doumpos M., Multicriteria classification and sorting mehtods: A literature review. EJOR, 138(2), 229-246, 2002.
    3. Levin M.Sh., Composite strategy for multicriteria ranking/sorting (methodological issues, examples). Electronic preprint. 24 pp., Nov. 9, 2012.
    http://arxiv.org/abs/1211.2245 [math.OC]

    For lecture 3:
    1. Garey M.R., Johnson D.S., Computers and Intractability. The Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco, 1979.
    2. Kelleler H., Pferschy U., Pisinger D., Knapsack Problems, Springer, 2004.
    3. Martello S., Toth P., Knapsack Problems: Algorithms and Computer Implementation. Wiley, 1990.
    (accessible via Internet)

    For lecture 4:
    1. Levin M.Sh., Combinatorial optimization in system configuration design.
    Autom. and Remote Control, 70(3), 519-561, 2009.
    Version in Rusian:
    Levin M.Sh., Combinatorial optimization in system configuration design.
    "Information Processes", 8(4), 256-300 , 2008.

    For lecture 5:
    1. Jain A.K., Murty M.N., Flynn P.J., Data clustering: a review. ACM Comput. Surv., 31(3), 264-323, 1992.
    2. Mirkin B., Muchnik I., Combinatorial optimization in clustering. In: D.-Z. Du, P. Pardalos, (Eds.), Kluwer, 261-329, 1998.
    3. Levin M.Sh., Towards hierarchical clustering,
    In: V. Diekert, M. Volkov, A. Voronkov, (Eds.), CSR 2007, LNCS 4649, Springer,
    205-215, 2007.
    4. Garey M.R., Johnson D.S., Computers and Intractability. The Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco, 1979.

    For lecture 6:
    1. Levin M.Sh., Composite Systems Decisions. Springer, 2006.
    2. Levin M.Sh., 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. Levin M.Sh., Towards configuration of applied Web-based information system.
    Electronic preprint. 13 pp., Aug. 31, 2011.
    http://arxiv.org/abs/1108.6223 [cs.SE]
    4. Levin M.Sh., Towards electronic shopping of composite product. Electronic preprint. 10 pp., March 3, 2012.
    http://arxiv.org/abs/1203.0648 [cs.SE]

    For lecture 7:
    1. Levin M.Sh., Four-layer framework for combinatorial optimization problems domain.
    Advances in Engineering Software, 42(12), 1089-1098, 2011.
    (journal site)
    2. Levin M.Sh., Combinatorial scheme for design of marketing strategy.
    Business Informatics, Issue 2, 42-51, 2009 (in Russian). (journal issue site)
    3. Levin M.Sh., Selection of user's connection in last mile problem.
    IEEE Trans. SMC - Part A, 41(2), 370-374, 2011.

    For lecture 8:
    1. Pachos V.Th., Polynomial approximation and graph coloring. Computing, 70(1), 41-86, 2003.
    2. Johnson D.S., Trick M.A. (Eds.), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challendge, Providence, RI, AMS, 1996.
    3. Garey M.R., Johnson D.S., Computers and Intractability. The Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco, 1979.

    For lecture 9:
    1. Levin M.Sh., Towards hierarchical clustering,
    In: V. Diekert, M. Volkov, A. Voronkov, (Eds.), CSR 2007, LNCS 4649, Springer,
    205-215, 2007.
    2. Levin M.Sh., Kudinov O.P., On structural approach to political management.
    "Information Processes", 11(4), 466-475, 2011 (in Russian).
    3. Levin M.Sh., Towards design of hierarchy (research survey). Electronic preprint. 36 pp., Dec. 8, 2012.
    http://arxiv.org/abs/1212.1735 [math.OC]
    4. Bose P., Kranakis E., Kriznc D., Martin M., Czyzowicz M.V., Pelc A., Gasieniec L., Strategies for hotlink assignment. LNCS 1969, Springer, 23-34, 2000.
    5. Fuhrmann S., Krumke S., Multiple hotlink assignment. LNCS 2204, Springer, 189-200, 2001.

    For lecture 10:
    1. Levin M.Sh., Aggregation of composite solutions: strategies, models, examples.
    Electronic preprint. 72 pp., Nov. 29, 2011.
    http://arxiv.org/abs/1111.6983 [cs.SE]

    For lecture 11:
    1. M.Sh. Levin, Multiset estimates and combinatorial synthesis. Electronic preprint. 30 pp., May 9, 2012.
    http://arxiv.org/abs/1205.2046 [cs.SY]
    2. M.Sh. Levin, Modular design and improvement of management in smart homes with interval multiset estimates.
    Electronic Scientific Journal "Information Processes", 12(2), 141-154, 2012 (in Russian)
    3. M.Sh. Levin, Composition of modular telemetry system with interval multiset estimates. Electronic preprint. 9 pp., July 25, 2012.
    http://arxiv.org/abs/1207.6051 [cs.SY]

    For lecture 12:
    1. Levin M.Sh., Restructuring in combinatorial optimization. Electronic preprint. 11 pp., Febr. 8, 2011.
    http://arxiv.org/abs/1102.1745 [cs.DS]
    2. Bockenhauer H.-J., Hromkovic J., Momke T., Widmayer P., On the hardness of reoptimization. LNCS 4910, Springer, 50-65, 2008.

    For lecture 13:
    1. Levin M.Sh., Towards communication network development (structural systems issues, combinatorial problems).
    IEEE Region 8 Int. Conf. Sibircon 2010, vol. 1, 204-208, 2010.
    2. Levin M.Sh., Andrushevich A., Klapproth A., Improvement of building automation system.
    In: K.G. Mehrotra et al. (Eds.), Proc. of 24th Int. Conf. IEA/AIE 2011, LNCS 6704, Part II, Springer, 459-468, 2011.

    For lecture 14:
    1. Garey M.R., Johnson D.S., Computers and Intractability. The Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco, 1979.
    2. Johnson D.S., Trick M.A. (Eds.), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challendge, Providence, RI, AMS, 1996.

    For lecture 15:
    1. de Werra D., An introduction to timetabling. EJOR, 19(2), 151-162, 1985.
    2. Nemhauser G.I., Trick M.A., Scheduling a major college basketball conference. Operations Research, 46(1), 1-8, 1998.
    3. Schaerf A., A survey of automated timetabling. Artif. Intell. Review, 13(2), 87-127, 1999.


    STUDENT ARTICLES (based on course in Moscow Inst. of Physics and Technology - State Univ.):

    For lecture 3:
    1. Levin M.Sh., Safonov A.V., Design and redesign for equipment configuration in communication network.
    "Information technologies and computer systems", issue 4, 63-73, 2006 (in Russian).
    (journal site)
    (pdf.file)
    2. Levin M.Sh., Safonov A.V., Improvement of regional telecommunications networks.
    J. of Communications Technology and Electronics, 56(6), 770-778, 2011.
    (journal site)
    Version in Russian:
    Levin M.Sh., Safonov A.V., Towards improvement of regional telecommunication network.
    "Information Processes", 10(3),212-223, 2010 (in Russian).
    3. Levin M.Sh., Safonov A.V., Towards modular redesign of networked system.
    2nd Int. Congress on Ultra Modern Telecommunications and Control Systems and Workshops
    ICUMT-2010, Moscow, 109-114, 2010.

    For lecture 5:
    1. Levin M.Sh., Petukhov M.V., Connection of users with a telecommunications network: multicriteria assignment problem.
    J. of Communications Technology and Electronics, 55(12), 1532-1541, 2010.
    (journal site)
    Version in Russian::
    Levin M.Sh., Petukhov M.V., Connection of users and access points in telecommunication network
    (multicriteria assignment problem). "Information Processes", 9(4), 332-342, 2009 (in Russian).
    2. Levin M.Sh., Petukhov M.V., Multicriteria assignment problem(selection of access points).
    Proc. of 23rd Int. Conf. IEA/AIE 2010, "Trends in Applied Intelligent Systems",
    LNCS 6097, part II, Springer, pp. 277-287, 2010.

    For lecture 6:
    1. Levin M.Sh., Khodakovskii I.A., Structural composition of the telemetry system.
    Automation and Remote Control, 68(9), 1654-1661, 2007.
    Abstract in MAIK
    Version in Russian:
    Levin M.Sh., Khodakovsky I.A., Composition of structure for telemetry system.
    "Information Processes", 7(2), 191-198, 2007 (in Russian).
    2. Levin M.Sh., Vishnitskiy R.O., Towards morphological design of GSM network.
    "Information Processes" 7(2), 183-190, 2007
    3. Levin M.Sh., Sharov S.Yu., Hierarchical morphological design of Web-hosting system.
    Int. Journal of Integrated Design & Process Science, 13(1), 1-14, 2009.
    (journal issue site)
    4. Levin M.Sh., Leus A.V., Configuration of integrated security system.
    7th IEEE Int. Conf. on Industrial Informatics INDIN 2009, Cardiff, UK, pp. 101-105, 2009.
    5. Levin M.Sh., Fimin A.V., Design of modular wireless sensor. Electronic preprint. 7 pp., March 9, 2012.
    http://arxiv.org/abs/1203.2031 [cs.SE]

    For lecture 7:
    1. Levin M.Sh., Fimin A.V., Combinatorial scheme for analysis of political candidates and their strategies.
    "Information Processes", 9(2), 83-92, 2009 (in Russian).
    2. Levin M.Sh., A.O. Merzlyakov,
    Composite combinatorial scheme of test planning (example for microprocessor systems)
    IEEE Region 8 Int. Conf. "Sibircon-2008", Novosibirsk, 291-295, 2008.

    For lecture 9:
    1. Levin M.Sh., Nuriakhmetov R.I., Multicriteria Steiner tree problem for communication network.
    Electronic preprint. http://arxiv.org/abs/1102.2524 [cs.DS], 11 pp., Febr. 12, 2011
    2. Levin M.Sh., Zamkovoy A.A., Multicriteria Steiner tree with the cost of Steiner vertices.
    J. of Communications Technology and Electronics,
    56(12), 1527-1542, 2011.
    (journal site)
    Version in Russian:
    Levin M.Sh., Zamkovoy A.A., Multicriteria Steiner tree with cost of Steiner vertices.
    "Information Processes", 11(1), 140-160, 2011 (in Russian).