4.8
звезд
Оценки: 616

Professor Pascal Van Hentenryck и еще 1 преподаватель

54 536 уже зарегистрированы

от партнера

Дискретная оптимизация

Мельбурнский университет

Об этом курсе

Недавно просмотрено: 48 957

Tired of solving Sudokus by hand? This class teaches you how to solve complex search problems with discrete optimization concepts and algorithms, including constraint programming, local search, and mixed-integer programming.
Optimization technology is ubiquitous in our society. It schedules planes and their crews, coordinates the production of steel, and organizes the transportation of iron ore from the mines to the ports. Optimization clears the day-ahead and real-time markets to deliver electricity to millions of people. It organizes kidney exchanges and cancer treatments and helps scientists understand the fundamental fabric of life, control complex chemical reactions, and design drugs that may benefit billions of individuals.

This class is an introduction to discrete optimization and exposes students to some of the most fundamental concepts and algorithms in the field. It covers constraint programming, local search, and mixed-integer programming from their foundations to their applications for complex practical problems in areas such as scheduling, vehicle routing, supply-chain optimization, and resource allocation.

Гибкие сроки

Назначьте сроки сдачи в соответствии со своим графиком.

Сертификат, ссылками на который можно делиться с другими людьми

Получите сертификат по завершении

100% онлайн

Начните сейчас и учитесь по собственному графику.

Средний уровень

Прибл. 65 часов на выполнение

Английский

Субтитры: Арабский, Французский, Португальский (Европа), Итальянский, Вьетнамский, Немецкий, Русский, Английский, Испанский

Приобретаемые навыки

Constraint ProgrammingBranch And BoundDiscrete OptimizationLinear Programming (LP)

Гибкие сроки

Назначьте сроки сдачи в соответствии со своим графиком.

Сертификат, ссылками на который можно делиться с другими людьми

Получите сертификат по завершении

100% онлайн

Начните сейчас и учитесь по собственному графику.

Средний уровень

Прибл. 65 часов на выполнение

Английский

Преподаватели

Оценка преподавателя

4,84/5 (оценок: 102)

Professor Pascal Van Hentenryck

54 536 учащихся

1 курс

Dr. Carleton Coffrin

Adjunct Lecturer

Computing and Information Systems

56 365 учащихся

2 курса

от партнера

Мельбурнский университет

The University of Melbourne is an internationally recognised research intensive University with a strong tradition of excellence in teaching, research, and community engagement. Established in 1853, it is Australia's second oldest University.

Программа курса: что вы изучите

Оценка контента96%(4,069 оценки)

Неделя

Неделя 1

2 ч. на завершение

Welcome

These lectures and readings give you an introduction to this course: its philosophy, organization, and load. They also tell you how the assignments are a significant part of the class. This week covers the common input/output organization of the assignments, how they are graded, and how to succeed in this class.

2 ч. на завершение

4 видео ((всего 43 мин.)), 2 материалов для самостоятельного изучения, 1 тест

Неделя

Неделя 2

7 ч. на завершение

Knapsack

These lectures introduce optimization problems and some optimization techniques through the knapsack problem, one of the most well-known problem in the field. It discusses how to formalize and model optimization problems using knapsack as an example. It then reviews how to apply dynamic programming and branch and bound to the knapsack problem, providing intuition behind these two fundamental optimization techniques. The concept of relaxation and search are also discussed.

7 ч. на завершение

9 видео ((всего 101 мин.))

9 видео

Knapsack 1 - intuition2мин

Knapsack 2 - greedy algorithms7мин

Knapsack 3 - modeling8мин

Knapsack 4 - dynamic programming17мин

Knapsack 5 - relaxation, branch and bound14мин

Knapsack 6 - search strategies, depth first, best first, least discrepancy14мин

Assignments Getting Started13мин

Knapsack & External Solver10мин

Exploring the Material - open course design, optimization landscape, picking your adventure10мин

