Characterization and separation of the $chv\acute{a}tal$ -gomory inequalities

Abstract

In this thesis, we consider the $Chv\acute{a}tal$ -Gomory inequalities for integer programming problem. Although the $Chv\acute{a}tal$ -Gomory inequalities motivated the cutting plane approaches for combinatorial optimization problems, researches focusing on the practical aspects of the $Chv\acute{a}tal$ -Gomory inequalities seem to be limited. The goal of the research is to provide efficient separation procedures to get strong $Chv\acute{a}tal$ -Gomory inequalities for even multiple constraints. As a result, we provide several standard forms of strong rank 1 $Chv\acute{a}tal$ -Gomory inequalities and efficient separation heuristics even with complexity O(n). To begin with, we investigate the separation problem for the rank 1 $Chv\acute{a}tal$ -Gomory inequalities for the integer knapsack problem. First, we develop a dominant relation in the elementary closure for the knapsack problem. Then, we explicitly describe necessary conditions for an inequality to be a nondominated rank 1 $Chv\acute{a}tal$ -Gomory inequality for the knapsack problem, which we call maximal inequality. Independently, we show that the separation problem can be seen as a series of combinatorial optimization problems. Finally, we show that the optimal solution of the separation problem also falls into the category of the maximal inequalities. The concept of a cover naturally arises in the description of the maximal inequalities. We develop a relationship between the traditional cover inequalities and maximal inequalities. Furthermore, the relationship is expanded to the integer knapsack problem. In short, cover inequalities belong to a subclass of maximal inequalities. Next, we extend the results to the case of $Chv\acute{a}tal$ -Gomory inequalities for multiple constraints with special structure. We explicitly describe a useful condition to find the most-violated rank 1 $Chv\acute{a}tal$ -Gomory inequality for the generalized assignment problem. Then, we observe that the separation problem ...