World Library  
Flag as Inappropriate
Email this Article

Combinatorial optimization

Article Id: WHEBN0000420555
Reproduction Date:

Title: Combinatorial optimization  
Author: World Heritage Encyclopedia
Language: English
Subject: Network science, Theoretical computer science, Ellipsoid method, Mathematical optimization, Branch and price
Collection: Combinatorial Optimization, Computational Complexity Theory, Theoretical Computer Science
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Combinatorial optimization

A minimum spanning tree of a weighted planar graph. Finding a minimum spanning tree is a common problem involving 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 ("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[2] 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.

Contents

  • Applications 1
  • Methods 2
  • Specific problems 3
  • Further reading 4
  • References 5
  • External links 6

Applications

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

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 behavior 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 traveling 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

References

  1. ^ Schrijver, p. 1
  2. ^
  3. ^
  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.

External links

Lecture notes
  • Integer programming notes, J E Beasley.
Source code
  • Java Combinatorial Optimization Platform open source project.
Workshops
  • The Aussois Combinatorial Optimization Workshop
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 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)
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.