Accession Number:

ADA018113

Title:

A Minimax Facility Location Problem and the Cardinality Constrained Set Covering Problem.

Descriptive Note:

Technical rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1975-10-01

Pagination or Media Count:

23.0

Abstract:

Given n demand points with weights W sub i, an integer number k and a critical distance lambda, the problem discussed in the paper is one of choosing the location of k centers so that the total weight of demand points that lie within distance lambda from at least one center is maximized. This minimax location problem reduces to a cardinality constrained set covering problem CCP, and for this latter problem a hybrid tree-searchdynamic programming algorithm is given. The dynamic program plays two roles 1 it provides dominance tests to eliminate tree branchings and 2 the concavity properties associated with it can be used in a projection method to provide upper bounds for the nodes in the tree search.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE