Overview of combinatorial optimization and libraries and reference books for implementation

Machine Learning Artificial Intelligence Algorithm Digital Transformation Deep Learning Mathematics Probabilistic Generative Models Theory/Mathematics/Algorithms for AI  Navigation of this blog
What is a combinatorial optimization problem?

Combinatorial optimization theory has been applied to many real-world problems such as transportation planning, scheduling, placement, combinatorial problems, and optimization problems. The problem is to find a subset of a set consisting of a certain number of elements that satisfies a set of constraints and to find the best solution among them.

As a concrete example of combinatorial optimization theory, consider the problem of how to set up bus routes in a school in a certain area. When considering this problem, the objective of the problem is to find a bus route that is both accessible and efficient to the school under the constraints of distance and time from the school to the students’ homes, the number of children in each family, and so on.

There are various methods in combinatorial optimization theory, including dynamic programming, integer programming, graph theory, heuristic algorithms, and meta-heuristic algorithms, each of which has an optimal approach for a particular problem. We will discuss those specific methods below.

Various methods for combinatorial optimization
  • Dynamic Programming: The DP method divides a problem into smaller subproblems and solves each of them to find the optimal solution. One of the characteristics of DP is that the solutions to the subproblems are stored in tabular form and reused to reduce the amount of computation. Examples include the “knapsack problem,” in which multiple items are packed into a knapsack with a given capacity, and the “longest common subsequence problem,” in which the longest common subsequence among two or more given strings is found.
  • Integer Programming: This is a method of optimization under the constraint that the objective function takes integer values. Examples include the “0-1 knapsack problem,” in which there is only one item in the knapsack problem and only two choices of whether or not to include the item, and the “traveling salesman problem,” in which multiple cities are given and all cities are visited along the shortest possible route.
  • Graph Theory: This method uses graphs to represent problems and optimizes them using algorithms such as shortest path, minimum cut, and maximum flow. Examples include the “network flow problem” to optimize “flows” (fluid, energy, information, etc.) in a network, and the “maximum matching problem” to find the maximum subset of a graph edge set in which no two edges share endpoints (matching).
  • Heuristic algorithms (Heuristics): Heuristics do not guarantee an optimal solution, but they are a method that leads to a high-quality solution in a relatively short period of time. Typical examples include the “greedy method,” which repeatedly makes the best choice on the spot to obtain the optimal solution for a certain problem, and the “nearest neighbor search,” which seeks the optimal solution by repeatedly searching for solutions in the vicinity of a certain solution. Examples of specific combinatorial optimization problems include the “graph coloring problem,” which assigns a different color to each vertex of a given undirected graph, and the “traveling salesman problem.
  • Metaheuristics: A type of heuristic algorithm that introduces randomness, expands the search space, and leads to high-quality solutions. The “genetic algorithm problem” searches for the optimal solution by repeating the three operations of selection, crossover, and mutation, in which multiple populations of individuals are prepared and individuals with a high degree of adaptation are selected from among them to generate the next generation of individuals. The “particle swarm optimization problem,” in which the current self-optimal solution and the optimal solutions of the surrounding particles are known, and the next candidate solution is generated based on this information, are representative examples. Examples of specific combinatorial optimization problems include “multi-objective optimization problems” in which multiple objective functions are simultaneously optimized and “parameter optimization problems” in machine learning, etc.
Application of machine learning techniques to combinatorial optimization problems

In combinatorial optimization problems, deep learning techniques can be combined to solve more advanced problems. This can be done in the following ways

  • Deep Reinforcement Learning (DRL): Reinforcement learning combined with deep learning can be used to solve complex combinatorial optimization problems. This is applied, for example, to the traveling salesman problem and the problem of designing optimal road networks.
  • Deep Graph Neural Networks (DGNs): Can solve combinatorial optimization problems while taking into account the structure of the graph; DGNs can be used to derive advanced solutions for maximum cut problems, minimum spanning tree problems, etc. Deep Generative Modeling (DGN)
  • Deep Generative Models (DGM): DGM can be used to generate optimal solutions to combinatorial optimization problems. It is applied, for example, to the maximum cut problem and the graph coloring problem.
  • Deep Learning Feature Extraction: Deep learning models can be used to extract features for solving combinatorial optimization problems. In this technique, a deep learning model is used to extract features that are appropriate to the nature of the problem, and these features are then used to derive the optimal solution. This is applied, for example, to minimum cut and minimum cost flow problems.
