À propos de ce cours

46 115 consultations récentes

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.

Dates limites flexibles

Réinitialisez les dates limites selon votre disponibilité.

Certificat partageable

Obtenez un Certificat lorsque vous terminez

100 % en ligne

Commencez dès maintenant et apprenez aux horaires qui vous conviennent.

Niveau intermédiaire

Approx. 65 heures pour terminer

Anglais

Votre entreprise pourrait-elle bénéficier de la formation des employés à des compétences recherchées ?

Essayez Coursera pour les affaires

Compétences que vous acquerrez

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

Dates limites flexibles

Réinitialisez les dates limites selon votre disponibilité.

Certificat partageable

Obtenez un Certificat lorsque vous terminez

100 % en ligne

Commencez dès maintenant et apprenez aux horaires qui vous conviennent.

Niveau intermédiaire

Approx. 65 heures pour terminer

Anglais

Votre entreprise pourrait-elle bénéficier de la formation des employés à des compétences recherchées ?

Essayez Coursera pour les affaires

Enseignants

Évaluation de l'enseignant

4,79/5 (139 évaluations)

Professor Pascal Van Hentenryck

63 492 étudiants

1 cours

Dr. Carleton Coffrin

Adjunct Lecturer

Computing and Information Systems

65 301 étudiants

2 cours

Programme de cours : ce que vous apprendrez dans ce cours

Évaluation du contenu96%(4,299 évaluations)

Semaine

1

Semaine 1

2 heures pour terminer

Welcome

2 heures pour terminer

4 vidéos (Total 43 min), 2 lectures, 1 quiz

Semaine

2

Semaine 2

7 heures pour terminer

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 heures pour terminer

9 vidéos (Total 101 min)

9 vidéos

Knapsack 1 - intuition2 min

Knapsack 2 - greedy algorithms7 min

Knapsack 3 - modeling8 min

Knapsack 4 - dynamic programming17 min

Knapsack 5 - relaxation, branch and bound14 min

Knapsack 6 - search strategies, depth first, best first, least discrepancy14 min

Assignments Getting Started13 min

Knapsack & External Solver10 min

Exploring the Material - open course design, optimization landscape, picking your adventure10 min

Semaine

3

Semaine 3

17 heures pour terminer

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 heures pour terminer

13 vidéos (Total 248 min), 1 lecture, 2 quiz

13 vidéos

CP 1 - intuition, computational paradigm, map coloring, n-queens27 min

CP 2 - propagation, arithmetic constraints, send+more=money26 min

CP 3 - reification, element constraint, magic series, stable marriage16 min

CP 4 - global constraint intuition, table constraint, sudoku19 min

CP 5 - symmetry breaking, BIBD, scene allocation18 min

CP 6 - redundant constraints, magic series, market split11 min

CP 7 - car sequencing, dual modeling18 min

CP 8 - global constraints in detail, knapsack, alldifferent33 min

CP 9 - search, first-fail, euler knight, ESDD25 min

CP 10 - value/variable labeling, domain splitting, symmetry breaking in search28 min

Graph Coloring6 min

Optimization Tools5 min

Set Cover8 min

1 lecture

Optimization Tools10 min

Semaine

4

Semaine 4

13 heures pour terminer

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 heures pour terminer

10 vidéos (Total 191 min)

10 vidéos

LS 1 - intuition, n-queens13 min

LS 2 - swap neighborhood, car sequencing, magic square15 min

LS 3 - optimization, warehouse location, traveling salesman, 2-opt, k-opt23 min

LS 4 - optimality vs feasibility, graph coloring22 min

LS 5 - complex neighborhoods, sports scheduling21 min

LS 6 - escaping local minima, connectivity15 min

LS 7 - formalization, heuristics, meta-heuristics introduction22 min

LS 8 - iterated location search, metropolis heuristic, simulated annealing, tabu search intuition18 min

LS 9 - tabu search formalized, aspiration, car sequencing, n-queens26 min

Traveling Salesman10 min

Semaine

5

Semaine 5

2 heures pour terminer

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 heures pour terminer

6 vidéos (Total 130 min)

Semaine

6

Semaine 6

12 heures pour terminer

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 heures pour terminer

6 vidéos (Total 136 min)

Semaine

7

Semaine 7

11 heures pour terminer

Advanced Topics: Part I

11 heures pour terminer

2 vidéos (Total 51 min)

Semaine

8

Semaine 8

1 heure pour terminer

Advanced Topics: Part II

1 heure pour terminer

2 vidéos (Total 32 min), 1 lecture

Avis

4.8

164 avis

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

Meilleurs avis pour OPTIMISATION DISCRÈTE

par SK29 mai 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.

par GD1 mai 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

par DL26 oct. 2016

Too good course! One of the very best courses on Coursera!

Thank you so much. It is a wonder to follow your course.

par XW15 juil. 2017

Awesome course, learned a lot for solving NP hard problem. It could be hard for people without basic algorithm and data structure background.

Voir tous les avis

Foire Aux Questions

Quand aurai-je accès aux vidéos de cours et aux devoirs ?
L’accès à des vidéos de cours et des devoirs dépend de votre type d’inscription. Si vous suivez un cours en mode auditeur libre, vous pourrez voir la plupart des contenus de cours gratuitement. Pour accéder aux devoirs notés et obtenir un certificat, vous devrez acheter une expérience de certificat, pendant ou après avoir assister au cours en tant qu’auditeur libre. Si vous ne visualisez pas l’option auditeur libre :
Il est possible que le cours ne propose pas d’option auditeur libre. Vous pouvez en revanche accéder à un essai gratuit ou faire une demande d'aide financière.
Le cours propose peut-être « Cours complet, aucun certificat » à la place. Cette option vous permet de voir tous les contenus de cours, de soumettre les évaluations requises et d'obtenir une note finale. Cependant, vous ne pourrez pas acheter une expérience de certificat.
À quoi ai-je droit si j'achète le Certificat ?
Lorsque vous achetez un Certificat, vous bénéficiez d'un accès à tout le contenu du cours, y compris les devoirs notés. Lorsque vous avez terminé et réussi le cours, votre Certificat électronique est ajouté à votre page Accomplissements. À partir de cette page, vous pouvez imprimer votre Certificat ou l'ajouter à votre profil LinkedIn. Si vous souhaitez seulement lire et visualiser le contenu du cours, vous pouvez accéder gratuitement au cours en tant qu'auditeur libre.
Une aide financière est-elle possible ?
Oui. Dans certains programmes d’apprentissage, vous pouvez demander une aide financière ou une bourse d’études si vous ne pouvez pas payer les frais d’inscription. Si une aide financière ou une bourse d’études est disponible pour le programme d’apprentissage choisi, vous trouverez un lien pour faire une demande sur la page de description.
• 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

D'autres questions ? Visitez le Centre d'Aide pour les Étudiants.

Optimisation discrète