12.3 Some Practical Problems Reducible to the CLC Problem
In fact, the CLC problem, while having an independent theoretical interest, is nothing but a convenient mathematical model for presenting various practical problems arising in real-life situations. A few such situations are presented below as discrete optimization problems originating from different areas of human activity.
12.3.1 The Problem of Connected Service Areas
The CLC problem may have the following interpretation. The set of vertices of graph G is the set of clients consuming some resource or service. (Some vertices may correspond to dummy clients.) To each client v ∈ V we need to assign a unique provider (v) ∈ C from a prespecified list A(v) of admissible providers. At that, the connectivity of the service area for each provider is often required.
This problem is closely related to the optimization Plant Location Problem (PLP, or PL problem) in which, instead of a prespecified set of providers A(v), we define a cost gi,v of serving client v by provider i. Theobjectiveistofind the assignment : V→ C that minimizes the function
where gi() isthecostofusingclient i in the assignment ;it is equal to g0i if –1 (i)≠ ∅, and ...