Parametric Integer Linear Programming: A Synthesis Of Branch And Bound With Cutting Planes

Abstract

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.

Department(s)

Computer Science

International Standard Serial Number (ISSN)

0377-2217

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2023 Elsevier, All rights reserved.

Publication Date

01 Jan 1982

Link to Full Text

Share

 
COinS