Lattice Algorithms and Their Applications to Combinatorial Optimization

虽然整数规划问题是已知的困难（NP-难）， 总的来说，解决这些问题有很大的实际需要。 在 在过去十年左右的时间里，运筹学研究人员一直在研究整数 从计算复杂性的角度和 多项式时间算法被设计用于任何固定数量的 尺寸. 该方法涉及解决一个定义明确的问题， 格，然后将结果应用于整数规划。 的晶格 是一个有限的线性集合的所有整数组合的集合， 独立向量（向量的有限集合被称为 晶格）。 这些结果表明，更好地了解 格可以产生重要的进展，在解决组合 优化问题 这项研究将集中在晶格和 有两个主要目的：设计更有效的算法格 问题，并应用这些算法来解决整数规划 和其他组合优化问题。

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.