Parametric Integer Linear Programming: A Synthesis Of Branch And Bound With Cutting Planes
A branch and bound algorithm is designed to solve the general integer linear programming problem with parametric right-hand sides. The right-hand sides have the form b + θd where b and d are comformable vectors, d consists of nonnegative constants, and θ varies from zero to one. The method consists of first determining all possible right-hand side integer constants and appending this set of integer constants to the initial tableau to form an expanded problem with a finite number of family members. The implicit enumeration method gives a lower bound on the integer solutions. The branch and bound method is used with fathoming tests which allow one family member possibly to fathom other family members. A cutting plane option applies a finite number of cuts to each node before branching. In addition, the cutting plane method is invoked whenever some members are feasible at a node and others are infeasible. The branching and cutting process is repeated until the entire family of problem has been solved. © 1982.
S. L. Rountree and B. E. Gillett, "Parametric Integer Linear Programming: A Synthesis Of Branch And Bound With Cutting Planes," European Journal of Operational Research, vol. 10, no. 2, pp. 183 - 189, Elsevier, Jan 1982.
The definitive version is available at https://doi.org/10.1016/0377-2217(82)90158-8
International Standard Serial Number (ISSN)
Article - Journal
© 2023 Elsevier, All rights reserved.
01 Jan 1982