Неделя

Неделя 3

17 ч. на завершение

Constraint Programming

Constraint programming is an optimization technique that emerged from the field of artificial intelligence. It is characterized by two key ideas: To express the optimization problem at a high level to reveal its structure and to use constraints to reduce the search space by removing, from the variable domains, values that cannot appear in solutions. These lectures cover constraint programming in detail, describing the language of constraint programming, its underlying computational paradigm and how it can be applied in practice.

17 ч. на завершение

13 видео ((всего 248 мин.)), 1 материал для самостоятельного изучения, 2 тестов

13 видео

CP 1 - intuition, computational paradigm, map coloring, n-queens27мин

CP 2 - propagation, arithmetic constraints, send+more=money26мин

CP 3 - reification, element constraint, magic series, stable marriage16мин

CP 4 - global constraint intuition, table constraint, sudoku19мин

CP 5 - symmetry breaking, BIBD, scene allocation18мин

CP 6 - redundant constraints, magic series, market split11мин

CP 7 - car sequencing, dual modeling18мин

CP 8 - global constraints in detail, knapsack, alldifferent33мин

CP 9 - search, first-fail, euler knight, ESDD25мин

CP 10 - value/variable labeling, domain splitting, symmetry breaking in search28мин

Graph Coloring6мин

Optimization Tools5мин

Set Cover8мин

1 материал для самостоятельного изучения

Optimization Tools10мин

Неделя

Неделя 4

13 ч. на завершение

Local Search

Local search is probably the oldest and most intuitive optimization technique. It consists in starting from a solution and improving it by performing (typically) local perturbations (often called moves). Local search has evolved substantially in the last decades with a lot of attention being devoted on which moves to explore. These lectures explore the theory and practice of local search, from the concept of neighborhood and connectivity to meta-heuristics such as tabu search and simulated annealing.

13 ч. на завершение

10 видео ((всего 191 мин.))

10 видео

LS 1 - intuition, n-queens13мин

LS 2 - swap neighborhood, car sequencing, magic square15мин

LS 3 - optimization, warehouse location, traveling salesman, 2-opt, k-opt23мин

LS 4 - optimality vs feasibility, graph coloring22мин

LS 5 - complex neighborhoods, sports scheduling21мин

LS 6 - escaping local minima, connectivity15мин

LS 7 - formalization, heuristics, meta-heuristics introduction22мин

LS 8 - iterated location search, metropolis heuristic, simulated annealing, tabu search intuition18мин

LS 9 - tabu search formalized, aspiration, car sequencing, n-queens26мин

Traveling Salesman10мин

Неделя

Неделя 5

2 ч. на завершение

Linear Programming

Linear programming has been, and remains, a workhorse of optimization. It consists in optimizing a linear objective subject to linear constraints, admits efficient algorithmic solutions, and is often an important building block for other optimization techniques. These lectures review fundamental concepts in linear programming, including the infamous simplex algorithm, simplex tableau, and duality. .

2 ч. на завершение

6 видео ((всего 130 мин.))

Неделя

Неделя 6

12 ч. на завершение

Mixed Integer Programming

Mixed Integer Programming generalizes linear programming by allowing integer variables, which dramatically changes the complexity of the problems but also broadens the potential applications significantly. These lectures review how to model problems in mixed-integer programming and how to solve mixed-integer programs using branch and bound. Advanced techniques such as cutting planes and polyhedral cuts are also covered.

12 ч. на завершение

6 видео ((всего 136 мин.))

6 видео

MIP 1 - intuition, relaxation, branch and bound, knapsack, warehouse location26мин

MIP 2 - modeling, big-M, warehouse location, graph coloring28мин

MIP 3 - cutting planes, Gomory cuts20мин

MIP 4 - convex hull, polyhedral cuts, warehouse location, node packing, graph coloring19мин

MIP 5 - cover cuts, branch and cut, seven bridges, traveling salesman31мин

