Article ID: | iaor20001799 |
Country: | Portugal |
Volume: | 19 |
Issue: | 1 |
Start Page Number: | 27 |
End Page Number: | 41 |
Publication Date: | Jun 1999 |
Journal: | Investigao Operacional |
Authors: | Hultberg Tim H. |
The efficiency of solving mixed 0–1 linear programs by linear programming based branch-and-bound algorithms depends heavily on the formulation of the problem. In seeking a better formulation, automatic reformulation employs a range of different techniques for obtaining an equivalent formulation of a given pure or mixed integer programming problem, such that the new formulation has a tighter LP-relaxation than the original formulation. This paper surveys the use of automatic reformulation techniques for general mixed 0–1 linear programs.