Solving a mixed integer program by fathoming dual programs

Solving a mixed integer program by fathoming dual programs

0.00 Avg rating0 Votes
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:
Keywords: programming: integer
Abstract:

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.

Reviews

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