Ray projection for optimizing polytopes with prohibitively many constraints in set-covering column generation (Q5962716)

The author develops an integer ray method to maximize large-scale linear programs. Using a ray projection approach and introducing an intersection sub-problem which can be effectively solved, the proposed method generates a number of points that tend to the optimal solution. The conditions providing a finite convergence of the integer ray method are derived. The author also introduces the dual column generation interpretation for a little more general large-scale linear program. The necessary changes in the integer ray method are introduced and a dynamic programming scheme for the corresponding intersection sub-problem is proposed. Numerical experiments on large-range instances of elastic cutting stock and capacitated arc routing problems are carried out. The given analysis of the obtained experimental results provides evidence for the practical importance of the proposed approach.