Article ID: | iaor20032971 |
Country: | Singapore |
Volume: | 20 |
Issue: | 1 |
Start Page Number: | 21 |
End Page Number: | 30 |
Publication Date: | May 2003 |
Journal: | Asia-Pacific Journal of Operational Research |
Authors: | Beaumont Nicholas |
Keywords: | programming: integer |
Some Mixed Integer (MIP's) have many more rows than columns. Because the time taken to solve an LP depends more on the number of rows than the number of columns, for some problems it may be computationally advantageous for the branch and bound (B&B) procedure to fathom subproblems by solving their duals. Other possible advantages are that (i) the subproblems are always feasible (but not optimal) (ii) the rows of the original problem, being stored as columns, could be more conveniently accessed and modified during solution. When compared with the ‘Primal’ B&B algorithm, the ‘Dual’ B&B algorithm (which fathoms subproblems by solving their duals) performs better on only a minority of problems; the relative performance is in fact poorly correlated with the ratio of rows to columns. It would be useful to ascertain the characteristics of problems on which the dual algorithm performs better.