Discrete Optimization

Academic unit or major

Graduate major in Mathematical and Computing Science

Instructor(s)

Hanna Sumita / Makoto Yamashita / Yu Yokoi

Class Format

Lecture (Face-to-face)

Media-enhanced courses

-

Day of week/Period
(Classrooms)

3-4 Mon / 3-4 Thu

Class

-

Course Code

MCS.M421

Number of credits

200

Course offered

2024

Offered quarter

2Q

Syllabus updated

Mar 14, 2025

Language

English

Syllabus

Course overview and goals

This course introduces a mathematical structure called matroids. To solve discrete optimization problems efficiently, we need to investigate structure of problems. A matroid, which is an abstraction of the notion of linear independence in vector spaces, is a fundamental structure in discrete optimization theory. This course begins with the definition and characterizations of matroids, and then shows properties of matroids and algorithms to solve discrete optimization problems with a matroid structure. The course also explains related topics and concepts such as the polyhedral aspects of matroids and submodular functions.

The aim of this course is to let students recognize that the matroid structure is essential for solving discrete optimization problem. It is often said that matroids appear in most of efficiently solvable discrete optimization problems. Knowledge on structures behind efficiently solvable problems will help you to solve your problem efficiently as much as possible.

Course description and aims

The goals of this course are the following.
1. Students explain basic properties of matroids and the importance in discrete optimization theory
2. Students recognize basic discrete optimization problems having matroid structures
3. Students explain algorithms for basic discrete optimization problems having matroid strictures

Keywords

discrete optimization, combinatorial optimization, matroid, submodular function, graph algorithm, polyhedron

Competencies

• Specialist skills
• Intercultural skills
• Communication skills
• Critical thinking skills
• Practical and/or problem-solving skills

Class flow

In each class we focus on one topic.

Course schedule/Objectives

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)

We do not assign textbooks. We will use course materials that are based on the following books.

Reference books, course materials, etc.

Alexander Schrijver: Combinatorial Optimization - Polyhedra and Efficiency, Springer, 2003.
伊理正夫，藤重 悟，大山達夫：グラフ・ネットワーク・マトロイド，産業図書，1986年．(in Japanese)

Evaluation methods and criteria

Students will be assessed by the final report. The detail is described in the first class.

Related courses

• MCS.T322 ： Combinatorial Algorithms
• MCS.T302 ： Mathematical Optimization

Prerequisites

This course is planned on the premise that students have learned Mathematical Optimization (MCS.T302) and Combinatorial Algorithms (MCS.T322), or have basic knowledge of combinatorial optimization theory.