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 ("TSP") and the minimum spanning tree problem ("MST").
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 problems dealing with graph structures) although all of these topics have closely intertwined research literature. It often involves determining the way to efficiently allocate resources used to find solutions to mathematical problems.
Applications for combinatorial optimization include, but are not limited to:
- Developing the best airline network of spokes and destinations
- Deciding which taxis in a fleet to route to pick up fares
- Determining the optimal way to deliver packages
- Determining the right attributes of concept elements prior to concept testing
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 programming. Some examples of combinatorial optimization problems that fall into this framework are shortest paths and shortest path trees, flows and circulations, spanning trees, matching, and matroid problems.
For NP-complete 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 algorithms 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 behavior 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 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 traveling salesman problem, this is expected unless P=NP.
- Assignment problem
- Closure problem
- Constraint satisfaction problem
- Cutting stock problem
- Integer programming
- Knapsack problem
- Linear programming
- Minimum spanning tree
- Nurse scheduling problem
- Traveling salesman problem
- Vehicle routing problem
- Vehicle rescheduling problem
- Weapon target assignment problem
Distributed Combinatorial Optimization
Distributed combinatorial optimization problems extend the scope of conventional combinatorial optimization problems to scenarios where multiple decision-makers are involved. Each decision-maker can make choices from an action set, and the global objective function is determined by the choices of all decision-makers. Each decision maker can observe the choices of other decision-makers, but not their action sets, i.e., only the selected action can be observed not the complete view. Distributed combinatorial optimization problems arise in many engineering applications where multiple decision-makers interact with limited information. The importance of distributed combinatorial optimization problems lies in the practical constraint that in many engineering applications related to large scale distributed systems such as network scheduling, centralized coordinators are not available and each node has to act as a myopic decision maker in order to make a social-optimal solution, possibly with limited message exchange. The interactive decision-making process is usually studied in a game-theoretical setting, e.g., potential game, where the optimization problem is casted in an equilibrium selection context. Equilibrium selective learning algorithms such as MaxLogit, which converges to the global optimum solution at fastest speed at its class, can be applied to solve such combinatorial optimization problems, even in a distributed fashion.
Another practical example is that in a residential area where multiple wireless access points were set up, with discrete wireless frequency channel configurable, and the objective is to reach a social-optimal, i.e., minimal mutual interference, solution by relying on distributed local decision makers (wireless access points in the example). This can be addressed in a distributed combinatorial optimization framework solved by aforementioned algorithms, where conventional centralized combinatorial optimization algorithms cannot be directly applied due to the lack of a central authority. Markovian approximation methods, e.g., MaxLogit and Metropolis–Hastings algorithm are generally preferred in practice due to the ease of implementation. An example of Markovian approximation in wireless network scheduling is presented in.
- Schrijver, Alexander. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics 24. Springer.
- Schrijver, p. 1
- "Discrete Optimization". Elsevier. Retrieved 2009-06-08.
- Cook, William. "Optimal TSP Tours". University of Waterloo. Retrieved 2009-06-08.
- MaxLogit. "Optimal gateway selection in multi-domain wireless networks: a potential game perspective". ACM MOBICOM 2011. Retrieved 7 September 2014.
- Markov_Approximation_for_Combinatorial_Network_Optimization. "Markov Approximation for Combinatorial Network Optimization". Information Theory, IEEE Transactions on , vol.59, no.10, pp.6301,6327, Oct. 2013. Retrieved 10 September 2014.
- Take one city, and take all possible orders of the other 14 cities. Then divide by two because it does not matter in which direction in time they come after each other: 14!/2 = 43,589,145,600.
||This article's use of external links may not follow Wikipedia's policies or guidelines. (April 2012)|
- Lecture notes
- Integer programming notes, J E Beasley.
- Source code
- Java Combinatorial Optimization Platform open source project.
- 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.
- Eugene Lawler (2001). Combinatorial Optimization: Networks and Matroids. Dover. ISBN 0-486-41453-1.
- 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 Karpinski, Gerhard Woeginger, A Compendium of NP Optimization Problems.
- Christos H. Papadimitriou and Kenneth Steiglitz Combinatorial Optimization : Algorithms and Complexity; Dover Pubns; (paperback, Unabridged edition, July 1998) ISBN 0-486-40258-4.
- Arnab Das and Bikas K Chakrabarti (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 Chakrabarti, Rev. Mod. Phys. 80 1061 (2008)
- El-Ghazali Talbi (Editor); Parallel Combinatorial Optimization ISBN 978-0-471-72101-7, 352 pages, October 2006
- Fabian Kuhn, Roger Wattenhofer; Distributed Combinatorial Optimization Department of Computer Science, ETH Zurich, 8092 Zurich, Switzerland
- Reza Zadeh; CourseL CME 323: Distributed Algorithms and Optimization Institute for Computational & Mathematical Engineering, Stanford University, Spring 2015.