The paper presents an approximation algorithm for solving large 0-1 integer programming problems where A is 0-1 and where b is integer. The method can be viewed as a dual coordinate search for solving the LP-relaxation, reformulated as an unconstrained nonlinear problem, and an approximation scheme working together with this method. The approximation scheme works by adjusting the costs as little as possible so that the new problem has an integer solution. The degree of approximation is determined by a parameter, and for different levels of approximation the resulting algorithm can be interpreted in terms of linear programming, dynamic programming, and as a greedy algorithm. The algorithm is used in the CARMEN system for airline crew scheduling used by several major airlines, and the paper shows that the algorithm performs well for large set covering problems, in comparison to the CPLEX system, in terms of both time and quality. It also presents results on some well known difficult set covering problems that have appeared in the literature.
