Binary Integer Linear Programming: A Hybrid Implicit Enumeration Approach.

Abstract

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1980
Accession Number
ADA097108

Entities

People

  • Nancy Eileen Jacqmin

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Computer Programming
  • Convex Programming
  • Dynamic Programming
  • Evolutionary Algorithms
  • Heuristic Methods
  • Inequalities
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Nonlinear Programming
  • Operations Research
  • Simplex Method

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Artificial Intelligence
  • Regression Analysis.