Specific applications of combinatorial optimization problems

Combinatorial optimization problems can be applied to many real-world problems. Some examples of applications are given below.

  • Knapsack Problem: Given the value and weight of a product, the problem is to pack the product into a knapsack of limited capacity, which is applied to optimize the luggage carried by travelers.
  • Traveling Salesman Problem: Given the location of a city, the problem is to find the shortest tour route by visiting all cities exactly once each. Mathematical and heuristic algorithms are used to find the optimal route, and are applied in logistics and delivery route optimization.
  • Max Flow Problem: This is the problem of finding the optimal route that allows the maximum amount of flow to pass through a certain network. This problem is used, for example, in the design of water pipes and optimization of telecommunication networks.
  • Scheduling Problem: This is the problem of determining the optimal schedule for allocating a certain resource to multiple tasks. This problem is applied, for example, to production scheduling in manufacturing plants and optimization of employee work schedules.
  • Minimum Vertex Cover Problem: In graph theory, this is the problem of finding the minimum set of vertices such that each edge of a graph is connected to at least one vertex. This problem is applied, for example, to the optimization of information networks and the creation of optimal shopping lists.

These problems are often treated as complex combinatorial optimization problems. By applying combinatorial optimization problems, high-quality solutions can be derived.

The above methods have been implemented in various programming languages. Some of them are described below.

Library used to implement Pyhton’s combinatorial optimization problem

Libraries for solving combinatorial optimization problems in Python include

  • PuLP: A Python library for mathematical optimization that can solve combinatorial optimization problems such as linear programming problems, integer programming problems, and mixed integer programming problems.
  • Pyomo: An open-source optimization framework for solving combinatorial optimization problems, including linear, integer, nonlinear, and mixed integer programming problems.
  • CVXPY: A Python library for solving quadratic programming problems and convex optimization problems, which also supports combinatorial optimization problems.
  • DEAP: A Python library that supports the implementation of evolutionary computation algorithms and can solve combinatorial optimization problems using evolutionary computation methods such as genetic algorithms and particle swarm optimization.
Library used to implement combinatorial optimization problems in R

The main libraries for solving combinatorial optimization problems in R include

  • lpSolve: An R package for solving linear programming problems, which can also handle integer programming problems and mixed integer programming problems.
  • Rglpk: A package for using the GLPK library from R, which can also solve integer programming problems and mixed integer programming problems.
  • NMOF: A package for solving optimization problems, supporting methods such as optimization by evolutionary computation algorithms and optimization by local search methods.
  • MOSEK: A package for using the MOSEK solver from R. It can solve optimization problems such as linear programming problems, quadratic programming problems, and integer programming problems.

By using these libraries, combinatorial optimization problems can be solved in R. However, since combinatorial optimization problems are NP-hard, it is necessary to combine appropriate algorithms and heuristic methods for large-scale problems.

Library used to implement combinatorial optimization problems in C

Libraries for solving combinatorial optimization problems in C include

  • CPLEX: This is a commercial optimization solver provided by IBM that can be used from the C language. These can be used to solve optimization problems such as linear programming problems, integer programming problems, and mixed integer programming problems.
  • GLPK: GNU Linear Programming Kit, a library for solving optimization problems such as linear programming, integer programming, and mixed integer programming problems, available in C.
  • SCIP: A commercial optimization solver for large-scale optimization problems, which can be used from the C language.
  • COIN-OR: A set of libraries for solving optimization problems such as linear programming, integer programming, and mixed integer programming provided by the COIN-OR project and available in C.
Library used to implement combinatorial optimization problems in Java

