Computational Optimization Techniques

Participation Prerequisites

Interests in technical orientation and classic settings in computer science

Course Content

Session 1

Content:

• Introduction to combinatorial optimization
• Application of linear models
• Defining mixed integer programming models
• Examples: facility location, scheduling, transportation

Illustrative Method:

• Construct models
• Group discussion
• Software implementation

Session 2

Content:

• Introduction to metaheuristics
• Trajectory methods
• Evolutionary computation
• Comparison and application

Illustrative method:

• Algorithm visualization
• Student presentation

Session 3

Content:

• Research proposal in diverse fields
  
• Guest lectures on extended topics (hybridiza-tion, real-cases)

Illustrative method:

• Final presentation and discussion

Intended Learning Outcomes and Competencies

• Building efficient and transformative mathematical models
• Applying state-of-the-art optimization software
• Familiarizing with metaheuristic framework

Instruction Type

On-campus face-to-face.

Form of Examination

Class participation: 30%

Active participation and lively discussion in the
classroom are greatly encouraged.

Research proposal: 40%

The purpose of a research proposal is twofold. Students
are first required to summarize existing solution
methods in their individual research field, if
applicable, with an emphasis on the implementations
of metaheuristics. More importantly, the proposal
shall focus on a specific problem setting. Students
are to design new algorithms using metaheuristic
framework. For conventional combinatorial
problems, constructive suggestions and extensions
are expected.

Or, Exercises in Modeling: 40%

Presentation: 30%

For refinement and further discussion, students
are to present their proposal/models in the third
session.

Literature

Recommended Reading:

1) E. H. L. Aarts and J. K. Lenstra, editors. Local Search in Combinatorial Optimization. J. Wiley & Sons, Chichester, UK, 1997.

2) F. Glover. Heuristics for integer programming using surrogate constraints. Decision Sciences, 8:156 – 166, 1977.

3) C. Blum and A. Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3):268–308, 2003.

4) G. Kontoravdis and J. F. Bard. A grasp for the vehicle routing problem with time windows. ORSA Journal on Computing, 7(1):10–23, 1995.

5) M.G.C. Resende. Greedy randomized adaptive search procedures (grasp). Journal of Global Optimization, 6:109–133, 1999.

6) C. Blum and M. Dorigo. The hyper-cube framework for ant colony optimization. IEEE Transactions on Systems, Man and Cybernetics, Part B, 34(2):1161–1172, 2004.

7) J. B. Chambers and J. W. Barnes. New tabu search results for the job shop scheduling problem. Technical report, University of Texas, Austin, 1996. Graduate Program in Operations Research and Industrial Engineering.

8) D. deWerra and A. Hertz. Tabu search techniques: A tutorial and an application to neural networks. OR Spektrum, 11:131–141, 1989.

9) M. Dell’Amico and M. Trubian. Applying tabu search to the job-shop scheduling problem. Annals of Operations Research, 41:231–252, 1993.

10) F. Glover. Tabu search - part i. ORSA Journal on Computing, 1:190–206, 1989.

11) F. Glover. Tabu search - part ii. ORSA Journal on Computing, 2:4–32, 1990.

12) P. Hansen and N. Mladenovic. Variable neighborhood search. In Edmund K. Burke and Graham Kendall, editors, Search Methodologies - Introductory Tutorials in Optimization and Decision Support Techniques, chapter 8, pages 211–238. Springer Science + Business Media, Inc., 2005.

13) S. Kirkpatrick, C. D. Gelatt, andM. P. Vecchi. Optimization by simulated annealing. Science, 220:671 – 680, 1983.

14) R. Marti, M. Laguna, and F. Glover. Principles of scatter search. European Journal of Operational Research, 169:359–372, 2006.

15) S. Kobayashi, I. Ono, and M. Yamamura. An efficient genetic algorithm for job shop scheduling problems. In Proceedings of the 6th ICGA, pages 506–511, 1995.

16) M. Mitchell. An Introduction to Genetic Algorithms. The MIT Press, 1996.

17) F. Glover. A template for scatter search and path relinking. Lecture Notes on Computer Science, 1363:1–51, 1998.

18) M. Laguna. Scatter search. In Handbook of Applied Optimization, chapter 3.6.6, pages 183–193. Oxford University Press, 2002.

19) M. Lundy and A.Mees. Convergence of an annealing algorithm.Mathematical Programming, 34:111 – 124, 1986.

20) A. S. Manne. On the job shop scheduling problem. Operations Research, 8:219–223, 1960.

21) H. Matsuo, C. J. Suh, and R. S. Sullivan. A controlled search simulated annealing method for the general job-shop scheduling problem. Working Paper # 03-04-88, Graduate School of Business, The University of Texas, Austin, Texas, 1988.

22) D. C. Mattfeld. Evolutionary Search and the Job Shop. Physica-Verlag, 1996.

23) L. M. Rousseau and M. Gendreau. Using constraints-based operators to solve the vehicle routing problem with time windows. Journal of Heuristics, 8:43–58, 2002.

24) S. Singh and R. Sharma. A review of different approaches to the facility layout problems. International Journal of Advanced Manufacturing Technology, 30(5-6):425–433, 2006.

25) E. Taillard. Parallel taboo search techniques for the job shop scheduling problem. ORSA Journal on Computing, 6:108–117, 1994.

26) A. Udomsakdigool and V. Kachitvichyanukul.Multiple colony ant algorithm for job-shop scheduling problem. International Journal of Production Research, 46(15):4155–4175, 2008.

27) S. H. Zanakis, J. R. Evans, and A. A. Vazacopoulos. Heuristic methods and applications: A categorized survey. European Journal of Operational Research, 43:88–110, 1989.