An interior point method in Dantzig-Wolfe decomposition

This paper studies the application of interior point methods in Dantzig-Wol fe decomposition. The main idea is to develop strategies for finding useful interior points in the dual of the restricted:master problem as an alterna tive to finding an optimal solution or the analytic center. The method cons iders points on the central path between the optimal solution and the analy tic center, and thus it includes the previous instances as extreme cases. F or a given duality gap there exists a unique primal-dual solution on the ce ntral path. We use this solution for some choice of the duality gap. The de sired duality gap is either kept fixed in all master iterations or it is up dated according to some strategy. We test the method On a number of randoml y generated problems of different sizes and with different numbers of subpr oblems. For most problems our method requires fewer master iterations than the classical Dantzig-Wolfe and the analytic center method. This result is especially true for problems requiring many master iterations. In addition to experiments using an interior point method on the master problems, we ha ve also performed some experiments with an interior point method on the sub problems. Instead of finding an optimal solution for the problems we have d eveloped a strategy that selects a feasible solution having a reduced cost below some prescribed level; Our study focuses on comparative experiments.