The main libraries for solving combinatorial optimization problems in Java include

  • Apache Commons Math: This is a numerical library in Java provided by the Apache Software Foundation that can solve optimization problems such as linear programming problems, integer programming problems, and mixed integer programming problems.
  • JOptimizer: An optimization library implemented in Java that can solve linear programming problems, nonlinear programming problems, integer programming problems, and other optimization problems, and also supports quadratic programming problems and convex programming problems.
  • JMetal: A framework for evolutionary computation algorithms implemented in Java, which also supports multi-objective optimization and constrained optimization.
  • OptaPlanner: An optimization software framework from Red Hat that can solve optimization problems based on business rules and constraints, and uses a Java DSL to model the problem and set constraints.
Library used to implement combinatorial optimization problems in Clojure

Clojure can directly use the Java, C, and Python libraries mentioned above. Other libraries for solving combinatorial optimization problems include the following.

  • Incanter: A data analysis library implemented in Clojure that can solve optimization problems such as linear programming problems, integer programming problems, and mixed integer programming problems.
  • clj-optimization: An optimization library implemented in Clojure that can solve optimization problems such as linear programming problems, nonlinear programming problems, and quadratic programming problems.
  • Neanderthal: A matrix arithmetic library implemented in Clojure, which supports large-scale matrix computations. It can convert the constraints of linear and integer programming problems into matrix operations in order to solve combinatorial optimization problems.
    reference book (work)

    Finally, reference books are given. One of the most comprehensive reference books is Combinatorial Optimization Theory and Algorithm.

    Combinatorial Optimization  Theory and Algorithm
    	1 Introduction
    		1.1 Enumeration
    		1.2 Running Time of Algorithm
    		1.3 Linear Optimization Problems
    		1.4 Sorting
    	2 Graphs
    		2.1 Basic Definitions
    		2.2 Trees, Circuits and Cuts
    		2.3 Connectivity
    		2.4 Eulerian Bipartite and Graphs
    		2.5 Planarity
    		2.6 Planar Duality
    	3 Linear Programming Linear Programming
    		Overview
    			In mathematical programming, a method for finding the value that maximizes or minimizes a linear expression among several first-order inequalities and variable values that satisfy the first-order equality.
    			Linear programming is an optimization problem in which the objective function and constraints are all linear.
    		3.1 Polyhedra
    		3.2 The Simplex Algorithm
    			Follow the edges of the polyhedron one after another until the optimal solution is reached.
    		3.3 Implementation of the Simplex Algorithm
    		3.4 Duality
    		3.5 Convex Hulls and Polytopes
    	4 Linear Programming Algorithms
    		4.1 Size of Vertices and Faces
    		4.2 Continued Fractions
    		4.3 Gaussian Elimination
    		4.4 The Ellipsoid Method
    		4.5 Khachiyan's Theorem
    		4.6 Separation and Optimization
    	5 Integer Programming Integer Programming Problems
    		Overview
    			A linear programming problem in which each element of the solution vector x is limited to integers
    			NP-hard problems
    		5.1 The Integer Hull of Polyhedron
    		5.2 Unimodular Transformations
    		5.3 Total Dual Integrality
    		5.4 Totally Unimodular Matrices
    		5.5 Cutting Planes
    		5.6 Lagrangean Relaxation
    	6 Spanning Trees and Arborescences Totally Pointed Trees and Directed Trees
    		Overview
    			Whole point trees: Trees consisting of all vertices of a graph and only a part of the edges that make up the graph.
    			Directed Trees: Trees with only one point that is a root. Any directed graph without a closed path is called a Directed Acyclic Graph (DAG).
    		6.1 Minimun Spanning Trees
    		6.2 Minimun Weight Arborsecences
    		6.3 Polyhedral Descriptions
    		6.4 Packing Spanning Trees and Arborescences
    	7 Shortest Paths Shortest Paths Problem
    		7.1 Shortest Paths From One Source
    		7.2 Shortest Path Between All Pairs of Vertices
    		7.3 Minimun Mean Cycles
    	8 Network Flows
    		Overview
    			Flow Network: Each branch is assigned a capacity, and flows flow through each branch.
    			The flow in each branch never exceeds the capacity.
    			As a constraint, the flow into a node is always equal to the flow out of the node.
    		8.1 Max-Flow-Min-Cut Theorem
    			Max-Flow-Min-Cut Theorem
    		8.2 Menger's Theorem
    		8.3 The Edmonds-Karp Algorithm
    		8.4 Dinic's Kazanov's and Fujishige's Algorithm
    		8.5 The Goldberg-Tarjan Algorithm
    		8.6 Gomory-Hu Trees
    		8.7 The Minimum Capacity of a Cut in an Undirected Graph
    	9 Minimum Cost Flows Minimum Cost Flows Problem
    		Overview
    			Given a given amount of goods to flow on a given network, the problem of minimizing the total cost of transportation in order to minimize the total cost of flow is called the Minimum Cost Flows problem.
    		9.1 Problem Formulation
    		9.2 An Optimality Criterion
    		9.3 Minimum Mean Cycle-Cancelling Algorithm
    		9.4 Successive Shortest Path Algorithm
    		9.5 Orlin's Algorithm
    		9.6 The Network Simplex Algorithm
    		9.7 Flows Over Time
    	10 Maximum Matchings Maximum Matching Problem
    		10.1 Bipartite Matching
    		10.2 The Tuttle Matrix
    		10.3 Lute's Theorem
    		10.4 Ear-Decompositions of Factor-Critical Graphs
    		10.5 Edmond's Matching Algorithm
    	11 Weighted Matching
    		11.1 The Assignment Problem
    		11.2 Outline of the Weighted Matching Algorithm
    		11.3 Implementation of the Weighted Matching Algorithm
    		11.4 Postoptimality
    		11.5 The Matching Polytope
    	12 b-Matchings and T-Joins
    		12.1 b-Matching
    		12.2 Minimun Weight T-Joins
    		12.3 T-Joins and T-Cuts
    		12.4 The Padberg-Rao Theorem
    	13 Matroids
    		13.1 Independence Systems and Matroids
    		13.2 Other Matroid Axioms
    		13.3 Duality
    		13.4 The Greedy Algorithm
    		13.5 Matroid Intersctuon
    		13.6 Matroid Partitioning
    		13.7 Weighted Matroid Intersection
    	14 Generalized of Matroids
    		14.1 Greedoids
    		14.2 Polymatroid
    		14.3 Minimizing Submodular Functions
    		14.4 Schrijver's Algorithm
    		14.5 Symmetric Submodular Functions
    	15 NP-Completeness NP Complete Issues
    		Overview
    			NP-Completeness Problems
    		15.1 Turing Machines
    		15.2 Church's Thesis
    		15.3 P and NP
    		15.4 Cook's Theorem
    		15.5 Some Basic NP-Complete Problems
    		15.6 The Class coNP
    		15.7 NP-Hard Problems
    			Equally or more difficult than NP-Complete Problems
    			Do not necessarily belong to NP
    	16 Approximation Algorithms
    		16.1 Set Covering
    		16.2 The Max-Cut Problem
    		16.3 Colouring
    		16.4 Approximation Schemes
    		16.5 Maximum Satisfiability
    		16.6 The PCP Theorem
    		16.7 L-Reductions
    	17 The Knapsack Problem
    		Overview of the Knapsack Problem
    			Given a knapsack of capacity C and n items (each with value pi capacity ci), which item should be selected to maximize the sum of the values of the items in the knapsack by placing several items in the knapsack without exceeding the knapsack's capacity C?
    		17.1 Fractional Knapsack and Weighted Median Problem
    		17.2 A Pseudopolynomial Algorithm
    		17.3 A Fully Polynomial Approximation Scheme
    		17.4 Multi-Dimensional Knapsack
    	18 Bin-Packing Problem
    		Overview of the Bin-Packing Problem
    			Finding the minimum number of boxes (bins, containers, etc.) to pack a given package (with weight and number)
    			NP-hard problems
    		18.1 Greedy Heuristics
    		18.2 An Asymptotic Approximation Scheme
    		18.3 The Karmarkar-Karp Algorithm
    	19 Multicommodity Flows and Edge-Disjoint Paths
    		19.1 Multicommodity Flows
    		19.2 Algorithm for Multicommodity Flows
    		19.3 Sparest Cut and Max-Flow Min-Cut Ratio
    		19.4 The Leighton-Rao Theorem
    		19.5 Directed Edge-Disjoint Path Problem
    		19.7 Undirected Edge-Disjoint Path Problem
    	20 Network Design Problems
    		Overview
    			Given a network of candidate arcs with nodes and capacities, and the demand for multiple products flowing on the network, the problem is to find the arc selection and flow path for each product that minimizes the total network design cost and flow design.
    			NP-hard problem
    		20.1 Steiner Trees
    		20.2 The Robins-Zelikovsky Algorithm
    		20.3 Survivable Network Design
    		20.4 A Primal-Dual Approximation Algorithm
    		20.5 Jain's Algorithm
    	21 The Traveling Salesman Problem
    		Overview
    			Given a set of cities and a travel cost (e.g., distance) between two cities, find the travel route with the smallest total travel cost that travels to all cities exactly once and returns to the starting city.
    			NP-hard problem
    			Hamilton closed circuit problem is a special case
    			Used in delivery planning and motion planning for surface mount robots
    		21.1 Approximation Algorithms for the TSP
    		21.2 Euclidean TSP
    			A subproblem in which the distance between cities is the Euclidean distance on a plane
    		21.3 Local Search
    		21.4 The Traveling Salesman Polytope
    		21.5 Lower Bounds
    		21.6 Branch-and-Bound
    	22 Facility Location Facility Location Issues
    		Overview
    			Given a set of possible locations for a facility and a set of customers with demand, the problem is to determine the location of a facility that meets certain criteria.
    			Variations
    				Consider the number and location of facilities that can serve all customers at the lowest cost.
    					Unlimited service capacity per facility Uncapacitated Facility Location Problem (UFLP)
    					When there is a limit to the service delivery capacity per facility Capacitated Facility Location Problem (Capacitated Facility Location Problem)
    				Fix the number of facilities at p, and consider a layout that can provide service to all customers.
    					Minimize the sum of distances between customers and facilities P-median problem
    					Minimize the maximum distance between customers and facilities P-center problem
    				Consider the coverage of customers (coverage problem)
    					Find the location that covers everyone at the lowest cost Set Covering Location Problem (SCLP)
    					Expand the area that can be covered with a specific budget Maximal Covering Location Problem
    				Consider the case where a company's facilities are located in an area where others have already expanded to take market share
    					Competitive Location Models
    		22.1 The Uncapacitated Facility Location Problem
    		22.2 Rounding Linear Programming Solutions
    		22.3 Primal-Dual Algoritm
    		22.4 Scaling and Greedy Augmentations
    		22.5 Bounding the Number Facilities
    		22.6 Local Search
    		22.7 Capacitated Facility Location Problems
    		22.8 Universal Facility Location
    	memo
    		Algorithms on Discrete Structures such as Graphs and Networks
    		Proposed Polynomial-Time Algorithms
    			Based on Dynamic Programming
    			Based on the duality concept
    		Other approaches
    			Approaches based on "graph minor theory
    				Using the feature of "planar structure" in a network of "planar structures" Theoretical analysis of networks
    				VSLI and other network construction, rapid car navigation system information update
    				Planar graph
    					A graph that can be drawn on a plane without crossing each of its edges
    					Determine if a given graph is a planar graph
    						Minor operations
    							Any planar graph remains a planar graph after the addition of the following three operations (minor operations)
    								Remove an edge
    								Remove a vertex
    								Contract an edge
    

    Other reference books include “Discrete Mathematics for Beginners,” “Discrete Mathematics ‘Counting Theory’,” “Introduction to Optimization Problems: Problem Solving with Python by Combining Python Optimization, Integer Optimization, and Network Models Series” and others.

    コメント

    Exit mobile version
    タイトルとURLをコピーしました