DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click HERE
to register or log in.
Set Covering by Ordinal Cuts II: Partial Preference Functions.
Management sciences research rept.,
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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
APPROVED FOR PUBLIC RELEASE