Combinatorial Optimization

Introductory problems for beginners learning combinatorial optimization.

Objective

Learn the basics and applications of mathematical optimization, especially combinatorial optimization.

Problems and How to Proceed

Preparation

Introduction

Optimization (mathematical optimization) is a broad field related to applied mathematics, dealing with methods for finding the optimal solution to a problem.

Problems where variables (such as "X" in a quadratic function or the quantity of products) take real values are classified as continuous optimization problems, while problems involving discrete values such as integers are classified as combinatorial optimization (discrete optimization) problems.

combination

Examples:

Continuous optimization problems:
- Finding the minimum/maximum of a quadratic function in high school math
- Optimization functions in machine learning (SGD, Adam, etc.)
Combinatorial optimization (discrete optimization) problems:
- Knapsack problem, Traveling Salesman Problem, etc.

Optimization materials from a university open campus

Continuous Optimization

This covers finding the minimum value (equilibrium state) of potential energy in physics, optimizing loss functions in machine learning, and similar topics. It is very mathematical.

minimize

Combinatorial Optimization

Many problems are related to real-world scenarios, such as determining which combination of materials to prepare to maximize sales.

Open campus materials

Combinatorial optimization overview

List of algorithms

Problems to Work On

Here is a selection of well-known optimization problems.

Read through the examples to understand the solution approaches.

Then, based on what you learned from the examples, try solving the problems.

Also, read through the references as supplementary material.

Continuous Optimization

Simple continuous optimization
- Example(PuLP)
- Reference: Minimizing a quartic function(Simulated annealing)
- Reference: Minimizing a circle(Particle swarm optimization)

Combinatorial Optimization

Simple combinatorial optimization (minimization problem)
- Example(Greedy algorithm)
Knapsack Problem
- Problem(Dynamic programming)
- Problem: Maximize calories at Saizeriya for 1000 yen Menu(Reference: Quantum annealing)
- Reference: A slightly more complex knapsack(Dynamic programming)
- Reference(Linear programming)
- Reference: paiza (Dynamic programming)
Traveling Salesman Problem
- Example(Dijkstra)
- Problem: Stamp Rally
  - Distance data between stores(Small number of stores)
- Problem: Plan a date course(Solve without using PuLP)
- Reference(Local search 2-opt, multi-start strategy)
- Reference: paiza(Beam search)(Dijkstra)(Greedy algorithm)
Scheduling Problem
- Example: Interval scheduling (Greedy algorithm)
- Problem: Nurse scheduling (Genetic algorithm)(You may solve it without using DEAP)
  - Reference: Simple example of genetic algorithm
  - Reference: How to use DEAP
- Reference: Job shop problem(Genetic algorithm)(Includes illustrations and code, but in Chinese -- please use Google Translate or similar)
N Queens Problem
- Example: 8 Queens (Genetic algorithm)
Four Color Problem (also featured in the movie "The Devotion of Suspect X")
- Example: Color Japanese prefectures (PuLP)(You don't need to use ortoolpy)
  - Reference: Brief explanation of ortoolpy
- Reference: Graph-theoretic approach
Matching Problem
- Example(Graph theory)
- Problem: Photo restoration
  - Reference: Kotsuki-san's code(Note: The return type of the max_weight_matching function has changed due to a networkx version upgrade)
- Reference: Explanation of bipartite matching problem
Assignment Problem
- Example(Hungarian method)
Shortest Path Problem
- Example(Dijkstra)
Set Cover Problem
- Example: Comiket(Greedy algorithm)
Maximum Flow Problem
- Example(Ford-Fulkerson)
  
  (Despite saying "queue", a stack is used, so the explanation and code are inconsistent)
Transportation Problem
- Reference: "Python Data Analysis 100 Knocks 50-70" (many missing pages)
Rectangle Packing Problem
- Reference: paiza
Comprehensive Problem Collection
- Reference: paiza Real Events

Useful Links

First Problems?

https://www.yamagata-univ-derp.org/wp-content/uploads/2019/04/%E6%9C%80%E9%81%A9%E5%8C%96%E5%95%8F%E9%A1%8C%E3%82%92Python%E3%81%A7%E8%A7%A3%E6%B1%BA%E3%81%99%E3%82%8B%EF%BC%81-1.pdf (Note: Many problems require referring to a specific textbook)