Combinatorial optimization
Encyclopedia
In applied mathematics
and theoretical computer science
, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible. It operates on the domain of those optimization problems, in which the set of feasible solutions
is discrete or can be reduced to discrete, and in which the goal is to find the best solution. Some common problems involving combinatorial optimization are the traveling salesman problem and the minimum spanning tree problem
.
Combinatorial optimization is a subset of mathematical optimization that is related to operations research
, algorithm theory
, and computational complexity theory
. It has important applications in several fields, including artificial intelligence
, machine learning
, mathematics
, auction theory
, and software engineering
.
Some research literature considers discrete optimization
to consist of integer programming
together with combinatorial optimization (which in turn is composed of optimization problem
s dealing with graphs
, matroid
s, and related structures) although all of these topics have closely intertwined research literature. It often involves determining the way to efficiently allocate resources used to find solution to mathematical problems.
. Some examples of combinatorial optimization problems that fall into this framework are shortest paths and shortest path tree
s, flows and circulations
, spanning tree
s, matching, and matroid
problems.
For NP-complete
discrete optimization problems, current research literature includes the following topics:
Combinatorial optimization problems can be viewed as searching for the best element of some set of discrete items, therefore, in principle, any sort of search algorithm
or metaheuristic
can be used to solve them. However, generic search algorithms are not guaranteed to find an optimal solution, nor are they guaranteed to run quickly (in polynomial time). (Since some discrete optimization problems are NP-complete
, such as the travelling salesman problem, this is expected unless P=NP.)
Lecture notes
Source code
Others
Applied mathematics
Applied mathematics is a branch of mathematics that concerns itself with mathematical methods that are typically used in science, engineering, business, and industry. Thus, "applied mathematics" is a mathematical science with specialized knowledge...
and theoretical computer science
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible. It operates on the domain of those optimization problems, in which the set of feasible solutions
Candidate solution
In optimization , a candidate solution is a member of a set of possible solutions to a given problem. A candidate solution does not have to be a likely or reasonable solution to the problem – it is simply in the set that satisfies all constraints.The space of all candidate solutions is called the...
is discrete or can be reduced to discrete, and in which the goal is to find the best solution. Some common problems involving combinatorial optimization are the traveling salesman problem and the minimum spanning tree problem
Minimum spanning tree
Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
.
Combinatorial optimization is a subset of mathematical optimization that is related to operations research
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
, algorithm theory
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
, and computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
. It has important applications in several fields, including artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
, machine learning
Machine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
, mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, auction theory
Auction theory
Auction theory is an applied branch of economics which deals with how people act in auction markets and researches the properties of auction markets. There are many possible designs for an auction and typical issues studied by auction theorists include the efficiency of a given auction design,...
, and software engineering
Software engineering
Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
.
Some research literature considers discrete optimization
Discrete optimization
Discrete optimization is a branch of optimization in applied mathematics and computer science.As opposed to continuous optimization, the variables used in the mathematical program are restricted to assume only discrete values, such as the integers.Two notable branches of discrete optimization...
to consist of integer programming
Integer programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming.Integer programming is NP-hard...
together with combinatorial optimization (which in turn is composed of optimization problem
Optimization problem
In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...
s dealing with graphs
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
, matroid
Matroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
s, and related structures) although all of these topics have closely intertwined research literature. It often involves determining the way to efficiently allocate resources used to find solution to mathematical problems.
Methods
There is a large amount of literature on polynomial-time algorithms for certain special classes of discrete optimization, a considerable amount of it unified by the theory of linear programmingLinear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
. Some examples of combinatorial optimization problems that fall into this framework are shortest paths and shortest path tree
Shortest path tree
A shortest path tree, in graph theory, is a subgraph of a given graph constructed so that the distance between a selected root node and all other nodes is minimal. It is a tree because if there are two paths between the root node and some vertex v A shortest path tree, in graph theory, is a...
s, flows and circulations
Flow network
In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are...
, spanning tree
Spanning tree
Spanning tree can refer to:* Spanning tree , a tree which contains every vertex of a more general graph* Spanning tree protocol, a protocol for finding spanning trees in bridged networks...
s, matching, and matroid
Matroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
problems.
For NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
discrete optimization problems, current research literature includes the following topics:
- polynomial-time exactly-solvable special cases of the problem at hand (e.g. see fixed-parameter tractable)
- algorithms that perform well on "random" instances (e.g. for TSP)
- approximation algorithmApproximation algorithmIn computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
s that run in polynomial time and find a solution that is "close" to optimal - solving real-world instances that arise in practice and do not necessarily exhibit the worst-case behaviour inherent in NP-complete problems (e.g. TSP instances with tens of thousands of nodes).
Combinatorial optimization problems can be viewed as searching for the best element of some set of discrete items, therefore, in principle, any sort of search algorithm
Search algorithm
In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
or metaheuristic
Metaheuristic
In computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the problem being optimized and can search very large spaces...
can be used to solve them. However, generic search algorithms are not guaranteed to find an optimal solution, nor are they guaranteed to run quickly (in polynomial time). (Since some discrete optimization problems are NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
, such as the travelling salesman problem, this is expected unless P=NP.)
Specific problems
- Vehicle routing problemVehicle routing problemThe vehicle routing problem is a combinatorial optimization and integer programming problem seeking to service a number of customers with a fleet of vehicles. Proposed by Dantzig and Ramser in 1959, VRP is an important problem in the fields of transportation, distribution and logistics...
- Traveling salesman problem (TSP)
- Minimum spanning treeMinimum spanning treeGiven a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
problem - Linear programmingLinear programmingLinear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
(if the solution space is the choice of which variables to make basic) - Integer programming
- Eight queens puzzleEight queens puzzleThe eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal...
(A constraint satisfaction problemConstraint satisfaction problemConstraint satisfaction problems s are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint...
. When applying standard combinatorial optimization algorithms to this problem, one would usually treat the goal function as the number of unsatisfied constraints (say number of attacks) rather than as a single boolean indicating whether the whole problem is satisfied or not.) - Knapsack problemKnapsack problemThe knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as...
- Cutting stock problemCutting stock problemThe cutting-stock problem is an optimization problem, or more specifically, an integer linear programming problem. It arises from many applications in industry. Imagine that you work in a paper mill and you have a number of rolls of paper of fixed width waiting to be cut, yet different customers...
- Assignment problemAssignment problemThe assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics...
- Weapon target assignment problemWeapon target assignment problemThe weapon target assignment problem is a class of combinatorial optimization problems present in the fields of optimization and operations research...
External links
- Alexander Schrijver. On the history of combinatorial optimization (till 1960).
Lecture notes
- Integer programming notes, J E Beasley.
Source code
- Java Combinatorial Optimization Platform open source project.
Others
- Alexander Schrijver; A Course in Combinatorial Optimization February 1, 2006 (© A. Schrijver)
- William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver; Combinatorial Optimization; John Wiley & Sons; 1 edition (November 12, 1997); ISBN 0-471-55894-X.
- Jon Lee; A First Course in Combinatorial Optimization; Cambridge University Press; 2004; ISBN 0-521-01012-8.
- Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek KarpinskiMarek KarpinskiMarek Karpinski is a computer scientist and mathematician known for his research in the theory of algorithms and their applications, combinatorial optimization, computational complexity, and mathematical foundations...
, Gerhard Woeginger, A Compendium of NP Optimization Problems. - Christos H. Papadimitriou and Kenneth SteiglitzKenneth SteiglitzDr. Kenneth "Ken" Steiglitz is a professor of computer science at Princeton University. He was born in Weehawken, New Jersey on January 30, 1939. He received his Doctor of Engineering Science from New York University in 1963. In 1997 he was inducted as a Fellow of the Association for Computing...
Combinatorial Optimization : Algorithms and Complexity; Dover Pubns; (paperback, Unabridged edition, July 1998) ISBN 0-486-40258-4. - Arnab Das and Bikas K ChakrabartiBikas K ChakrabartiBikas Kanta Chakrabarti is an Indian physicist.He is a professor of Physics at Saha Institute of Nuclear Physics, Kolkataand Visiting Professor of Economics, Indian Statistical Institute, Kolkata....
(Eds.) Quantum Annealing and Related Optimization Methods, Lecture Note in Physics, Vol. 679, Springer, Heidelberg (2005) - Journal of Combinatorial Optimization
- Arnab Das and Bikas K ChakrabartiBikas K ChakrabartiBikas Kanta Chakrabarti is an Indian physicist.He is a professor of Physics at Saha Institute of Nuclear Physics, Kolkataand Visiting Professor of Economics, Indian Statistical Institute, Kolkata....
, Rev. Mod. Phys. 80 1061 (2008)