Binary Integer Linear Programming: A Hybrid Implicit Enumeration Approach
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).
4 pages matching Petersen problems in this book
Results 1-3 of 4
What people are saying - Write a review
We haven't found any reviews in the usual places.
algorithms to solve assumption attempt to fathom Balas BILP)R binary point binary value binary variables bounding inequality bounding technique Branch and Bound branching variable change of variables Chapter column computational testing conditional binary infeasibility constraints Ax convex combination current partial solution cutting planes defined developed effective gradient eligible partial solution enumeration algorithm Enumeration Approach extreme points feasible completion feasible point feasible solution Gomory Hence heuristic procedures Hillier implicit enumeration incumbent integer linear programming Integer Programming Problem JN variables Lagrangian relaxation Lemma linear constraints linear programming problem linear programming relaxation lower bound LP relaxation maximize Mixed Integer Programming node nonbasic variable number of variables objective function value Operations Research optimal objective function optimal solution partial solutions obtained perturbed Petersen problems pseudocosts Ribiere satisfied simplex method slack variable solution to BILP solve BILP subset surrogate constraint test problems Tomlin penalties Trauth and Woolsey upper bound yield Zanakis