Combinatorial optimization

Combinatorial optimization

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.[1] 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[2] considers discrete optimization to consist of integer programming together with combinatorial optimization (which in turn is composed of optimization problems dealing with graphs, matroids, 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.

Contents

Applications

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 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 behaviour inherent in NP-complete problems (e.g. TSP instances with tens of thousands of nodes[3]).

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.)

Specific problems

An optimal traveling salesperson tour through Germany’s 15 largest cities. It is the shortest among 43,589,145,600[nb 1] possible tours visiting each city exactly once.

Further reading

  • Schrijver, Alexander. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics. 24. Springer. 

External links

Lecture notes
Source code
Others

References

  1. ^ Schrijver, p. 1
  2. ^ "Discrete Optimization". Elsevier. http://www.elsevier.com/locate/disopt. Retrieved 2009-06-08. 
  3. ^ Bill Cook. "Optimal TSP Tours". http://www.tsp.gatech.edu/optimal/index.html. Retrieved 2009-06-08. 
  1. ^ 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.

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Combinatorial method — may refer to: Combinatorial method (linguistics), a method used for the study of unknown languages. For the use of combinatorial methods in mathematics, see Combinatorial principles. For the use of combinatorial methods in computer science, see… …   Wikipedia

  • 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… …   Wikipedia

  • Optimization (mathematics) — In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an… …   Wikipedia

  • optimization — /op teuh meuh zay sheuhn/ 1. the fact of optimizing; making the best of anything. 2. the condition of being optimized. 3. Math. a mathematical technique for finding a maximum or minimum value of a function of several variables subject to a set of …   Universalium

  • Combinatorial data analysis — (CDA) is the study of data sets where the arrangement of objects is important. CDA can be used either to determine how well a given combinatorial construct reflects the observed data, or to search for a suitable combinatorial construct that does… …   Wikipedia

  • Combinatorial auction — A combinatorial auction is a type of smart market in which participants can place bids on combinations of discrete items, or “packages,” rather than just individual items or continuous quantities. Simple combinatorial auctions have been used for… …   Wikipedia

  • Mathematical optimization — For other uses, see Optimization (disambiguation). The maximum of a paraboloid (red dot) In mathematics, computational science, or management science, mathematical optimization (alternatively, optimization or mathematical programming) refers to… …   Wikipedia

  • Extremal optimization — (EO) is an optimization heuristic inspired by the Bak Sneppen model of self organized criticality from the field of statistical physics. This heuristic was designed initially to address combinatorial optimization problems such as the travelling… …   Wikipedia

  • Ant colony optimization algorithms — Ant behavior was the inspiration for the metaheuristic optimization technique. In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be… …   Wikipedia

  • Ordinal optimization — In mathematical optimization, ordinal optimization is the maximization of functions taking values in a partially ordered set ( poset ). Ordinal optimization has applications in the theory of queuing networks. Contents 1 Mathematical foundations 1 …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”