КУРС:
МОДЕЛИ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ И КОНФИГУРАЦИИ СИСТЕМ

(предварительная версия: июнь 2012)

К.т.н. Марк Шмуилович Левин (ИППИ РАН).
http://www.mslevin.iitp.ru/
email: mslevin@acm.org

Кафедра технологии моделирования сложных систем,
Отделение "Прикладная математика и информатика"
Факультет "Бизнес информатика",
НИУ "Высшая школа экономики"

Лекция 1.
Модели комбинаторное оптимизации. Задача о рюкзаке. Алгоритмическая сложность. Типы алгоритмов.

Лекция 2.
Многокритериальное принятие решений. Ранжирование альтернатив (multicriteria ranking / sorting problem).

Лекция 3.
Задача блочного рюкзака (multiple choice problem).

Лекция 4.
Задача построения конфигурации систем: (1) выбор компонентов системы, (2) выбор компонентов системы с учетом их совместимости, (3) построение иерархических структур (задача о представителях, путь в многодольном графе, клика и др.).

Лекция 5.
Задача кластеризации. Задача о назначениях (о размещении).

Лекция 6.
Клика, клика в многодольном графе. Комбинаторное проектирование конфигураций систем.

Лекция 7.
Составные комбинаторные схемы построения конфигураций систем. Подключение пользователей к точкам доступа.

Лекция 8.
Задачи раскраски графа.

Лекция 9.
Построение иерархий (включая задачу добавления связей в иерархиях - hotlink assignment problem).

Лекция 10.
Агрегирование иерархических структур/конфигураций.

Лекция 11.
Комбинаторный синтез с интервальными оценками в виде мультимножеств.

Лекция 12.
Реструктуризация в задачах комбинаторной оптимизации (reoptimization).

Лекция 13.
О реконфигурации систем. Примеры прикладных систем.

Лекция 14.
Задача о выполнимости (SAT problem).

Лекция 15.
Составные задачи: расписания в университетах, спорте, госпиталях (timetabling problems).

Лекция 16.
Обсуждение курсовых работ, итогов курса.

В рамках данного курса рассматриваются модели для конфигураций систем.
По каждой комбинаторной модели/семейству моделей:
(1) простейшие варианты модели (полиномиально разрешимые),
(2) сложные модели (NP-трудные),
(3) приближенные схемы решения / эвристики,
(4) примеры применения для конфигурации прикладных систем.
Данный курс направлен на реализацию следующего:
(1) передача студентам знаний (традиционный подход в преподавании),
(2) совместное создание (генерация) знаний (перспективный подход в преподавании).

Самостоятельная работа по курсу
(оформляется как отчет / курсовая работа и материалы для публикации и выступления на конференции):
  • Вариант 1: выбор модели из курса и построение примера конфигурации прикладной системы с расчетами
    (например: конфигурация иерархической сети для группы пользователей банка)
  • Вариант 2: выбор модели из курса и построение модификации модели (включая прикладной пример)
  • Вариант 3: выбор модели из курса и разработка модификации алгоритма для модели (включая вычислительный эксперимент)

    Можно использовать готовые программные блоки (в среде MATLAB):
    (а) выделение множества Парето,
    (б) метод порогов несравнимости (Electre),
    (в) "жадный" алгоритм для задачи о рюкзаке,
    (г) "жадный" алгоритм для задачи блочного рюкзака,
    (д) агломеративный алгоритм для иерархической кластеризации.


    ЛИТЕРАТУРА ПО КУРСУ:

    К лекции 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.

    К лекции 2:
    1. Simon H.A., Newell A., Heuristic problem solving: the next advance in operations research. Operations Research, 6(1), 1-10, 1958.
    2. Левин М.Ш., Михайлов А.А., Фрагменты технологии стратификации множества объектов. Препринт, ИСА РАН, Москва, 60 С., 1988.
    3.Белкин А.Р., Левин М.Ш., Принятие решений: Комбинаторные модели аппроксимации информации. Наука, Физматлит, Москва, 1990.
    Book (pdf-file)
    4. Zoponidis N., Doumpos M., Multicriteria classification and sorting mehtods: A literature review. EJOR, 138(2), 229-246, 2002.
    5. 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]


    К лекции 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)

    К лекции 4:
    1. Levin M.Sh., Combinatorial optimization in system configuration design.
    Autom. and Remote Control, 70(3), 519-561, 2009.

    Версия на русском:
    Левин М.Ш., Комбинаторная оптимизация при проектировании конфигураций систем.
    "Информационные процессы", 8(4), 256-300 , 2008.


    К лекции 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., Combinagtorial 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.

    К лекции 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]


    К лекции 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. Левин М.Ш., Комбинированная схема построения маркетинговой стратегии.
    Бизнес информатика, вып. 2, 42-51, 2009. (сайт выпуска 4 журнала)
    3. Levin M.Sh., Selection of user's connection in last mile problem.
    IEEE Trans. SMC - Part A, 41(2), 370-374, 2011.


    К лекции 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.

    К лекции 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. Левин М.Ш., Кудинов О.П., О структурном подходе к политическому управлению.
    "Информационные процессы", 11(4), 466-475, 2011.

    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. Воронин А.А., Мишин С.П., Оптимальные иерархические структуры. Москва, ИПУ РАН, 2003.
    5. Губко М.Б., Поиск оптимальных организационных иерархий при однородных функциях затрат менеджеров. Автоматика и телемеханика, 1, 97-113, 2008.
    6. 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.
    7. Fuhrmann S., Krumke S., Multiple hotlink assignment. LNCS 2204, Springer, 189-200, 2001.

    К лекции 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]


    К лекции 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. Левин М.Ш., Модульное проектирование и улучшение системы управления в умном доме с использованием интервальных оценок в виде мультимножеств.
    "Информационные процессы", 12(2), 141-154, 2012.
    (pdf.file)
    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]


    К лекции 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.

    К лекции 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.


    К лекции 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.

    К лекции 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.


    СТУДЕНЧЕСКИЕ ПУБЛИКАЦИИ (на базе курса в МФТИ):

    К лекции 3:
    1. Левин М.Ш., Сафонов А.В., Проектирование и перепроектирование конфигурации оборудования коммуникационной сети. "Информационные технологии и вычислительные системы", вып. 4, 63-73, 2006.
    (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)
    Версия на русском:
    Левин М.Ш., Сафонов А.В., Об улучшении региональной телекоммуникационной сети.
    "Информационные процессы", 10(3),212-223, 2010.

    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.


    К лекции 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)
    Версия на русском:
    Левин М.Ш., Петухов М.В., Подключение пользователей к точкам дуступа телекоммуникационной сети
    (многокритериальная задача о назначении). "Информационные процессы", 9(4), 332-342, 2009.

    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.


    К лекции 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
    Версия на русском:
    Левин М.Ш., Ходаковский И.А., Композиция структуры телеметрической системы.
    "Информационные процессы", 7(2), 191-198, 2007.

    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.

    6. 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]


    К лекции 7:
    1. Левин М.Ш., Фимин А.В., Комбинаторная схема для анализа политических кандидатов и их стратегий.
    "Информационные процессы", 9(2), 83-92, 2009.

    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.


    К лекции 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)
    Версия на русском:
    Левин М.Ш., Замковой А.А., Многокритериальное дерево Штейнера с учетом стоимости вершин Штейнера.
    "Информационные процессы", 11(1), 140-160, 2011.