Complexity of Primal Methods in Integer Programming (Extended Abstract)

One common approach to solve optimization problems is the primal method. One starts with a feasible point and then successively produces new feasible solutions with better objective function values until an optimal solution is reached. From an abstract point of view, an augmentation problem is solved in each iteration, i.e., given a feasible point find an augmenting vector, if one exists. The driving question behind most of the results in this paper on integer programming is whether the ability to efficiently solve some kind of augmentation problem already implies an integer linear programming problem to be efficiently solvable as well. We give various (partial) answers to this question