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
Homework
Project
Reading
- Introduction
Pap. 1-6, 20-23
Law. 1-15
Gar. 1-12
Cor. 15-27 (algorithm analysis)
- Complexity
Cor. 966-979 (introduction)
Cor. 979-982 (P and NP)
Cor. 984-1003 (NP completeness)
Cor. 1003-1017 (Other NPC problems)
- Greedy algorithms
Cor. 370-379 (greedy algorithms)
Cor. 393-401 (matroids)
Pap. 218-224 (matching, bipartite matching)
Pap. 289-294 (matroid intersection)
Coo. 289-291 (matroid intersection)
- Linear programming
Cor. 770-790 (introduction and formulation)
Hil. 81-87 (simplex)
- Integer programming
Hil. 538-555 (introduction and formulation)
Hil. 555-586 (branch and bound solution)
Bra. 312-317 (branch and bound examples)
- Local search
Aar 1-7 (introduction)
Law 215-231 (TSP tour creation heuristics)
Aar 215-234 (heuristics, 2-Opt, 3-Opt)
Aar 234-241 (experimental results)
Aar 246-249 (other local search)
Aar 249-254 (tabu search)
Aar 254-261 (Lin-Kernighan)
Aar 261-286 (simulated annealing)
Aar 286-302 (genetic algorithms)
Course texts
- E. Aarts and J. Lenstra, Local Search in Combinatorial
Optimization, Wiley, 1997. 0-471-94822-5
- R. Ahuja, T. Magnanti, and J. Orlin, Network Flows,
Prentice Hall, 1993. 0-13-617549-x
- G. Brassard and P. Bratley, Fundamentals of Algorithmics,
Prentice Hall, 1996. 0-13-335068-1
- W. Cook, W. Cunningham, W. Pulleyblank, A Schrijver, Combinatorial
Optimization, Wiley Interscience, 1998. 0-471-55894-X
- T. Cormen, C. Leiserson, R. Rivest, Introduction to Algorithms,
McGraw Hill, 1991, 0-07-013143-0.
- R. Fourer, D. Gay, B. Kernighan, AMPL: A Modeling Language for
Mathematical Programming, Boyd & Fraser, 1993, 0-89426-232-7
- M. Garey and D. Johnson, Computers and Intractability: A Guide to
the Theory of NP Completeness, Freeman, 1997. 0-7167-1045-5
- F. Hillier, G. Lieberman, Introduction to Mathematical Programming,
McGraw-Hill, 1995. 0-07-911829-1
- 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
- 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