## Computer solutions to minimum-cover problems.(English)Zbl 0174.20706

Summary: A covering problem may be stated as follows:
$\text{Minimize}\ \sum_{j=1}^n c_jx_j\quad\text{subject to the constraints}$ $\sum_{j\in J_i x_j\ge 1, J_i\subseteq \{1,2,\ldots,n\}; x_j \text{integers}, 1=1,2,\ldots,m.$ An algorithm has been programmed on the IBM 7094 for solving such problems. For a given problem, it generates a set of independent “locally-optimum” solutions. If $$p$$ is the probability that any one solution is actually an optimum, then for $$n$$ independently generated solutions we have a probabiiity of $$1-(1-p)^n$$ that an optimal solution appears in the set generated. Computational experience indicates that this approach yields good results for large problems (up to $$m\cdot n \le0.5 \times 10^6)$$.

### MSC:

 65K05 Numerical mathematical programming methods 90C10 Integer programming 65Y10 Numerical algorithms for specific classes of architectures

### Keywords:

computer solutions; minimum-cover problems
Full Text: