Information about Combinatorial Optimization
Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory that sits at the intersection of several fields, including artificial intelligence, mathematics and software engineering. Combinatorial optimization algorithms solve instances of problems that are believed to be hard in general, by exploring the usually-large solution space of these instances. Combinatorial optimization algorithms achieve this by reducing the effective size of the space, and by exploring the space efficiently.
A study of computational complexity theory helps to motivate combinatorial optimization. Combinatorial optimization algorithms are typically concerned with problems that are NP-hard. Such problems are not believed to be efficiently solvable in general. However, the various approximations of complexity theory suggest that some instances (e.g. "small" instances) of these problems could be efficiently solved. This is indeed the case, and such instances often have important practical ramifications.
where
NP-hard (nondeterministic polynomial-time hard), in computational complexity theory, is a class of problems informally "at least as hard as the hardest problems in NP.
..... Click the link for more information.
In mathematics, a tuple is a finite sequence (also known as an "ordered list") of objects, each of a specified type. A tuple containing n objects is known as an "n-tuple".
..... Click the link for more information.
A study of computational complexity theory helps to motivate combinatorial optimization. Combinatorial optimization algorithms are typically concerned with problems that are NP-hard. Such problems are not believed to be efficiently solvable in general. However, the various approximations of complexity theory suggest that some instances (e.g. "small" instances) of these problems could be efficiently solved. This is indeed the case, and such instances often have important practical ramifications.
Informal definition
The domain of combinatorial optimization is optimization problems where the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution.Formal definition
An instance of a combinatorial optimization problem can be described in a formal way as a tuple
where
- X is the solution space (on which f and P are defined)
- P is the feasibility predicate.
- Y is the set of feasible solutions.
- f is the objective function.
- extr is the extreme (usually min or max).
Example problems
- Vehicle routing problem
- Traveling salesman problem
- Minimum spanning tree problem
- Linear programming
- Eight queens puzzle
- Knapsack problem
Methods
Heuristic search methods (metaheuristic algorithms) as those listed below have been used to solve problems of this type.See also
A question of great interest is whether one search method is superior in performance to others across all problems. For a broad class of algorithms, the answer is no:References
- 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.
- 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)
Journals
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 allowed set.
..... Click the link for more information.
..... Click the link for more information.
Applied mathematics is a branch of mathematics that concerns itself with the mathematical techniques typically used in the application of mathematical knowledge to other domains.
..... Click the link for more information.
..... Click the link for more information.
Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems.
..... Click the link for more information.
..... Click the link for more information.
Operations Research or Operational Research (OR) is an interdisciplinary branch of mathematics which uses methods like mathematical modeling, statistics, and algorithms to arrive at optimal or good decisions in complex problems which are concerned with optimizing the maxima
..... Click the link for more information.
..... Click the link for more information.
In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will proceed through a well-defined series of successive states, eventually terminating in an
..... Click the link for more information.
..... Click the link for more information.
As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e.g.
..... Click the link for more information.
..... Click the link for more information.
artificial intelligence (or AI) is "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions which maximizes its chances of success.
..... Click the link for more information.
..... Click the link for more information.
Mathematics (colloquially, maths or math) is the body of knowledge centered on such concepts as quantity, structure, space, and change, and also the academic discipline that studies them. Benjamin Peirce called it "the science that draws necessary conclusions".
..... Click the link for more information.
..... Click the link for more information.
Software engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software.[1] The term software engineering
..... Click the link for more information.
..... Click the link for more information.
As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e.g.
..... Click the link for more information.
..... Click the link for more information.
- For a gentler introduction, see P = NP problem.
NP-hard (nondeterministic polynomial-time hard), in computational complexity theory, is a class of problems informally "at least as hard as the hardest problems in NP.
..... Click the link for more information.
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 allowed set.
..... Click the link for more information.
..... Click the link for more information.
isolated point, if there exists a neighborhood of x not containing other points of S. In particular, in a Euclidean space (or in a metric space), x is an isolated point of S, if one can find an open ball around x
..... Click the link for more information.
..... Click the link for more information.
Instantiation may be
..... Click the link for more information.
- Philosophy:
- *A concept in Platonism, see idea
- *Instantiation principle - the idea that if properties exist, the essence that "has" the properties must necessarily exist
- *
..... Click the link for more information.
For the musical term, see .
In mathematics, a tuple is a finite sequence (also known as an "ordered list") of objects, each of a specified type. A tuple containing n objects is known as an "n-tuple".
..... Click the link for more information.
In optimization (a branch of mathematics), 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.
..... Click the link for more information.
..... Click the link for more information.
predicate is either a relation or the boolean-valued function that amounts to the characteristic function or the indicator function of such a relation.
A function P: X→ is called a predicate on X. When P is a predicate on X, we sometimes say P is a property of X.
..... Click the link for more information.
A function P: X→ is called a predicate on X. When P is a predicate on X, we sometimes say P is a property of X.
..... Click the link for more information.
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 allowed set.
..... Click the link for more information.
..... Click the link for more information.
Min may refer to:
..... Click the link for more information.
- Min (god), an Egyptian fertility god.
- Min (entertainer), a South Korean artist.
- MiN, a US based hair care company.
- Menes, an early Egyptian Pharaoh.
- Minuth, in Judaism.
..... Click the link for more information.
Max, as a word or as an abbreviation, may refer to:
..... Click the link for more information.
Fictional characters
- Max (24 character), a conspiratorial terrorist from the second season of 24 and 24: The Game, portrayed by Thomas Kretschmann
- Max Tennyson, a character from Ben 10
..... Click the link for more information.
The vehicle routing problem or VRP is a combinatorial optimization problem seeking to service a number of customers with a fleet of vehicles. Often the context is that of delivering goods located at a central depot to customers who have placed orders for such goods.
..... Click the link for more information.
..... Click the link for more information.
travelling salesman problem (TSP) is a problem in discrete or combinatorial optimization. It is a prominent illustration of a class of problems in computational complexity theory which are classified as NP-hard.
..... Click the link for more information.
..... Click the link for more information.
minimum spanning tree or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree. More generally, any undirected graph has a minimum spanning forest.
..... Click the link for more information.
..... Click the link for more information.
In mathematics, linear programming (LP) problems involve the optimization of a linear objective function, subject to linear equality and inequality constraints.
Put very informally, LP is about trying to get the best outcome (e.g.
..... Click the link for more information.
Put very informally, LP is about trying to get the best outcome (e.g.
..... Click the link for more information.
eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen's moves. The colour of the queens is meaningless in this puzzle.
..... Click the link for more information.
..... Click the link for more information.
knapsack problem is a problem in combinatorial optimization. It derives its name from the maximization problem of choosing possible essentials that can fit into one bag (of maximum weight) to be carried on a trip.
..... Click the link for more information.
..... Click the link for more information.
A metaheuristic is a heuristic method for solving a very general class of computational problems by combining user given black-box procedures — usually heuristics themselves — in a hopefully efficient way.
..... Click the link for more information.
..... Click the link for more information.
Local search is a metaheuristic for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions.
..... Click the link for more information.
..... Click the link for more information.
Simulated annealing (SA) is a generic probabilistic meta-algorithm for the global optimization problem, namely locating a good approximation to the global optimum of a given function in a large search space. It was independently presented by S. Kirkpatrick, C. D. Gelatt and M. P.
..... Click the link for more information.
..... Click the link for more information.
In mathematics and applications, quantum annealing is a method for finding solutions to combinatorial optimization problems and ground states of glassy systems using quantum fluctuations.
..... Click the link for more information.
..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
