On the Chvatal-Complexity of Binary Knapsack Problems

Bela Vizvari

Abstract:

There is a famous result of Chvatal giving a theoretical iterative

procedure, which determines the integer hull of a polyhedral set.

It starts from the polyhedral set itself and in each iteration new cuts

are introduced. This result is considered the theory of the Gomory

method of integer programming. The simplest integer programming

problem is the knapsack problem. The number of iterations in Chvatals

procedure is investigated in the case of some special binary knapsack

problems.