A primal dual integer programming algorithm (Q1309813)

The authors intend to apply the results of theoretical investigations in practice and propose an algorithm for solving linear integer problems (LIP). The method uses a Chvatal function to verify the optimality of a feasible solution. As the authors note themselves, two steps of the algorithm include in fact the solution of two LIPs that could be as difficult as the original problem. To solve these subproblems cutting planes and Chvatal functions are applied. A problem of finding a maximum weight matching in a graph is solved as an example of the proposed algorithm.