大规模整数线性规划直接搜索算法

管理，计划等人类活动中产生的大量实际问题都涉及整数线性规划问题的求解.全球化趋势更凸显大规模问题求解的重要，而现有算法在处理这类问题时常显得效不从心。.本项目力图另辟奇径，将近年来发展的线性规划算法中对偶投影搜索、最钝角原理和松弛方法，特别是非标准单纯形算法技术巧妙地整合应用，推出大规模整数线性规划的直接搜索算法。与传统算法相比, 新算法极具创新性。 它将节省求解松弛线性规划子问题所耗费的繁复计算，大大提高计算效率。 众所周知，实践中所需要的常常是问题的近似解而非精确解；新算法特别适合于这类情形的快速有效处理。

本研究项目对于混合整数线性规划问题的预处理、整数线性规划的分支定界算法、线性规划的单纯形方法快速计算、整数线性规划问题的松弛方法、整数线性规划问题遗传算法的研究取得了重要成果。特别是在线性规划的仿射尺度主元算法和组合算法、整数线性规划问题的松弛子问题的构造和计算等研究中取得了突破性的进展。