一、 优化程序基线性能测试背景

       求解速度是评价优化程序/软件最重要的指标之一，测试程序在基准数据集（benchmark dataset）上的表现是工业界和学界最常用的评价方法之一。虽然对算法本身的计算复杂性分析也可以用来衡量算法的求解效率，但是benchmark 数据集上的表现往往更能体现优化程序的实际效果。造成理论分析与实际表现存在差异的主要原因有：

1. 计算复杂性分析理论基于最坏情况分析（worst case analysis），即将算法在“最难”实例上的计算用时作为该算法复杂程度的度量。这些困难实例通常是为了证明算法的理论性质人为构造的，具有特殊的结构，而在实际应用中遇到的问题往往是“一般的”，通常可以快速求解。这方面最著名的例子是求解线性规划的单纯形法（simplex method），在最坏情况下单纯形法的计算复杂度是问题规模的指数函数，而在实际应用中使用单纯形法通常可以较快的求解线性规划问题。

2. 即使优化程序使用的算法具有相近的时间复杂度，甚至使用了相同的算法，不同优化程序在相同实例上的求解效率同样可能存在巨大差异。造成这种差异的原因既有编程语言、运行环境以及硬件差距等客观原因，也有算法实现方式等客观原因。例如求解TSP问题LKH[1]算法相较于其前身LK算法最大的改进在于预先生成交换组合以及更高效的算法实现，而非整体求解策略上的创新。

3. 对于NP难问题，由于目前没有多项式时间算法，在这种情况下算法的理论复杂性无法提供有关算法效率的有效的信息。算法设计者和使用者更关心的是在相同时间内算法的优度或达到特定目标值需要的时间。

二、组合优化领域经典的benchmark数据集

1. TSP 问题：http://www.math.uwaterloo.ca/tsp/data/index.html

2. OR领域问题：http://people.brunel.ac.uk/~mastjjb/jeb/info.html；https://w1.cirrelt.ca/~vidalt/en/research-data.html

3. VRP问题：https://neo.lcc.uma.es/vrp/vrp-instances/

4. Cutting&Packing问题：https://www.euro-online.org/websites/esicup/data-sets/

5. 数学规划问题：可参考http://plato.asu.edu/bench.html

[1] Helsgaun, Keld. "An effective implementation of the Lin–Kernighan traveling salesman heuristic." European Journal of Operational Research 126.1 (2000): 106-130.