Facility Location9мин

Неделя

Неделя 7

11 ч. на завершение

Advanced Topics: Part I

These lectures cover some more advanced concepts in optimization. They introduce constraint-programming techniques for scheduling and routing.

11 ч. на завершение

2 видео ((всего 51 мин.))

Неделя

Неделя 8

1 ч. на завершение

Advanced Topics: Part II

These lectures continues to cover some more advanced concepts in optimization. They introduce large neighborhood search, which often combines constraint programming and local search, and column generation which decomposes an optimization model into a master and pricing problem, using more complex variables.

1 ч. на завершение

2 видео ((всего 32 мин.)), 1 материал для самостоятельного изучения

Рецензии

4.8

Рецензии: 142

5 stars
89,17 %
4 stars
8,07 %
3 stars
1,13 %
2 stars
0,16 %
1 star
1,45 %

Лучшие отзывы о курсе ДИСКРЕТНАЯ ОПТИМИЗАЦИЯ

от партнера SK29 мая 2019 г.

Exceptional coverage of optimization fundamentals. Learning of practical applied methods. Real university level course, no water down "data science". Absolutely love it! Thank you professor Pascal.

от партнера JB21 июля 2017 г.

Great course, the teacher is very clear and often goes into sufficient depth for the student to understand concepts. Assignments are challenging and help understanding course content.

от партнера M2 июня 2020 г.

This is, without a doubt, one of the most interesting courses I have ever taken. You will be challenged to create your own ideas and you will get to know what NP hard means in practice.

от партнера AM5 февр. 2017 г.

I like the instructor teaching approach and the evaluation system, the subject itself took me a lot of effort and i think the LNS technique should be teached just after local search.

Посмотреть все отзывы

Часто задаваемые вопросы

Когда я получу доступ к лекциям и заданиям?
Доступ к лекциям и заданиям предоставляется в зависимости от типа регистрации. Если вы проходите курс в режиме слушателя, то получите бесплатный доступ к большинству материалов курса. Чтобы открыть оцениваемые задания и возможность получить сертификат, необходимо будет приобрести прохождение с сертификатом. Это можно сделать во время прохождения в режиме слушателя или после него. Если вы не видите варианта 'Режим слушателя'.
Курс может не предлагаться в режиме слушателя. Попробуйте бесплатную пробную версию или подайте заявку на финансовую помощь.
Курс предлагаться в режиме 'Полный курс, без сертификата'. В нем можно просматривать все материалы, выполнять обязательные задания и получить итоговую оценку. Приобрести дополнительно прохождение с сертификатом в таком случае нельзя.
Что я получу, оплатив сертификацию?
Оплатив сертификацию, вы получите доступ ко всем материалам курса, включая оцениваемые задания. После успешного прохождения курса на странице ваших достижений появится электронный сертификат. Оттуда его можно распечатать или прикрепить к профилю LinkedIn. Просто ознакомиться с содержанием курса можно бесплатно.
Можно ли получить финансовую помощь?
Да, Coursera предоставляет финансовую помощь учащимся, которые не могут оплатить обучение. Чтобы подать заявление, перейдите по ссылке 'Финансовая помощь' слева под кнопкой 'Зарегистрироваться' и заполните форму. Если его примут, вы получите уведомление. Подробнее
• What are the pre-requisites for the class?
Good programming skills, knowledge of algorithms and linear algebra.
• What programming language will be used in this class?
A minimal knowledge of python is necessary to integrate with the course infrastructure. Outside of that, students are free to use any language of their choice.
• How difficult is this class?
A motivated student spending the time on the programming assignment will succeed in this class.
• Where can I get one of those T-Shirts?
At the discrete optimization store: http://www.zazzle.com.au/discreteoptimization

Остались вопросы? Посетите Центр поддержки учащихся.

Дискретная оптимизация

Дискретная оптимизация

Об этом курсе

Приобретаемые навыки