Research On Lattice Algorithm And Its Application In Integer Programming

This thesis dealt with the shortest vector problem(SVP),closest vector problem(CVP)and integer programming problem(IP).Kannan studied the joint algorithm of the above problems for the first time in the Algorithmic Geometry of Numbes.In Kannan's view,this research combined the classical Minkowski mathematical theory and lattice algorithm theory,which was an important subject of computer science and operations research.The main goal of this thesis is to use the latest lattice algorithm to solve integer programming problems.This thesis is based on the lattice algorithm proposed by Christoph Hun-kenschroder,Gina Reuland and Matthias Schymura in 2020(this algorithm is an improvement of MV algorithm,hereinafter referred to as HRS algorithm).Firstly,HRS algorithm under?₂ norm is extended to arbitrary convex body norm by enumeration algorithm.Secondly,the HRS algorithm under the convex norm is applied to solve the convex integer programming problem,and a better complexity than the convex integer programming algorithm proposed by DN Dadush is obtained,and its time complexity is the same as(9))⁹)but the space complexity is reduced from 2⁹)to7)(9)).Thirdly,parallel the convex integer programming algorithm in this article.Finally,the convex integer programming algorithm is applied to solve the convex mixed integer programming problem.