Pivot and Complement - A Heuristic for 0-1 Programming.
Management sciences research rept.,
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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.
- Numerical Mathematics
- Operations Research