Research On Valid Inequalities And Cutting Planes In Integer (Mixed) Linear Programming

This thesis is for Master degree of mine, converting an intensivestudy of some theories of valid inequalities and cutting planes forinteger and mixed integer program with four chapters. Firstly itdiscuses some rules in deducing the simple valid inequalities, and theexamples in using these rules. Thus on this basis, we get all thefamous C-G cut, Gomory fractional cut, mixed integer roundingcut and Gomory mixed integer cut as well. Secondly we get a seriesof valid inequalities through changing the parameters in asupperadditive function, and also the relationship between this cutswith those as the valid inequalities which described in the first chapter.Thirdly, putting our focus on the discussion of Knapsack problem, wetalk about the cover inequalities of 0-1 knapsack and mixed 0-1knapsack problems, and also some results for the integer knapsackproblem. The lifting procedure was also discussed in this chapter.Lastly we give some introduction on branch and bounds and cuttingplane methods, and we also explain the usage of valid inequalities andcutting planes in newly branch and cut algorithm.