Monash University
monash_62874.pdf (584.08 kB)

Solving a mixed integer program by fathoming dual programs

Download (584.08 kB)
journal contribution
posted 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.


Year of first publication



Working paper series (Monash University. Department of Management).

Usage metrics


    No categories selected