Accession Number:

ADA059873

Title:

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

Descriptive Note:

Management sciences research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1978-02-01

Pagination or Media Count:

44.0

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.

Subject Categories:

  • Numerical Mathematics
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE