[PYTHON] Combinatorial optimization-typical problems and execution methods

Typical problems of combinatorial optimization and how to execute

Here is a list of typical problems and how to execute with Python in Combinatorial optimization. ([Let's run](# Let's run)) For a more detailed explanation, refer to the book "Combinatorial Optimization".

Typical problem class # Typical problem Complexity class Duality problem
Graph network problem 1 Minimum spanning tree problem P
2 Clique problem
( Vertex cover problem , Maximum creek problem of complement graph)
NP-hard
3 Maximum cut problem NP-hard < / tr>
4 Shortest path problem P
5 Maximum flow problem P Minimum cut problem
6 Minimum Cost Flow Problem P < / tr>
Route problem 7 Transportation route (delivery optimization) problem NP-hard
8 Traveling salesman problem NP-hard
9 Chinese postal delivery problem P
Set cover / partition problem 10 Set cover problem NP-hard 11 Partitioning problem NP-hard
12 Combination auction problem NP-hard < / tr>
Scheduling problem 13 Job shop problem NP-hard
14 Work Scheduling Problem NP Hardness < / tr>
Cutout / jamming problem 15 Knapsack problem NP-hard
16 Bin packing problem NP-hard < / tr>
17 n-dimensional jamming problem NP-hard
Placement problem less
19 No capacity constraint Facility placement problem NP-hard
Assignment / matching problem 20 Secondary allocation problem NP-hard
21 Generalization allocation problem NP-hard
22 Maximum matching problem P
23 Weight matching problem P
24 Stable matching problem (P)

--Nodes not selected in the solution of the maximum stable set problem become the solution of the vertex cover problem. ――Delivery optimization is often called XX plan like delivery plan, but XX plan is old name.

Let's run

When starting from Docker

Install Docker Toolbox, and from Kitematic, Docker image tsutomu7 / typical_optimizationPlease run the. Once done, open http: // localhost: 8888. The password for Jupyter Notebook is jupyter. For installing Docker, please also refer to Until you start Jupyter with Docker.

When installing and running locally

Please install the following software. After installation, you can run the code linked to each of the above issues.

--Installation of Python and pip: Select the target OS in the Environment Construction Guide and install it. --We recommend the latest version of 3 series. However, some libraries may not work with the latest version, in which case the older version will be more stable. --Library installation: pip install pandas matplotlib jupyter more-itertools scipy networkx ortoolpy

--ortoolpy: For typical problems. Some have minimal functionality and some are inefficient. PuLP (modeler and solver for mathematical optimization) is also installed.

--Reference: There is also a method using Anaconda, but the management of the library is different from the above method (Anaconda integrates various packages for Python and science and technology). This is the distribution that I did).

reference

-Mathematical Optimization Modeler PuLP Cheat Sheet

Recommended Posts

Combinatorial optimization-typical problems and execution methods
pytube execution and error
Class methods and static methods
Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-typical problem-n-dimensional packing problem
FizzBuzz problems here and there
Various class methods and static methods
Combinatorial optimization-Typical problem-Vertex cover problem
Combinatorial optimization-Typical problem-Stable matching problem
Combinatorial optimization-typical problem-generalized allocation problem
Combinatorial optimization-typical problem-bin packing problem
Combinatorial optimization-typical problem-maximum matching problem
Combinatorial optimization-Typical problem-Secondary allocation problem
Combinatorial optimization-typical problem-shortest path problem
Combinatorial optimization-typical problem-combinatorial auction problem
Combinatorial optimization-typical problem-maximum flow problem
Problems of liars and honesty
Combinatorial optimization-typical problem-set cover problem
Combinatorial optimization-typical problem-weight matching problem
Combinatorial optimization-Typical problem-Facility placement problem
Combinatorial optimization-typical problem-job shop problem
Combinatorial optimization-typical problem-maximum cut problem
Combinatorial optimization-typical problem-traveling salesman problem
Combinatorial optimization-typical problem-work scheduling problem