Math 490

Heuristics for Discrete Optimization

Spring 2009

CLASS MEETING TIMES.

DESCRIPTION. Discrete optimization problems are those problems with decisions that are logical (yes/no) or countable. Topics include relaxation techniques, constructive heuristics, improving search techniques (e.g. simplex method, simulated annealing, tabu search and genetic algorithms), branch and bound schemes, and valid inequalites for branch and cut methods.

RECOMMENDED BACKGROUND. Csci 141, Csci 241 and Math 323.

TOPIC OUTLINE

  1. Survey of Discrete Optimization Methods [11 lectures] (Ra Ch.11,12)
    1. Enumeration and Relaxations
    2. Strengthening Relaxations
    3. Branch and Bound
    4. Refinements to Branch and Bound
    5. Improving Search Heuristics
    6. Constructive Heuristics
  2. Extending Discrete Improving Search [9 lectures]
    1. Simulated Annealing (JAMS, Ra Ch.12)
    2. Tabu Search (GL, Gl, Ra Ch.12)
    3. Genetic Algorithms (Be, G)
    4. Evolutionary Search Strategies (Ba, KWS)
  3. Lagrangean Relaxation [8 lectures] (PR Ch.5, Be)
    1. Introduction
    2. Exposition
    3. Choosing Lagrange Multipliers
  4. Matroids and Integer Solvability of IPs [5 lectures] (PR Ch.3,4.2)
    1. Matroids (PR Ch 3.1-3.4)
    2. Unimodularity
    3. Total Dual Integrality
  • Student Project Ideas [2 lectures ]
    1. Periodic meetings in smaller groups with instructor
    2. Final presentations open to the public

    REFERENCES.

    1. {Ba} Back T. Evolutionary Algorithms in Theory and Practice. Oxford University Press, 1996.
    2. {Be} Bean, J.C., ``Genetics and Random Keys for Sequencing and Optimization,'' (1992) Tech. Report 92-43, Dept. of Industrial and Operations Engr., U. of Michigan, Ann Arbor, MI 48109-2117.
    3. {G} Goldberg, D.E. GAs in Search Optimization and Machine Learning, Addison Wesley (1989).
    4. {Gl} Glover, F., ``Tabu Search: A Tutorial,'' INTERFACES, 20 (1990) 74-94.
    5. {GL} Glover, F. and M. Laguna, ``Tabu Search," chapter in Modern Heuristics for Combinatorial Problems, (1993).
    6. {JAMS} Johnson, D.S., C.R. Aragon, L.A. McGeoch, and C. Schevon, ``Opimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning,'' Operations Research, 37 (1989) 865-892.
    7. {KWS} Kincaid, R.K., M. Weber and J. Sobieski, ``An Atypical Evolutionary Algorithm,'' under review for Computers and IE.
    8. {PR} Parker, R.G. and R.L. Rardin, ``Chapter 5: Nonpolynomial Algorithms--Partial Enumeration," Discrete Optimization}, Academic Press, Boston (1988).
    9. {Ra} Optimization in Operations Research, Ronald L. Rardin, Prentice Hall (1998). Chapters 11 and 12.
    HOMEWORK. Regular homework emphasizing and extending lecture material will be assigned and graded. Late homeworks are not accepted except in the case of an unanticipatable absence (e.g. serious illness, death in the family, loss of your favorite videotape etc.).

    COMPUTING. Homework will require using computer programs, but students will not be required to do any significant computer programming. The final project, however, may involve significant computing.

    EXAMINATIONS. There will be two traditional exams during the term. There is no final examination, rather there will be presentations of final projects to which the public may be invited.

    GRADES. There will be two exams and a final project. The exams will count 50% of the final course grade. The exam will be open notes. The project will count 20% of the final course grade and will include both a written document and an oral presentation. Homework assignments will be given periodically throughout the semester and together will count 30% of the final course grade.