This week’s post comes from recent conversations we’ve had around the Reed group concerning tools to quickly solve (approximately) non-linear programming problems. First, some context.
As part of a simulation model our group is building, a drinking water allocation sub-problem must be solved. Figure 1 is a simplified example of the sort of problem we are solving.
There are three utilities that each have a demand (, , and ). The utilities are connected via some infrastructure, as shown in Figure 1. When our total available water () is in excess of the demand (), no rationing is needed. When we do need to ration, we want to allocate the water to minimize the percent supply deficits across the three utilities:
The last constraint here describes the a limitation of the distribution network. The real problem is much more complicated, but we needn’t detail that here.
This problem needs to be solved thousands, or hundreds of thousands of times in each simulation, so we want any solution technique to be fast. The natural solution is linear programming (LP), which can solve problems with tens of thousands of variables and constraints nearly instantaneously.
We won’t discuss LP in great detail here, except to say that LP requires an objective and constraints that are linear with respect to the decision variables. These restrictive requirements significantly reduce the number of potential optimal solutions that must be searched. By systematically testing and pivoting between these potential optimal solutions, the popular Simplex Algorithm quickly converges to the optimal solution.
As stated in equation 1, our rationing scheme is indifferent to imposing small deficits across all three utilities, or imposing one large deficit to a single utility. For example, the objective value in equation 1 is the same, whether each utility has a deficit of 5%, or if utility 1 has a deficit of 15%, and utilities 2 and 3 have no deficit. In reality, many small deficits are likely preferable to one large one. So what are we to do?
We could square our deficits. In that case, our rationing scheme will prefer small distributed deficits over one large deficit:
BUT, we can’t use LP to solve this problem, as our objective is now non-linear! There are non-linear programming algorithms that are relatively fast, but perhaps not fast enough. Instead we could linearize our non-linear objective, as shown in Figure 2.
The strategy here is to divide a single allocation, for instance, into many decision variables, representing different ranges of the actual allocation . In each range, a linear segment approximates the actual quadratic objective function. Any actual release can be achieved by assigning the appropriate values to the new decision variables (, , and ), and the contribution to the objective function from that release can be approximated by:
If a more accurate description is needed, the range of can be divided into more segments. For our purposes just a few segments are probably sufficient. A similar strategy can be adopted for and . Of course the constraints from the original optimization problem would need to be translated into terms of the new decision variables.
Now we are adding many more decision variables and constraints, but this is unlikely to slow a modern LP algorithm too much; we are still solving a relatively simple problem. BUT, how does the LP algorithm know to increase to its maximum threshold before applying ? Do we need to add a number of conditional constraints to ensure this is done properly?
It turns out we don’t! Because our squared deficit curve in Figure 2 is monotonic and convex, we know that slope of the linear segments making up the approximation are increasing (becoming less negative). Thus, in a minimization problem, the marginal improvement in the objective is highest for the segment, followed by the segment, followed by the segment, and so on. In other words .For this reason, the algorithm will increase to its maximum threshold before assigning a non-zero value to , and so forth. No need for complicated constraints!
Now this is not always the case. If the function were not monotonic, or if it were convex for a maximization, or concave for a minimization, this would not work. But, this trick works for a surprising number of applications in water resources systems analysis!
If nothing else this simple example serves as a reminder that a little bit of thought in formulating problems can save a lot of time later!