Computer Solutions to Minimum-Cover Problems

R. Roth
Additional contact information
R. Roth: Bell Telephone Laboratories, Inc., Murray Hill, New Jersey

Operations Research, 1969, vol. 17, issue 3, 455-465

Abstract: A covering problem may be stated as follows: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$$\begin{array}{c}\mbox{Minimize}\ \sum^{j=n}_{j=1}c_{j}x_{j}\ \mbox{subject to the constraints}\\ \sum_{j\in J_{i}}x_{j}\geq 1,\quad J_i \subseteq \{1,2, \ldots, n\};\\ x_{j}\mbox{ integers},\quad i=1,2, \ldots, m.\end{array}$$\end{document} 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 prob-babiiity 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 · n ≦ 0.5 × 10 6 ).

Date: 1969
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.17.3.455 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:17:y:1969:i:3:p:455-465

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().