Disciplina Discipline MAC5781
Otimização Combinatória

Combinatorial Optimization

Área de Concentração: 45134

Concentration area: 45134

Criação: 26/06/2020

Creation: 26/06/2020

Ativação: 26/06/2020

Activation: 26/06/2020

Nr. de Créditos: 8

Credits: 8

Carga Horária:

Workload:

Teórica

(por semana)

Theory

(weekly)

Prática

(por semana)

Practice

(weekly)

Estudos

(por semana)

Study

(weekly)

Duração Duration Total Total
4 2 4 12 semanas 12 weeks 120 horas 120 hours

Docente Responsável:

Professor:

Marcel Kenji de Carli Silva

Objetivos:

Ensinar técnicas para o tratamento de problemas de otimização combinatória, em especial aqueles que podem ser formulados como problemas em grafos.

Objectives:

Teaching techniques for solving combinatorial optimization problems, especially those that can be formulated as problems on graphs.

Justificativa:

Problemas de otimização sobre grafos e outras estruturas discretas são fundamentais tanto pelas suas aplicações diretas, como para fornecer modelos abstratos em que outras áreas se apoiam. As técnicas de desenvolvimento de algoritmos para esses problemas são cruciais para uma fundamentação na área de otimização.

Rationale:

Optimization problems over graphs and other discrete structures are fundamental not only for their direct applications, but also for providing abstract models on which other areas rely. The techniques for algorithm design to solve these problems are crucial for a solid background in optimization.

Conteúdo:

O escopo da otimização combinatória e programação inteira. Modelagem de vários problemas usando variáveis 0/1. O problema do transporte. Especialização do método simplex para redes. Aplicações: teorema de Hall, teorema de König, teorema de Dilworth. O problema do transporte capacitado: o método primal-dual. Algoritmos para fluxos máximos em redes. Fluxos de custo mínimo e circulações viáveis: o método "out-of-kilter". Estudo aprofundado de poliedros de alguns problemas não-unimodulares bem resolvidos (emparelhamentos, branchings, etc.).

Content:

The scope of combinatorial optimization and integer programming. Modelling various problems using 0-1 variables. The transportation problem. The simplex method applied to networks. Applications: Hall's Theorem, König's Theorem, Dilworth's Theorem. The capacited transportation problem: the primal-dual method. Algorithms for maximum flows. Minimum-cost flows and feasible circulations: the "out-of-kilter" method. In-depth study of polyhedra for some well-solved problems that are not unimodular (matchings, branchings).

Forma de Avaliação:

Média ponderada de provas e exercícios.

Bibliografia:

W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver, Combinatorial Optimization, John Wiley, 1998. R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993. C.H. Papadimitrou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, 1982. E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart & Winston, 1976. V. Chvátal, Linear Programming, Freeman, New York, 1983.

Bibliography:

W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver, Combinatorial Optimization, John Wiley, 1998. R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993. C.H. Papadimitrou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, 1982. E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart & Winston, 1976. V. Chvátal, Linear Programming, Freeman, New York, 1983.

Idiomas ministrados:

Inglês

Languages taught:

English

Tipo de oferecimento da disciplina:

Presencial

Class type:

Presencial