Об этом курсе: 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.
Для кого этот курс: Good programming skills, knowledge of fundamental algorithms, and linear algebra.
Автор: The University of Melbourne
Преподаватели: Professor Pascal Van Hentenryck
Преподаватели: Dr. Carleton Coffrin, Adjunct Lecturer
Computing and Information Systems
| Уровень | Intermediate |
| Выполнение | 8 weeks of study, 10-15 hours per week |
| Язык | English |
| Как пройти курс | Чтобы пройти курс, выполните все оцениваемые задания. |
| Оценки пользователей |
Программа курса
НЕДЕЛЯ 1
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.
4 видео, 3 материалов для самостоятельного изучения
- Видео: Course Promo
- Видео: Course Motivation - Indiana Jones, challenges, applications
- Reading: Start of Course Survey
- Reading: Socialize
- Видео: Course Introduction - philosophy, design, grading rubric
- Reading: Course Syllabus
- Видео: Assignments Introduction & Any Integer
Оцениваемый: Any Integer
НЕДЕЛЯ 2
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.
9 видео
- Видео: Knapsack 1 - intuition
- Видео: Knapsack 2 - greedy algorithms
- Видео: Knapsack 3 - modeling
- Видео: Knapsack 4 - dynamic programming
- Видео: Knapsack 5 - relaxation, branch and bound
- Видео: Knapsack 6 - search strategies, depth first, best first, least discrepancy
- Видео: Assignments Getting Started
- Видео: Knapsack & External Solver
- Видео: Exploring the Material - open course design, optimization landscape, picking your adventure
Оцениваемый: Knapsack
НЕДЕЛЯ 3
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.
13 видео, 1 материал для самостоятельного изучения
- Видео: CP 1 - intuition, computational paradigm, map coloring, n-queens
- Видео: CP 2 - propagation, arithmetic constraints, send+more=money
- Видео: CP 3 - reification, element constraint, magic series, stable marriage
- Видео: CP 4 - global constraint intuition, table constraint, sudoku
- Видео: CP 5 - symmetry breaking, BIBD, scene allocation
- Видео: CP 6 - redundant constraints, magic series, market split
- Видео: CP 7 - car sequencing, dual modeling
- Видео: CP 8 - global constraints in detail, knapsack, alldifferent
- Видео: CP 9 - search, first-fail, euler knight, ESDD
- Видео: CP 10 - value/variable labeling, domain splitting, symmetry breaking in search
- Видео: Graph Coloring
- Видео: Optimization Tools
- Reading: Optimization Tools
- Видео: Set Cover
- Ungraded Programming: Set Cover
Оцениваемый: Graph Coloring
НЕДЕЛЯ 4
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.
10 видео
- Видео: LS 1 - intuition, n-queens
- Видео: LS 2 - swap neighborhood, car sequencing, magic square
- Видео: LS 3 - optimization, warehouse location, traveling salesman, 2-opt, k-opt
- Видео: LS 4 - optimality vs feasibility, graph coloring
- Видео: LS 5 - complex neighborhoods, sports scheduling
- Видео: LS 6 - escaping local minima, connectivity
- Видео: LS 7 - formalization, heuristics, meta-heuristics introduction
- Видео: LS 8 - iterated location search, metropolis heuristic, simulated annealing, tabu search intuition
- Видео: LS 9 - tabu search formalized, aspiration, car sequencing, n-queens
- Видео: Traveling Salesman
Оцениваемый: Traveling Salesman
НЕДЕЛЯ 5
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. .
6 видео
- Видео: LP 1 - intuition, convexity, geometric view
- Видео: LP 2 - algebraic view, naive algorithm
- Видео: LP 3 - the simplex algorithm
- Видео: LP 4 - matrix notation, the tableau
- Видео: LP 5 - duality derivation
- Видео: LP 6 - duality interpretation and uses
НЕДЕЛЯ 6
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.
6 видео
- Видео: MIP 1 - intuition, relaxation, branch and bound, knapsack, warehouse location
- Видео: MIP 2 - modeling, big-M, warehouse location, graph coloring
- Видео: MIP 3 - cutting planes, Gomory cuts
- Видео: MIP 4 - convex hull, polyhedral cuts, warehouse location, node packing, graph coloring
- Видео: MIP 5 - cover cuts, branch and cut, seven bridges, traveling salesman
- Видео: Facility Location
Оцениваемый: Facility Location
НЕДЕЛЯ 7
Advanced Topics: Part I
These lectures cover some more advanced concepts in optimization. They introduce constraint-programming techniques for scheduling and routing.
2 видео
- Видео: Scheduling - jobshop, disjunctive global constraint
- Видео: Vehicle Routing
Оцениваемый: Vehicle Routing
НЕДЕЛЯ 8
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.
2 видео
- Видео: Large Neighborhood Search - asymmetric TSP with time windows
- Видео: Column Generation - branch and price, cutting stock
Часто задаваемые вопросы
Как это работает
Coursework
Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.
Help from Your Peers
Connect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.
Certificates
Earn official recognition for your work, and share your success with friends, colleagues, and employers.
Авторы
The University of Melbourne
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.
Рейтинги и отзывы
Wonderful material and humorous instructor.
BTW, I like his hat : )
Excellent course. The programming assignments make you think about optimization
The programming assignments of this course are very challenge and the pursuit of the 'Good Optimization' is torturous, especially after Knapsack Problem, such as the TSP, Facility Problem and VRP. However, the sense of achievement gained when you passed the online judge is also unspeakable. Last but not least, Professor Pascal Van Hentenryck is really a nice man, he is humorous and charming. Wish you a memorable and nice experiences on the on the journey of OPTIMIZATION.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
X
I love this course!