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

Roth, R.

Oper. Res. 17, 455-465 (1969).

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