Informações sobre o curso

41.769 visualizações recentes

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.

Prazos flexíveis

Redefinir os prazos de acordo com sua programação.

Certificados compartilháveis

Tenha o certificado após a conclusão

100% on-line

Comece imediatamente e aprenda em seu próprio cronograma.

Nível intermediário

Aprox. 65 horas para completar

Inglês

Sua empresa se beneficiaria do treinamento dos funcionários em habilidades sob demanda?

Experimente o Coursera for Business

Habilidades que você terá

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

Prazos flexíveis

Redefinir os prazos de acordo com sua programação.

Certificados compartilháveis

Tenha o certificado após a conclusão

100% on-line

Comece imediatamente e aprenda em seu próprio cronograma.

Nível intermediário

Aprox. 65 horas para completar

Inglês

Sua empresa se beneficiaria do treinamento dos funcionários em habilidades sob demanda?

Experimente o Coursera for Business

Instrutores

Classificação do instrutor

4,8/5 (138 classificações)

Professor Pascal Van Hentenryck

62.317 aprendizes

1 Curso

Dr. Carleton Coffrin

Adjunct Lecturer

Computing and Information Systems

64.130 aprendizes

2 Cursos

Programa - O que você aprenderá com este curso

Classificação do conteúdo96%(4,285 classificações)

Semana

1

Semana 1

2 horas para concluir

Welcome

2 horas para concluir

4 vídeos (Total 43 mín.), 2 leituras, 1 teste

Semana

2

Semana 2

7 horas para concluir

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 horas para concluir

9 vídeos (Total 101 mín.)

9 videos

Knapsack 1 - intuition2min

Knapsack 2 - greedy algorithms7min

Knapsack 3 - modeling8min

Knapsack 4 - dynamic programming17min

Knapsack 5 - relaxation, branch and bound14min

Knapsack 6 - search strategies, depth first, best first, least discrepancy14min

Assignments Getting Started13min

Knapsack & External Solver10min

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

Semana

3

Semana 3

17 horas para concluir

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 horas para concluir

13 vídeos (Total 248 mín.), 1 leitura, 2 testes

13 videos

CP 1 - intuition, computational paradigm, map coloring, n-queens27min

CP 2 - propagation, arithmetic constraints, send+more=money26min

CP 3 - reification, element constraint, magic series, stable marriage16min

CP 4 - global constraint intuition, table constraint, sudoku19min

CP 5 - symmetry breaking, BIBD, scene allocation18min

CP 6 - redundant constraints, magic series, market split11min

CP 7 - car sequencing, dual modeling18min

CP 8 - global constraints in detail, knapsack, alldifferent33min

CP 9 - search, first-fail, euler knight, ESDD25min

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

Graph Coloring6min

Optimization Tools5min

Set Cover8min

1 leituras

Optimization Tools10min

Semana

4

Semana 4

13 horas para concluir

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 horas para concluir

10 vídeos (Total 191 mín.)

10 videos

LS 1 - intuition, n-queens13min

LS 2 - swap neighborhood, car sequencing, magic square15min

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

LS 4 - optimality vs feasibility, graph coloring22min

LS 5 - complex neighborhoods, sports scheduling21min

LS 6 - escaping local minima, connectivity15min

LS 7 - formalization, heuristics, meta-heuristics introduction22min

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

LS 9 - tabu search formalized, aspiration, car sequencing, n-queens26min

Traveling Salesman10min

Semana

5

Semana 5

2 horas para concluir

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 horas para concluir

6 vídeos (Total 130 mín.)

Semana

6

Semana 6

12 horas para concluir

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 horas para concluir

6 vídeos (Total 136 mín.)

Semana

7

Semana 7

11 horas para concluir

Advanced Topics: Part I

11 horas para concluir

2 vídeos (Total 51 mín.)

Semana

8

Semana 8

1 hora para concluir

Advanced Topics: Part II

1 hora para concluir

2 vídeos (Total 32 mín.), 1 leitura

Avaliações

4.8

161 avaliações

5 stars
89,08%
4 stars
8,18%
3 stars
1%
2 stars
0,14%
1 star
1,58%

Principais avaliações do OTIMIZAÇÃO DISCRETA

por BT15 de set de 2020

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

por AD5 de jun de 2019

Excellent course! The course video are very clear and build on each other as the course progress. It is well structured. The assignments have the right amount of difficulty.

por XW15 de jul de 2017

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

por SK29 de mai de 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.

Visualizar todas as avaliações

Perguntas Frequentes – FAQ

Quando terei acesso às palestras e às tarefas?
O acesso a palestras e tarefas depende do tipo de inscrição. Se você participar de um curso como ouvinte, você poderá ver quase todo o conteúdo do curso gratuitamente. Para acessar tarefas valendo nota e obter um Certificado, você precisará adquirir a experiência do Certificado, durante ou após a participação como ouvinte. Se você não vir a opção de participar como ouvinte:
o curso pode não oferecer essa opção. Você pode experimentar um teste gratuito ou solicitar o auxílio financeiro.
Em vez disso, o curso pode oferecer 'Curso completo, sem Certificado'. Com esta opção, é possível ver todo o conteúdo do curso, enviar as avaliações necessárias e obter uma nota final. Isso também significa que você não poderá comprar uma experiência de Certificado.
O que recebo ao adquirir o Certificado?
Quando você adquire o Certificado, ganha acesso a todo o material do curso, incluindo avaliações com nota atribuída. Após concluir o curso, seu Certificado eletrônico será adicionado à sua página de Participações e você poderá imprimi-lo ou adicioná-lo ao seu perfil no LinkedIn. Se quiser apenas ler e assistir o conteúdo do curso, você poderá frequentá-lo como ouvinte sem custo.
Existe algum auxílio financeiro disponível?
Sim. Em programas de aprendizado selecionados, você pode solicitar auxílio financeiro ou uma bolsa de estudos caso não consiga pagar a taxa de inscrição. Se o auxílio financeiro ou bolsa de estudos estiver disponível para a seleção do seu programa de aprendizado, você encontrará um link para se inscrever na página de descrição.
• 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

Mais dúvidas? Visite o Central de Ajuda ao estudante.

Otimização discreta