• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Магистратура 2020/2021

Прикладная количественная логистика

Статус: Курс по выбору (Науки о данных)
Направление: 01.04.02. Прикладная математика и информатика
Когда читается: 1-й курс, 3, 4 модуль
Формат изучения: без онлайн-курса
Прогр. обучения: Науки о данных
Язык: английский
Кредиты: 4
Контактные часы: 60

Course Syllabus

Abstract

Basic quantitative logistics models and algorithms for Allocation, Transportation, and Vehicle Routing Problems including the sensitivity and stability analysis applied to the Minimum Spanning Tree Problem (MSTP) and its variations, Shortest Path, Traveling Salesman and Vehicle Routing Problems (Capacitated, Time Windows, Pick Up and Delivery, etc.), Preempted Single Machine Scheduling Jobs (Operations) with Arbitrary Processing Times, Release and Due Dates will be studied in this course.
Learning Objectives

Learning Objectives

  • Students who complete this course successfully will learn or acquire: <ul><li>Basic concepts of computational complexities for problems and algorithms (both exact and heuristic), which are necessary for further learning supply chain management models and algorithms, computational methods, algorithms for big data, algorithms and computational complexity, machine learning, operations research, game theory, and combinatorial optimization.</li> <li>Skills in design, implementation, and analysis of mathematical models and algorithms for solving applied quantitative logistics problems.</li> <li>Individual presentation of research activities following a pre-defined pattern including the corresponding research report.</li> <li>High quality reports will be recommended for publication in top international scientific journals in Optimization, Operations Research, Computer Science, Algorithms, Mathematical Modeling, etc. (Q2 or Q1, see scimago for details) among them Journal of Global Optimization, Journal of Combinatorial Optimization, Computers and Operations Research just to mention a few.</li></ul>
Expected Learning Outcomes

Expected Learning Outcomes

  • Able to find mathematical structures defined on graphs and transportation networks related to location, sequencing and scheduling problems.
  • Learn basic notions of models and algorithms to solve computationally intractable problems in quantitative logistics, scheduling algorithmsand computer science.
  • Basic skills to design and implement exact and heuristic (approximation) algorithms in quantitative logistics.
Course Contents

Course Contents

  • The Minimum Spanning Tree (Kruskal and Prim’s Algorithms), 1-Tree, and Linear Assignment Problems - LAPs including problems based on patterns in LAP (Hungarian Algorithm).
  • The Preempted Single Machine Scheduling Problems with different objective functions: Total Weighted Completion Time, Total Weighted Tardiness, Maximum Lateness, Makespan, Weighted Number of Tardy Jobs, Total Weighted Earliness, Total Weighted Earliness and Tardiness, Total Weighted Non-Linear Function depending on the key arguments (completion time, tardiness, earliness and tardiness, etc.
  • The Traveling Salesman Problem (TSP): Symmetric and Asymmetric Cases of TSP.
  • The Branch and Bound Algorithms for the Symmetric TSP (STSP).
  • The Branch and Bound Algorithms for the Asymmetric TSP (ATSP).
  • Upper, Lower, and Bottleneck Tolerances in Applied Quantitative Logistics.
  • Upper Tolerances Based Algorithm for the ATSP.
  • Lower Tolerances Based Algorithm for the ATSP.
  • Data Correcting Approach for Real-Valued Functions.
  • Data Correcting Approach for ATSP.
  • Heuristics for solving the TSP: greedy (nearest neighbor), tolerance based greedy, nearest insertion, 2, 3-opt.
  • Introduction to Submodular Functions: Local, Global Maxima on Hasse Diagram and Their Components.
  • Supermodular Functions Applied to the Simple Plant (Uncapacitated Facility) Location Problem (SPLP).
  • Cherenin-Khachaturov’s Theorem. Excluding vs Preservation Rules. Dichotomy (Preliminary Preservation) Algorithm.
  • Branch-and-Bound (BnB) Algorihm for Supermodular Function Minimization Problem and Its Applications to the SPLP.
  • Non-binary branching rules applied to the pseudo-Boolean formulation of the SPLP. The branching rule: Make Quadratic Terms Linear.
  • The Quadratic Cost Partition Problem (QCP) - an example for maximization of a submodular set function.
  • Cherenin’s Theorem (quasi-concavity of submodular functions).
  • The greedy algorithm for submodular set functions.
  • Pseudo-Boolean polynomials for the Simple Plant Location (SPLP).
  • Truncation Theorem for the p-Median problem.
  • Exact and Heuristic Algorithms for the SPLP.
Assessment Elements

Assessment Elements

  • non-blocking Homework and Assignments
  • non-blocking In-class test
    Midterm tеst will be announced at least one week in advance.
  • non-blocking Personal presentation of team reports
  • non-blocking Final exam (comprehensive)
    Экзамен проводится на платформе Skype (https://www.skype.com/). К экзамену необходимо подключиться согласно расписанию ответов, высланному преподавателем на корпоративные почты студентов накануне экзамена. Компьютер студента должен удовлетворять требованиям: наличие рабочей камеры и микрофона, поддержка Skype. Для участия в экзамене студент обязан: поставить на аватар свою фотографию, явиться на экзамен согласно точному расписанию, при ответе включить камеру и микрофон. Во время экзамена студентам запрещено: выключать камеру, пользоваться конспектами и подсказками. Кратковременным нарушением связи во время экзамена считается нарушение связи менее минуты. Долговременным нарушением связи во время экзамена считается нарушение минута и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи подразумевает использование усложненных заданий.
Interim Assessment

Interim Assessment

  • Interim assessment (4 module)
    0.4 * Final exam (comprehensive) + 0.3 * Homework and Assignments + 0.2 * In-class test + 0.1 * Personal presentation of team reports
Bibliography

Bibliography

Recommended Core Bibliography

  • Goldengorin, B., & Pardalos, P. M. (2012). Data Correcting Approaches in Combinatorial Optimization. New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=538347
  • Goldengorin, B., Pardalos, P. M., & Krushinsky, D. (2013). Cell Formation in Industrial Engineering : Theory, Algorithms and Experiments. Springer.

Recommended Additional Bibliography

  • Gerard Sierksma, & Diptesh Ghosh. (2010). Networks in Action. Springer.