FUNDAMENTALS OF
OPTIMIZATION
FUNDAMENTALS OF OPTIMIZATION
Week 1: Introduction to course
3
Outline
1. Description
2. Goal and output requirement
3. References
4. Evaluation
5. Schedule
4
Description
• Optimization has many effective and widespread applications in all areas of life,
including machine learning, resource planning, machine design, automation, business
administration, finance, transportation, manufacturing, and urban architecture.
• This course provides students with a theoretical foundation in linear programming,
branch-and-bound, integer programming, constraint programming for exact algorithms;
the greedy algorithm, local search as heuristics algorithm; and some metaheuristics such
as Iterated local search, Tabu search.
5
Description
• It also provides optimization software and libraries used to develop programs for
solving these kinds of problems.
• The course provides simplified versions of real-life applications as exercises and
mini-projects.
6
Outline
1. Description
2. Goal and output requirement
3. References
4. Evaluation
5. Schedule
7
Goal and output requirements
• Modelling the simple real-life applications as combinatorial
optimizations
• Set of decision variables
• Set of constraints
• Objective function
• Demonstrate the fundamental knowledges about exact and heuristic
algorithms
• Demonstrate the background theory about optimization
• Identify, compare and categorize algorithms
• Use libraries to implement the algorithms
8
Goal and output requirements
• Apply models, algorithms and libraries for solving various real-life
problem efficiently
• Propose mathematical models for the optimization with easy to medium level
of complexity
• Analyze the business requirement of the application to select appropriately the
solution approaches for the problem at hand
• Implement algorithms for the problems within or without the libraries
• Demonstrate a serious attitude towards learning, respect for peers and
society
• Demonstrate a continuous commitment to updating knowledge in the
field of optimization
9
Outline
1. Description
2. Goal and output requirement
3. References
4. Evaluation
5. Schedule
10
References
• Slide deck provided for the course
• Nguyễn Đức Nghĩa (1996). Tối ưu hóa (Quy hoạch tuyến tính và rời rạc). NXB Giáo dục.
• George B. Dantzig and Mukund N. Thapa (1997) Linear Programming 1: Introduction,
Springer Series in Operations Research and Financial Engineering
• Bertsimas, Dimitris, and Robert Weismantel (2005) Optimization over Integers. Belmont,
MA: Dynamic Ideas.
• F. S. Hillier, G. J. Lieberman (2005) Introduction to Operations Research, eighth edition,
McGraw Hill.
• De Jong K. A (2006). Evolutionary Computation. A Unified Approach. The MIT Press.
• Glover F (1998). Tabu Search. Kluwer Acad. Publish.
11
Outline
1. Description
2. Goal and output requirement
3. References
4. Evaluation
5. Schedule
12
Evaluation
• Mid-term evaluation (40%)
• Programming contest: 20%
• Individual mini-project: 20%
• Bonus: Up to 2 points added to the mid-term grade for contributions in
lectures, such as answering questions or solving exercises on the board.
• Bonus points are added to the mid-term grade. For example, if a student scores
7 in the programming contest, 7 in the individual mini-project, and earns 2
bonus points, their mid-term grade will be 9.
• Final term (60%)
• Final exam consists of two parts: Quiz and programming contest.
13
Outline
1. Description
2. Goal and output requirement
3. References
4. Evaluation
5. Schedule
14
Tentative schedule
• Part 1: Foundation • Part 3: Heuristic approaches
• Week 1: Introduction • Week 11: Greedy algorithm
• Week 2: Convex Optimization • Week 12: Local search
• Week 3: Divide and conquer and Dynamic • Week 13: Metaheuristics
programming algorithms for optimization • Week 14: Practicing heuristic and
• Week 4&5: Introduction to Linear metaheurist with real-life problems
Programming
• Week 15: Tutoring for the individual
• Part 2: Exact approaches mini-project
• Week 6: Branch-and-Bound algorithm
• Week 16: Mini-project presentation –
• Week 7: Integer programming
Randomly selected presenter
• Week 8: Constraint programming
• Week 9: Practicing IP and CP with real-life
problems
• Week 10: Mid-term exam
15
THANK YOU !
16