Pivot and Complement–A Heuristic for 0-1 Programming
提出一种名为Pivot and Complement的启发式方法，用于求解0-1规划问题的近似解。该方法通过求解线性规划、将松弛变量引入基、再通过互补局部搜索改进解，在92个测试问题中49%找到最优解，平均误差在0.15%以内。
Pivot and Complement 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, other than those in the upper bounding constraints, 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; finally, it attempts to improve the 0-1 solution obtained in this way by a local search based on complementing certain sets of 0-1 variables. The computational effort involved in the procedure is bounded by a polynomial in the number of constraints and variables. For the 92 test problems with 5 to 200 constraints and 20 to 900 variables on which the procedure was run, the time used to solve the linear program on the average considerably exceeded the time used for everything else. As to the quality of the solutions obtained, in 45 cases, or 49% of the total, the procedure found an optimal solution; for the capital budgeting problems (positive coefficients everywhere), the solution found was on the average within 0.15% of the optimum; for 81 of the 92 problems, it was within 1% of the optimum; and only in 1 case did the procedure not find a feasible solution.