大规模的NP困难排序问题松弛策略的研究

本项目突破传统的纯组合（即离散）的研究框架，基于数学规划的松弛策略，对大规模的NP困难排序问题以及其他的组合最优化问题，从随机化算法、列生成技术、凸性及其最优性条件等三个方面进行理论研究和应用研究。这是"离散"和"连续"的相互融合，"确定"和"随机"的相互交叉，经典方法（六十年代初提出Dantzig-Wolfe分解方法）和数学规划最新理论的相互渗透。解决这些问题，必将产生许多新的思想、方法和理论，必将产生许多创新点。所有这些不但对排序论、对组合最优化理论的发展有促进作用，而且，反过来对数学规划本身的发展也有促进作用。本项目的研究属于运筹学学科的前沿研究，代表学科的发展方向；其研究方法具有可行性和前瞻性。项目的完成对推动近似算法的研究，促进组合最优化学科和数学规划学科的发展具有重要的科学意义；预期获得的研究成果有着很强的应用背景，对促进国民经济以及社会的发展具有重要的实际意义。