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.
コメント