2024 Faculty Courses School of Computing Undergraduate major in Computer Science
Fundamentals of Optimization
- Academic unit or major
- Undergraduate major in Computer Science
- Instructor(s)
- Isao Ono
- Class Format
- Lecture (Face-to-face)
- Media-enhanced courses
- -
- Day of week/Period
(Classrooms) - 7-8 Tue / 7-8 Fri
- Class
- -
- Course Code
- CSC.T342
- Number of credits
- 200
- Course offered
- 2024
- Offered quarter
- 4Q
- Syllabus updated
- Mar 14, 2025
- Language
- Japanese
Syllabus
Course overview and goals
This course focuses on models and methodologies for optimization needed for system analysis and design. The topics of this cource include the linear programming model, linear programming, the nonlinear programming model, nonlinear programming, multiobjective optimization, the integer programming model, integer programming, and conbinatorial optimization methods. The aims of this course is to enable students 1) to acquire knowledge on optimization for system analysis and design, and 2) to apply the knowledge to solve real-world problems.
Course description and aims
By the end of this course, students will be able to:
1) Explain optimization problems and formulate real-world problems as optimization problems.
2) Explain the linear/nonlinear programming problems and linear/nonlinear programming, and solve linear/nonlinear programming problems.
3) Explain multiobjective optimization, typical multiobjective optimization methods, and typical stochastic optimization methods.
4) Explain integer programming and conbinatorial optimization, and solve integer programming and conbinatorial optimization problems.
Keywords
Linear/nonlinear programming, multiobjective optimization, integer programming, combinatorial optimization
Competencies
- Specialist skills
- Intercultural skills
- Communication skills
- Critical thinking skills
- Practical and/or problem-solving skills
Class flow
Exercise problems or homework are assigned.
Course schedule/Objectives
| Course schedule | Objectives | |
|---|---|---|
| Class 1 | Introduction | Understand the background and the aim of the course. |
| Class 2 | Linear programming (1): the linear programming problem and the simplex method. | Understand the linear programming problem and the simplex method. |
| Class 3 | Linear programming (2): the two-phase method. | Understand the two-phase method. |
| Class 4 | Nonlinear programming (1): unconstrained nonlinear programming problems, optimality conditions and iterative methods. | Understand the unconstrained nonlinear programming problem, optimality conditions and typical iterative methods. |
| Class 5 | Nonlinear programming (2): global convergence and convergence rate, conjugate gradient method and quasi-Newton method. | Understand global convergence, convergence rate, conjugate gradient method and quasi-Newton method. |
| Class 6 | Nonlinear programming (3): constrained nonlinear programming problems, and optimality conditions. | Understand the constrained nonlinear programming problem, and optimality conditions. |
| Class 7 | Nonlinear programming (4): Iterative methods for constrained nonlinear programming problems | Understand typical iterative methods for constrained nonlinear programming problems. |
| Class 8 | Multiobjective optimization | Understand the multiobjective optimization problem and typical multiobjective optimization methods. |
| Class 9 | Integer programming and combinatorial optimization (1): typical problem examples and modeling techniques of integer programming | Understand typical problem examples and modeling techniques of integer programming. |
| Class 10 | Integer programming and combinatorial optimization (2): modeling techniques and problem difficulty of integer programming | Understand modeling techniques and problem difficulty of integer programming. |
| Class 11 | Integer programming and combinatorial optimization (3): combinatorial optimization problems that can be solved efficiently (1) | Understand the greedy method and the dynamic programming. |
| Class 12 | Integer programming and combinatorial optimization (4): combinatorial optimization problems that can be solved efficiently (2) | Understand the network flow. |
| Class 13 | Integer programming and combinatorial optimization (5): branch and cut method, and cutting plane method | Understand the branch and cut method, and the cutting plane method. |
| Class 14 | Integer programming and combinatorial optimization (6): approximate methods, local search methods, and metaheuristics | Understand approximate methods, local search methods, and metaheuristics. |
Study advice (preparation and review)
To enhance effective learning, students are encouraged to spend approximately 100 minutes preparing for class and another 100 minutes reviewing class content afterwards (including assignments) for each class.
They should do so by referring to textbooks and other course material.
Textbook(s)
None required. All materials used in class can be found on WEB site.
Reference books, course materials, etc.
Not Specified.
Evaluation methods and criteria
Students’ scores are based on assignment.
Related courses
- CSC.T362 ： Numerical Analysis
- CSC.T351 ： System Analysis
- CSC.T373 ： Dynamical Systems
- CSC.T374 ： Control Systems
Prerequisites
No prerequisites.