An interior point method in Dantzig–Wolfe decomposition

An interior point method in Dantzig–Wolfe decomposition

0.00 Avg rating0 Votes
Article ID: iaor20002403
Country: United Kingdom
Volume: 26
Issue: 12
Start Page Number: 1195
End Page Number: 1216
Publication Date: Oct 1999
Journal: Computers and Operations Research
Authors: ,
Keywords: interior point methods
Abstract:

This paper studies the application of interior point methods in Dantzig–Wolfe decomposition. The main idea is to develop strategies for finding useful interior points in the dual of the restricted master problem as an alternative to finding an optimal solution or the analytic center. The method considers points on the central path between the optimal solution and the analytic center, and thus it includes the previous instances as extreme cases. For a given duality gap there exists a unique primal–dual solution on the central path. We use this solution for some choice of the duality gap. The desired duality gap is either kept fixed in all master iterations or it is updated according to some strategy. We test the method on a number of randomly generated problems of different sizes and with different numbers of subproblems. 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 have also performed some experiments with an interior point method on the subproblems. Instead of finding an optimal solution for the problems we have developed a strategy that selects a feasible solution having a reduced cost below some prescribed level. Our study focuses on comparative experiments.

Reviews

Required fields are marked *. Your email address will not be published.