Combinatorial optimization
Published:
Combinatorial optimization is a subfield of applied mathematics and theoretical computer science in which is based on find an optimal composed element from a combination of finite set of elements. In many such problems, exhaustive search is not feasible. The huge amount of possible solutions increase too fast with the size of the problem. 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.
Combinatorial optimization is a subset of mathematical optimization that is strongly related to:
- Operations research
- Algorithm theory
- Computational complexity theory
It has important applications in several fields, including:
- Artificial intelligence
- Machine learning
- Mathematics
- Auction theory
- Software engineering
- …
Typical related problems
- Assignment problem
- Closure problem
- Constraint satisfaction problem
- Cutting stock problem
- Integer programming
- Knapsack problem
- Minimum spanning tree
- Nurse scheduling problem
- Traveling salesman problem
- Vehicle routing problem
- Vehicle rescheduling problem
- Weapon target assignment problem
See also
Mathematical Optimization, Combinatorics
Material
- http://www.journals.elsevier.com/discrete-optimization
Papers
- Nemhauser, George L., and Laurence A. Wolsey. Integer programming and combinatorial optimization. Wiley, Chichester. GL Nemhauser, MWP Savelsbergh, GS Sigismondi (1992). Constraint Classification for Mixed Integer Programming Formulations. COAL Bulletin 20 (1988): 8-12.
Books
- Schrijver, Alexander (2002). Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics. 24. Springer.
- Schrijver, Alexander (February 1, 2006). A Course in Combinatorial Optimization. Notes
- Papadimitriou, C. H.; Steiglitz, K. (1982). Combinatorial optimization: algorithms and complexity. Courier Corporation.
- Lawler, E. L. (2001). Combinatorial optimization: networks and matroids. Courier Corporation.
- Steele, J. Michael (1987). Probability Theory and Combinatorial Optimization. Society for Industrial and Applied Mathematics
- Korte, Bernhard; Vygen, Jens (2012). Combinatorial Optimization: Theory and Algorithms. Springer
- Nemhauser, George L.; Wolsey, Laurence A. (1999). Integer and Combinatorial Optimization. Wiley-Interscience