On the convergence of cross decomposition |
| |
Authors: | Kaj Holmberg |
| |
Institution: | (1) Department of Mathematics, Linköping Institute of Technology, S-58183 Linköping, Sweden |
| |
Abstract: | Cross decomposition is a recent method for mixed integer programming problems, exploiting simultaneously both the primal and the dual structure of the problem, thus combining the advantages of Dantzig—Wolfe decomposition and Benders decomposition. Finite convergence of the algorithm equipped with some simple convergence tests has been proved. Stronger convergence tests have been proposed, but not shown to yield finite convergence.In this paper cross decomposition is generalized and applied to linear programming problems, mixed integer programming problems and nonlinear programming problems (with and without linear parts). Using the stronger convergence tests finite exact convergence is shown in the first cases. Unbounded cases are discussed and also included in the convergence tests. The behaviour of the algorithm when parts of the constraint matrix are zero is also discussed. The cross decomposition procedure is generalized (by using generalized Benders decomposition) in order to enable the solution of nonlinear programming problems. |
| |
Keywords: | Cross decomposition convergence linear programming mixed integer programming nonlinear programming |
本文献已被 SpringerLink 等数据库收录! |
|