2021 Faculty Courses School of Engineering Department of Industrial Engineering and Economics Graduate major in Industrial Engineering and Economics
Advanced Mathematical Programming
- Academic unit or major
- Graduate major in Industrial Engineering and Economics
- Instructor(s)
- Tomomi Matsui
- Class Format
- Lecture
- Media-enhanced courses
- -
- Day of week/Period
(Classrooms) - 7-8 Tue / 7-8 Fri
- Class
- -
- Course Code
- IEE.A432
- Number of credits
- 200
- Course offered
- 2021
- Offered quarter
- 4Q
- Syllabus updated
- Jul 10, 2025
- Language
- Japanese
Syllabus
Course overview and goals
Many of mathematical problems arising in the areas of economics and industrial engineering can be formulated as discrete optimization problems. In this lecture, we pick up integer programming problems, network programming problems, and combinatorial optimization problems. We explain the mathematical structures of the solution sets of the problems, and connection with combinatorics. We also review various algorithms for discrete optimization problems.
The objective is to let students learn skills which is necessary to solve discrete optimization problems.
Course description and aims
By the end of this course, students will be able to:
・Understand fundamental properties of discrete optimization problems.
・Understand fundamental properties of the branch and bound method.
・Understand fundamental properties of typical approximation algorithms.
・Understand fundamental properties of typical heuristics.
Keywords
discrete optimization problem, integer programming problem, combinatorial optimization problem, the branch and bound method, approximation algorithms, heuristics.
Competencies
- Specialist skills
- Intercultural skills
- Communication skills
- Critical thinking skills
- Practical and/or problem-solving skills
Class flow
In each class we give a lecture and assign some exercise problems if needed.
Course schedule/Objectives
| Course schedule | Objectives | |
|---|---|---|
| Class 1 | fundamental properties of discrete optimization problems. |
understand the contents of each class |
| Class 2 | algorithm and complexity |
|
| Class 3 | overview of linear programming and the duality theorem |
|
| Class 4 | relaxation method |
|
| Class 5 | Lagrange relaxation and subgradient method |
|
| Class 6 | enumerative method |
|
| Class 7 | linear relaxation problem |
|
| Class 8 | branch and bounds method |
|
| Class 9 | dual simplex method |
|
| Class 10 | additive lower bounds |
|
| Class 11 | approximation algorithm |
|
| Class 12 | randomized algorithm |
|
| Class 13 | heuristics |
|
| Class 14 | introduction to complexity theory |
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
Reference books, course materials, etc.
Course materials will be provided as needed.
Evaluation methods and criteria
Evaluation based on reports
Related courses
- IEE.B433 ： Advanced Topics in Mathematical Economics
Prerequisites
No prerequisites are necessary, but enrollment in related courses is desirable.