Об этом курсе

Недавно просмотрено: 43 694

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 часов на выполнение

Английский

Будет ли вашей компании выгодно обучить сотрудников востребованным навыкам?

Попробуйте Coursera для бизнеса

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

Constraint Programming
Branch And Bound
Discrete Optimization
Linear Programming (LP)

Гибкие сроки

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

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

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

100% онлайн

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

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

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

Английский

Будет ли вашей компании выгодно обучить сотрудников востребованным навыкам?

Попробуйте Coursera для бизнеса

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

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

4,79/5 (оценок: 139)

Professor Pascal Van Hentenryck

63 644 учащихся

1 курс

Dr. Carleton Coffrin

Adjunct Lecturer

Computing and Information Systems

65 453 учащихся

2 курса

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

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

Неделя

1

Неделя 1

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

Welcome

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

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

Неделя

2

Неделя 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

Неделя 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

Неделя 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

Неделя 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

Неделя 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

Неделя 7

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

Advanced Topics: Part I

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

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

Неделя

8

Неделя 8

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

Advanced Topics: Part II

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

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

Рецензии

4.8

Рецензии: 164

5 stars
89,04 %
4 stars
8,25 %
3 stars
0,99 %
2 stars
0,14 %
1 star
1,56 %

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

от партнера MM9 авг. 2019 г.

Very good course for operation research aspirants. Assignments are very good to understand the problems and the complexity of the problems.Thanks to the team

от партнера BT15 сент. 2020 г.

This is an amazing course to really help students explore the variety of techniques that are available to solve extremely hard optimization problems.

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

I just completed the course. This an amazing course with an Outstanding professor and highly interesting, although difficult, assignments. Thanks for this! I am proud to have finished

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

Amazing course! Prof. Pascal is awesome, challenging, and motivating, teaches all the fundamentals of discrete optimization very clearly.

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

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

Когда я получу доступ к лекциям и заданиям?
Доступ к лекциям и заданиям предоставляется в зависимости от типа регистрации. Если вы проходите курс в режиме слушателя, то получите бесплатный доступ к большинству материалов курса. Чтобы открыть оцениваемые задания и возможность получить сертификат, необходимо будет приобрести прохождение с сертификатом. Это можно сделать во время прохождения в режиме слушателя или после него. Если вы не видите варианта 'Режим слушателя'.
Курс может не предлагаться в режиме слушателя. Попробуйте бесплатную пробную версию или подайте заявку на финансовую помощь.
Курс предлагаться в режиме 'Полный курс, без сертификата'. В нем можно просматривать все материалы, выполнять обязательные задания и получить итоговую оценку. Приобрести дополнительно прохождение с сертификатом в таком случае нельзя.
Что я получу, оплатив сертификацию?
Оплатив сертификацию, вы получите доступ ко всем материалам курса, включая оцениваемые задания. После успешного прохождения курса на странице ваших достижений появится электронный сертификат. Оттуда его можно распечатать или прикрепить к профилю LinkedIn. Просто ознакомиться с содержанием курса можно бесплатно.
Можно ли получить финансовую помощь?
Да. В некоторых программах обучения вы можете подать заявку на получение финансовой помощи или стипендии, если не можете оплатить регистрационный взнос. Если для выбранной вами программы предлагается такая возможность, вы увидите ссылку для подачи заявки на странице описания.
• 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

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

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