Tentative Topics
1. Introduction to complexity theory
2. Heuristic, Dichotomous Search, and Neighborhood search
3. Greedy Random Adaptive Search Procedure
4. Simulated Annealing Algorithm
5. Genetic Algorithm
6. Tabu Search
7. Scatter Search
8. Bio-Inspired Algorithm – Ant Colony Optimization and Artificial Neural Network
9. Agent Based Modeling and Optimization
10. Simulation and Optimization
11. Advanced Topics and Recent Trend
12. Application and Presentations
* Topic may vary depends on the availability of time and interests of students
List of papers or publications
[1]
C. Tovey, (2002) "Tutorial on Computational Complexity,” Interfaces, Vol. 32, No. 3, pp. 30-61.
Neighborhood Search Heuristics and Meta-Heuristics
[2]
C. R. Reeves, (1993)
“Modern Heuristic techniques for Combinatorial Problems,” John Wily & Sons, New York, NY.
GRASP –
Semi-Greedy and Sampling
[3]
J.P. Hart and A.W. (1987) Shogan Semi-greedy Heuristics: An Empirical Study. Operations
Research Letters, 6:107–114.
[4]
T.A. Feo
and M.G.C. Resende (1989) A Probabilistic Heuristic
for a Computationally Difficult Set Covering Problem. Operations Research
Letters, 8:67–71.
[5]
T.A. Feo
and M.G.C. Resende (1995) Greedy Randomized Adaptive Search
Procedures. J. of Global Optimization,
6:109–133, 1995.
[6]
L. Pitsoulis and M.G.C. Resende
(2002) Greedy randomized adaptive search procedures. In P.M.Pardalos
and M.G.C.Resende, eds, Handbook of Applied Optimization, pp.
168–181, Oxford University Press.
[7]
M.G.C. Resende
and C.C. Ribeiro (2003) Greedy Randomized Adaptive Search
Procedures. In F. Glover and G. Kochenberger, eds, Handbook of Metaheuristics, pp. 219–249, Kluwer Academic Publishers, 2003.
[8]
P. Festa
and M.G.C. Resende (2002) GRASP: An Annotated Bibliography.
In C.C. Ribeiro and P. Hansen, editors, Essays and
Surveys on Metaheuristics, pp. 325–367, Kluwer
Academic Publishers, 2002.
[9]
S. Kirkpatrick and C. D. Gelatt and M. P. Vecchi,
Optimization by Simulated Annealing, Science, Vol
220, Number 4598, pages 671-680, 1983.
[10]
R. W. Eglese,
(1990), Simulated Annealing – A Tool for Operations Research, European Journal of Operational Research, 46:
271-281
[11]
C. Koulamas, S. R. Antony, and R. Jaen. A Survey of Simulated Annealing
Applications to Operations Research Problems. Omega International Journal of
Management Science, 22(1):41–56, 1994.
[12]
B. Suman and P.
Kumar, (2006) A survey of simulated annealing as a tool for single and multiobjective optimization, Journal of Operational
Research Society, 57:1143-1160.
[13]
W.C. Chiang and R. Russell, (1996) “Simulated Annealing Metaheuristics for the Vehicle
Routing Problem with Time Windows, Annals of Operations Research, 63:3-27.
[14]
D. Whitley, A Genetic Algorithm Tutorial, Computer
Science Department Colorado State University, CO, http://www.cs.iastate.edu/~honavar/ga_tutorial.pdf
[15]
C. L. Reeves, (1997) Genetic Algorithm for the Operations
Researcher, INFORMS Journal of Computing,
9:3 231-250
[16]
J. Beasley and P.C. Chu (1996) A Genetic Algorithm for the Set Covering
Problem. European Journal of Operational Research, 94(2), 393–404.
[17]
J. Beasley and P.C. Chu (1998) A Genetic Algorithm for the Multi-Dimension
Knapsack Problem, Journal of Heuristics 4, 63-86
[18]
Mitchell, Melanie, (1996), An Introduction to Genetic Algorithms, MIT
Press, Cambridge, MA.
[19]
Glover, F. and M. Laguna. (1997). Tabu
Search. Kluwer,
Norwell, MA.
[20]
Glover, F. "Tabu Search — Part I", ORSA Journal on Computing
1989 1: 3, 190-206.
[21]
Glover, F. "Tabu Search — Part II", ORSA Journal on Computing
1990 2: 1, 4-32.
[22]
Battiti, R. and G. Tecchiolli (1994), “The Reactive Tabu
Search”, ORSA Journal on Computing 6, 126-140.
[23]
Gendreau, M., A. Hertz and G. Laporte
(1994), “A Tabu Search Heuristic for the
Vehicle Routing Problem”, Management Science 40, 1276-1290.
[24]
Glover, F.
(1992), “Ejection chains, Reference Structures and Alternating Path Methods for
Traveling Salesman Problems”, University of Colorado. Shortened version published in Discrete
Applied Mathematics 65,
223-253, 1996.
[25]
Gendreau, M. (2002), “Recent Advances in Tabu Search”, in Essays and Surveys in Metaheuristics,
C.C. Ribeiro and P. Hansen (eds.), Kluwer Academic Publishers, pp. 369-377.
[26]
F. Glover, M. Laguna and R. Martí,
(2003) Scatter
Search, Advances in Evolutionary Computation: Theory and Applications, A. Ghosh and S. Tsutsui (Eds.),
Springer-Verlag, New York, pp. 519-537 (2003)
[27]
M. Laguna,
Scatter Search, In Handbook of Applied
Optimization, P. M. Pardalos and M. G. C. Resende (Eds.), Oxford University Press, pp. 183-193 (2002)
[28]
F. Glover, M. Laguna and R. Martí , (2000) Fundamentals of Scatter Search and Path Relinking, Control and Cybernetics, vol. 39, no. 3 pp.
653-684 (2000)
Ant Colony Optimization, Swarm
Intelligence, Partical Swarm, Harmony Search
[29]
M. Dorigo & T. Stützle,
2004. Ant Colony Optimization, MIT Press
[30]
M. Dorigo
& L. M. Gambardella, 1997. "Ant Colony System: A Cooperative Learning
Approach to the Traveling Salesman Problem". IEEE Transactions on
Evolutionary Computation, 1 (1): 53–66.
[31]
E. Bonabeau,
M. Dorigo et G. Theraulaz, 1999. Swarm Intelligence: From Natural to
Artificial Systems, Oxford University Press
[32]
A. P. Engelbrecht. Fundamentals of
Computational Swarm Intelligence. Wiley, 2005.
[33]
Haykin, S. (1999) Neural Networks: A Comprehensive
Foundation, Prentice Hall
[34]
“An Online
Textbook on Neural Network” http://www.statsoft.com/textbook/stneunet.html
Simulation and Optimization
[35] F. Azadivar, (2004), “A Tutorial on Simulation Optimization ,”Winter Simulation Conference. 198-204
Local Search for General Integer Program -- NSIP
[36] Fischetti, M., & Lodi, A. (2003). Local Branching. Math. Programming: Series B, 98, 23-47.
Advanced Topics, Recent Trend and Applications
[37] Osman, I.H. and J.P. Kelly (eds.) (1996), Meta-Heuristics: Theory and Applications, Kluwer Academic Publishers, Norwell, MA.
Sample Code:
Sample code for dichotomous search, simulated annealing, genetic algorithm, tabu search, scatter search for problems such as vehicle routing will be provided.