0—1规划的一维搜索

The One--Dimensional Search Procedure for 0--1 Programming

本文给出了一种分离线性0—1约束的可行域和非可行域的搜索方法。用该法求解变量系数均非负的0—1规划,其收敛速度不低于一般的稳枚举法。文末给出了一个具体算例,共做16次搜索,而Balas算法则需进行37次搜索。

In this paper,we present a search procedure for determining a feasible region to the linear 0-1 constraint. In some cases, this search procedure is more efficient than the generic implicit enumeration when we solve the 0-1 programming that the coefficients in all con- straints are nonnegative. As an example to illustrate the procedure, we have solved a knap sack problem at the end by making sixteen search evaluations, whereas thirty-seven are reguired when using the Balas algorithm.