Accession Number:

AD0769126

Title:

Set Covering by Ordinal Cuts II: Partial Preference Functions.

Descriptive Note:

Management sciences research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

• Bowman,V. Joseph
• Starr,James H.

Report Date:

1973-08-01

Pagination or Media Count:

18.0

Abstract:

The paper explores the set covering problem when the objective function is specified as an incomplete preference function. Use of real valued objective functions imposes a complete order on the solutions and therefore introduces nonexistent information when used as a surrogate for the incomplete preference function. It is shown that starting with a preference ranking of the variables and assuming additivity of preferences, one can infer a vector partial ordering representing the resulting preference relationships. The set covering problem can then be formulated as trying to find the set of undominated solutions in the sense that the elements of the set are incomparable under the preference function and each is preferred to any solution with which it is ordered. It is shown that one can easily generate elements of this set by making ordinal cuts on the partial order. The algorithm involves both enumeration and cutting planes but applied to vector orderings rather than conventional linear programs. Author

Descriptors:

• (*Linear programming
• Algorithms)
• Set theory
• Theorems
• Optimization

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE