The maximal conditional covering problem

This paper formulates and solves three new problems in the location coverage literature. Two of the formulations are variations of a problem which the authors term the Maximal Conditional Covering Problem (MCCP I and II), and the third they term the Multiobjective Conditional Covering Problem (MOCCP). The MCCP and the MOCCP are extensions of the Conditional Covering Problem, and draw upon the well-studied Location Set Covering Problem and the Maximal Covering Location Problem. The MCCP problem seeks to site servers in such a way as to maximize the number of servers which are themselves covered by another server. At the same time, primary coverage by servers is provided for all demand nodes subject to a constraint on the number of servers in the system. The MOCCP problem trades off population with primary coverage against the number of servers with supporting coverage. The models are formulated as linear zero-one programs; examples are solved as relaxed linear programs with modest branching and bounding to achieve all zero-one solutions. The models have applications to a variety of location coverage systems in which supporting coverage of servers is required, including emergency medical services, fire equipment services, and police squad car coverage.