Section 7.8 Discrete Optimization
Now that we have a basic model of medical need, let's think about how we can improve it. Figure 7.8.1 shows a plot of the need in each municipality (the variable \(z\) in Figure 7.7.3), with a darker color representing a higher need. Note that the three municipalities with the highest need (whose boundaries are highlighted in the figure) are not necessarily spread evenly across the county. In particular, two of the areas with highest need are Delavan city and Delavan town, and you can see that Delavan city is geographically surrounded by Delavan town. Rather than placing a clinic within both Delavan city and Delavan town, it would make more sense to serve the need in Delavan town and Delavan city with a single clinic in Delavan city. This would free OAFC up to place another clinic somewhere else in the county.
Continuing along this line of reasoning, it seems to make sense to assume that each mobile clinic will have a certain radius \(r\) of effective coverage. Areas within this radius can then be assumed to have all of their need met, or perhaps some fraction of their need met proportional to how far they are from the nearby clinic. For simplicity, let's assume that nearby municipalities will have all of their need met.
What will we mean by "nearby" municipalities? Again, we have some choice here. For simplicity, let's use the centroid of each municipality as a stand-in for where each clinic will be placed, and to measure how closeWindow() other municipalities are to it. The centroid of a 2-dimensional shape can be defined using calculus, and we won't spend time on it here. For our purposes, suffice it to say that the centroid of a shape is like a center of mass: If we were to laser-cut a piece of sheet metal in the shape of Delavan city, its centroid would be the point upon which it would balance perfectly on a finger. Figure 7.8.2 shows each municipality in the county along with its centroid.
With this additional assumption, one way to adjust our model is as follows:
As before, our goal will be to place three mobile clinics in three separate municipalities around the county. We will assume that each mobile clinic is placed at the centroid of a municipality.
As before, we will compute a value between \(0\) and \(1\) which represents the medical need within that municipality as a percentage, taking into account several strategically-chosen variables. For now, we will use the parametric linear model from the previous section.
We will choose (or allow OAFC to choose) a parameter \(r\) which represents the effective service radius of the mobile clinics. For a given choice of placement of the three clinics, we will compute the need met by adding up all need values corresponding to municipalities whose centroids fall within the service radius of one or more of the mobile clinics.
We will choose to place our clinics according to the placement which gives the greatest amount of need met.
At this point, we have a very nice example of a discrete optimization problem. In fact, this specific type of problem is known as the maximal covering location problem [7.12.1.132] [7.12.1.120].
Discrete optimization.
Discrete optimization is a broad area of study at the intersection of applied math and computer science. The goal is usually to minimize or maximize a function called an objective function. The most challenging problems in discrete optimization involve finding the maximum or minimum of the objective function among a large, but finite, set of possibilities. Often, the number of possibilities is so large that they cannot all be tested in a reasonable amount of time, and clever algorithms must be used to limit the number of possibilities to test, or to compute an approximate solution.
These days, a very popular application of discrete optimization is artificial intelligence. The problem of (approximately) minimizing or maximizing an objective function is fundamental to the success of machine learning algorithms. For example, there is a carefully-chosen objective function at the heart of language models such as ChatGPT [7.12.1.134].
Additionally, the reason that we care so much about counting the number of possibilities for the problem at hand (using permutations, combinations, etc) is that the size of the domain of the objective function (the number of possibilities to be considered) must be analyzed to estimate the amount of computing resources needed to solve the problem.
In our model, the objective function is the measure of need mentioned in the third step. The set of all \(29C3=3654\) possible clinic placements is the total number of possibilities to test. We certainly would not want to do this by hand, but a computer can do it relatively quickly. However, if there were ten times as many municipalities, or even if we were placing twice as many clinics, a clever algorithm may be needed to enable the computer to find a solution (or approximate solution) in a reasonable amount of time. Because the time taken by the computer corresponds closeWindow()ly to the number of possibilities to consider, computer scientists rely heavily on the basic counting principles in sections Section 7.5 and Section 7.6 when they come up with and analyze these algorithms.
The figure below shows a possible solution which was found by a computer, for a value of \(r=4500\) meters. When the clinics are placed at the three locations of Whitewater city, Delavan city, and Fontana-on-Geneva Lake village, this solution assumes that need is met in all municipalities whose centroids lie within \(4500\) meters of one of the mobile clinics. Those municipalities are the ones whose centroids fall inside one of the green disks. In this case, we cover the need from Delavan city, Delavan town, Fontana-on-Geneva Lake village, Walworth village, Walworth town, Whitewater city, Whitewater town, and Williams Bay village. Adding up their percentages of need from Figure 7.7.3, we see that this optimal solution covers \(\approx 45 \%\) of the need in the county. As we had hoped, this solution uses the proximity of Delavan city and Delavan town to increase the amount of need covered.
