A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems
A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems
复制标题
DOI：
10.1287/mnsc.21.12.1417
复制
发表时间：
1975-08
影响因子：
5.4
通讯作者：
Y. Toyoda
中科院分区：
文献类型：
--
作者：
Y. Toyoda
本文旨在给出一种简单而快速的方法来求得大规模0 - 1规划问题的近似解。该方法不使用枚举。相反，它将优选度量分配给0 - 1变量，从而将变量的值从0更改为1。该方法在极短的计算时间内对0 - 1规划问题产生非常好的近似解。即使对于涉及超过一千个01变量的问题，计算时间也不太重要。该方法不仅适用于求值为1的最优变量集的问题，而且适用于各种二元选择（“是-否”）问题。
This paper is intended to present a simple and quick method for obtaining approximate solutions to large scale zero-one programming problems. The method does not use enumeration. Instead, it assigns measures of preferability to zero-one variables that change the values of the variables from zero to one. The method yields very good approximate solutions to zero-one programming problems in dramatically short computation time. Even for problems involving more than a thousand zero-one variables the computation time is of little concern. The method is applicable not only to those problems associated with obtaining the optimal package of variables with the value one but also to a great variety of binary choice ("Yes-No") problems.