Optimization Methods

Optimization Methods

16 พย 50 นี้

Final Examination:

March, 2009) Open Book !!!

The slides used in the course:

1st week

slide no.1: Introduction to optimization problems slide no 1

2nd week

slide no.2: Linear programmng slide no 2
Download Octave: Octave-3.2.4_i686-pc-mingw32_gcc-4.4.0_setup.exe
Prof.Andrew’s Linear algebra review

3rd-4th weeks

slide no.3: Graphs and networks slide no 3

5th week

slide no.4: Polyhedral theory slide no 4

6-7th weeks

slide no.5: The theory of valid inequalities slide no 5

8th week

Midterm Examination (scope--slide no.1, no.5)

21 July,2003) Open Book!!!

9th week

slide no.6: Strong valid inequalities and facets for structured integer programming
Introduction to duality and relaxation
Lagrangian relaxation and duality slide no 6

10-11th weeks

slide no.7: Introduction to general algorithms
Branch-and-bound using linear programming relaxations slide no 7 (additional sheets about the dual simplex algorithm additional slide A)
slide no.8: Fractional cutting plane algorithm slide no 8

12th week

slide no.9: Introduction to special-purpose algorithms
A cutting-plane algorithm using strong valid inequalities
Decomposition algorithms slide no 9 (additional sheets about subgradient additional slide B)

13-14th weeks

slide no.10: Matching slide no 10

15th week

slide no.11: Introduction to approximation algorithm slide no 11

16th week

Final Examination

Text Books:

G.Nemhauser and L.Wolsey, Integer and Combinatorial Optimization, A Wiley-Interscience Pub. (MAIN TEXT)
C.Papadimitriou and K. Steiglitz., Combinatorial Optimization: Algorithms and Complexity, Dover Pub.