ECE 3484: Combinatorial Optimization

ECE 3484: Combinatorial Optimization

Waleed Meleis

Course description An introduction to combinatorial optimization, an emerging field that combines techniques from applied mathematics, operations research and computer science to solve optimization problems over discrete structures. Emphasizes problems that arise in the areas of Electrical and Computer Engineering, including (but not limited to) VLSI, computer aided design, parallel computing, computer architecture, and high performance compiling. Covers the foundations of algorithm analysis, including asymptotic notation and complexity theory, and a range of optimization techniques, including greedy algorithms, integer and linear programming, branch and bound, divide and conquer, dynamic programming, local optimization, simulated annealing, genetic algorithms and approximation algorithms. Considers the efficient generation of optimal solutions, the development and evaluation of heuristics, and the computation of tight upper and lower bounds.

Handouts, and announcements




Course texts
  1. E. Aarts and J. Lenstra, Local Search in Combinatorial Optimization, Wiley, 1997. 0-471-94822-5

  2. R. Ahuja, T. Magnanti, and J. Orlin, Network Flows, Prentice Hall, 1993. 0-13-617549-x

  3. G. Brassard and P. Bratley, Fundamentals of Algorithmics, Prentice Hall, 1996. 0-13-335068-1

  4. W. Cook, W. Cunningham, W. Pulleyblank, A Schrijver, Combinatorial Optimization, Wiley Interscience, 1998. 0-471-55894-X

  5. T. Cormen, C. Leiserson, R. Rivest, Introduction to Algorithms, McGraw Hill, 1991, 0-07-013143-0.

  6. R. Fourer, D. Gay, B. Kernighan, AMPL: A Modeling Language for Mathematical Programming, Boyd & Fraser, 1993, 0-89426-232-7

  7. M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP Completeness, Freeman, 1997. 0-7167-1045-5

  8. F. Hillier, G. Lieberman, Introduction to Mathematical Programming, McGraw-Hill, 1995. 0-07-911829-1

  9. E. Lawler, J. Lenstra, A. Rinnooy Kan, D. Shmoys, The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, 1997. 0-471-90413-9

  10. C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, 1982. 0-13-152462-3

ILP documentation

The AMPL and CPLEX manuals are on reserve in Snell library. Information about AMPL and CPLEX is also available in the following documents, and from the AMPL web site in the list at the bottom of this page.

Using AMPL and CPLEX at Northeastern

Running AMPL and CPLEX

Introduction to AMPL

AMPL manual

Running CPLEX

AMPL Modeling Language for Mathematical Programming

Useful links

Complexity results
Complexity results for scheduling problems
Joseph Culberson's Coloring Page
Math Forum: Game Theory / Linear / Non-Linear
Optimization Technology Center
The Stony Brook Algorithm Repository
INFORMS OR/MS Resource Collection