组合优化

组合最优化,在应用数学和理论计算机科学的领域中,组合优化是在一个有限的对象集中找出最优对象的一类问题。[1]在很多组合优化的问题中,穷举搜索/枚举法是不可行的。组合优化的问题的特征是可行解的集是离散或者可以简化到离散的,并且目标是找到最优解。常见的例子有旅行商问题最小生成树。二维的例子,比如服装厂做衣服,衣服分成很多块,这些块需要从布料上切下来。怎么切,剩下的废布料最少?三维的例子,如集装优化

组合优化的难处,主要是加进来拓扑分析,不同的拓扑形态下,不同部分的约束关系便不同,算法也就要调整。如果给定一个拓扑形态,组合优化往往就退化成一个整数优化的问题了。

参考文献

  1. ^ Schrijver 2003,第1页.

引注

  • Cook, William J.; Cunningham, William H.; Pulleyblank, William R.; Schrijver, Alexander. Combinatorial Optimization. Wiley. 1997. ISBN 0-471-55894-X. 
  • Cook, William. Optimal TSP Tours. University of Waterloo. 2016 [2022-10-16]. (原始内容存档于2012-07-22).  (Information on the largest TSP instances solved to date.)
  • Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (编). A Compendium of NP Optimization Problems. [2022-10-16]. (原始内容存档于2007-04-05).  (This is a continuously updated catalog of approximability results for NP optimization problems.)
  • Das, Arnab; Chakrabarti, Bikas K (编). Quantum Annealing and Related Optimization Methods. Lecture Notes in Physics 679. Springer. 2005. Bibcode:2005qnro.book.....D. 
  • Lawler, Eugene. Combinatorial Optimization: Networks and Matroids. Dover. 2001. ISBN 0-486-41453-1. 
  • Papadimitriou, Christos H.; Steiglitz, Kenneth. Combinatorial Optimization : Algorithms and Complexity. Dover. July 1998. ISBN 0-486-40258-4. 
  • Sierksma, Gerard; Ghosh, Diptesh. Networks in Action; Text and Computer Exercises in Network Optimization. Springer. 2010. ISBN 978-1-4419-5512-8. 
  • Gerard Sierksma; Yori Zwols. Linear and Integer Optimization: Theory and Practice. CRC Press. 2015. ISBN 978-1-498-71016-9.