monash_62874.pdf (584.08 kB)
Solving a mixed integer program by fathoming dual programs
journal contributionposted on 2017-06-05, 06:46 authored by Beaumont, Nicholas
Some Mixed Integer Programs (MTP'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 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 algorithm, the dual algorithm 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.