Mean value cross decomposition applied to integer programming problems

Mean value cross decomposition applied to integer programming problems

0.00 Avg rating0 Votes
Article ID: iaor19991433
Country: Netherlands
Volume: 97
Issue: 1
Start Page Number: 124
End Page Number: 138
Publication Date: Feb 1997
Journal: European Journal of Operational Research
Authors:
Abstract:

The mean value cross decomposition method for linear programming problems is a modification of ordinary cross decomposition, that eliminates the need for using the Benders or Dantzig–Wolfe master problems. As input to the dual subproblem the average of a part of all known dual solutions of the primal subproblem is used, and as input to the primal subproblem the average of a part of all known primal solutions of the dual subproblem. In this paper we study the lower bounds on the optimal objective function value of (linear) pure integer programming problems obtainable by the application of mean value cross decomposition, and find that this approach can be used to get lower bounds ranging from the bound obtained by the LP-relaxation to the bound obtained by the Lagrangean dual. We exemplify by applying the technique to the clustering problem and give some preliminary computational results.

Reviews

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