Binary Integer Linear Programming: A Hybrid Implicit Enumeration Approach

Front Cover
Stanford University, 1980 - Integer programming - 200 pages
0 Reviews
This report develops a hybrid algorithm to solve the binary integer linear programming problem. This problem involves optimizing a linear objective function subject to a set of linear inequalities where, in addition, we require the variables to take on the value 0 or 1. the approach developed is that of implicit enumeration; that is, the set of all possible binary combinations of values for the variables is searched without considering each combination explicitly. This is accomplished by applying a series of tests which when satisfied allow immediate elimination of large subsets of these completions. It is in the choice of tests to be used that this algorithm may be termed a hybrid. Borrowing penalties and pseudocosts as well as binary infeasibility and conditional binary infeasibility tests from previous approaches, the algorithm is built to use each of their strengths. In addition, an existing heuristic procedure is used to generate a good feasible binary point at the outset. Thus, a good initial bound on the optimal function value is available. (Author).

From inside the book

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

CHAPTER PAGE
1
EXISTING
13
A BOUNDING TECHNIQUE FOR BILP
39

4 other sections not shown

Common terms and phrases

Bibliographic information