monash_62874.pdf (584.08 kB)
Download file

Solving a mixed integer program by fathoming dual programs

Download (584.08 kB)
journal contribution
posted on 05.06.2017, 06:46 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.

History

Year of first publication

2001

Series

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

Usage metrics

Categories

Exports