Set Covering by Ordinal Cuts II: Partial Preference Functions.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1973
- Accession Number
- AD0769126
Entities
People
- James H. Starr
- V. Joseph Bowman
Organizations
- Carnegie Mellon University