2024 Faculty Courses School of Engineering Department of Industrial Engineering and Economics Graduate major in Industrial Engineering and Economics
Theory and Application of Discrete Optimization
- Academic unit or major
- Graduate major in Industrial Engineering and Economics
- Instructor(s)
- Akiyoshi Shioura
- Class Format
- Lecture (Face-to-face)
- Media-enhanced courses
- -
- Day of week/Period
(Classrooms) - 3-4 Tue / 3-4 Fri
- Class
- -
- Course Code
- IEE.B433
- Number of credits
- 200
- Course offered
- 2024
- Offered quarter
- 3Q
- Syllabus updated
- Mar 14, 2025
- Language
- English
Syllabus
Course overview and goals
We discuss an auction model with many indivisible (discrete) goods. It is known that an optimal allocation of goods as well as equilibrium prices can be computed by algorithms (protocols) called iterative auctions. In this lecture, we review various iterative auctions and investigate them from the viewpoint of discrete optimization. In particular, we explain the concept of gross-substitutes valuation, which plays a crucial role in the auction, and show the connectin with discrete concavity.
This lecture aims to enable students to understand the power of theoretical results in discrete optimization in application to auction theory in economics.
Course description and aims
By the end of this course, students will be able to do the following:
(1) explain the auction model with indivisible goods,
(2) understand the concept of gross-substitutes condition and its properties,
(3) explain how iterative auctions find equilbrium prices,
(4) understand the connection between iterative auctions and optimization algorithms.
Keywords
auction, discrete optimization, equilibrium, algorithm
Competencies
- Specialist skills
- Intercultural skills
- Communication skills
- Critical thinking skills
- Practical and/or problem-solving skills
Class flow
In each class the instructor gives a lecture. At the end of the lecture, the instructor presents some problems for exercise.
Course schedule/Objectives
| Course schedule | Objectives | |
|---|---|---|
| Class 1 | overview of the lecture | Details will be given in each lecture. |
| Class 2 | System of difference constraints and shortest path problem | |
| Class 3 | Matchings in bipartite graphs | |
| Class 4 | Max-weight Matching on a bipartite graph | |
| Class 5 | optimality condition for maximum matching | |
| Class 6 | algorithm for computing an equilibrium approximately | |
| Class 7 | algorithm for computing an equilibrium approximately | |
| Class 8 | algorithm for computing an equilibrium exactly | |
| Class 9 | algorithm for computing an equilibrium exactly | |
| Class 10 | multi-demand model and equilibrium | |
| Class 11 | gross substitutes property for valuation functions | |
| Class 12 | gross substitutes property for valuation functions | |
| Class 13 | algorithm for computing an equilibrium approximately | |
| Class 14 | algorithm for computing an equilibrium exactly |
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.
Reference books, course materials, etc.
Related Book:
K. Murota: Discrete Convex Analysis, SIAM, 2003
Evaluation methods and criteria
Evaluation based on reports and exams
Related courses
- IEE.A206 ： Operations Research
- IEE.A330 ： Advanced Operations Research
Prerequisites
Knowledge about the theory of combinatorial optimization is required; we may check the knowledge by a mini exam.
In particular, students should have knowledge about the definitions, the optimality conditions, and algorithms
of the shortest path problem, the maximum (weight) matching problem, and the network flow problem.
Office hours
Any time. Prior appointment by e-mail is required.