Lattice Algorithms and Their Applications to Combinatorial Optimization

虽然整数规划问题通常被认为是困难的（NP-hard），但解决这类问题的实际需求很大。在过去的十年左右，运筹学研究人员从计算复杂性的角度来研究整数规划问题，并设计了一个多项式时间算法，用于任何固定数量的维数。该方法涉及在格上解决一个定义良好的问题，然后将结果应用于整数程序。晶格是线性无关向量的有限集合的所有整数组合的集合（向量的有限集合称为晶格的基）。这些结果表明，更好地理解格可以在解决组合优化问题方面取得重要进展。本研究将集中在格上，并有两个主要目标：为格问题设计更有效的算法，并将这些算法应用于解决整数规划和其他组合优化问题。

While integer programming problems are known to be hard (NP-hard) in general, there is a great practical need to solve such problems. In the last decade or so, operations researchers have looked at integer programming problems from a computational complexity viewpoint and a polynomial time algorithm was devised for any fixed number of dimensions. The approach involved solving a well-defined problem on lattices and then applying the result to integer programs. A lattice is the set of all integer combinations of a finite set of linearly independent vectors (the finite set of vectors is called a basis of the lattice). These results indicate that a better understanding of lattices could yield important advances in solving combinatorial optimization problems. This research will concentrate on lattices and has two main aims: to devise more efficient algorithms for lattice problems, and to apply these algorithms to solve integer programming and other combinatorial optimization problems.