Pivot and Complement - A Heuristic for 0-1 Programming.

Abstract

The pivot and complement procedure is a heuristic for finding approximate solutions to 0-1 programming problems. It uses the fact that a 0-1 program is equivalent to the associated linear program with the added requirement that all slack variables be basic. The procedure starts by solving the linear program; then performs a sequence of pivots aimed at putting all slacks into the basis at a minimal cost in dual feasibility, while taking care of occasionally arising primal infeasibilities by complementing some nonbasic 0-1 variables; finally, it attempts to improve the 0-1 solution obtained in this way by a local search based again on complementing certain sets of 0-1 variables.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1978
Accession Number
ADA059873

Entities

People

  • Clarence H. Martin
  • Egon Balas

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic
  • Coefficients
  • Computations
  • Computer Programming
  • Computers
  • Evolutionary Algorithms
  • Integer Programming
  • Linear Programming
  • Mathematics
  • Operating Systems
  • Polynomials
  • Sequences
  • Simplex Method

Fields of Study

  • Mathematics

Readers

  • Operations Research
  • Systems Analysis and Design