Optimization

Mathematics of Preemptive Linear Goal Programming

This section provides technical details about the mathematics in the Preemptive Linear Goal Programming solution used by RiverWare Optimization. This includes details about how constraints and objectives are applied and how they get formulated internally in the RiverWare Optimization solution. It also describes the use of priorities to handle conflicting objectives.

About Preemptive Linear Goal Programming

This section provides a conceptual overview to the Preemptive Linear Goal Programming solution used by RiverWare Optimization. It begins with brief, general descriptions of linear programming, goal programming and preemptive goal programming. These are followed by some simple examples to illustrate the use of preemptive goal programming to handle conflicting objectives and conflicting constraints.

Linear Programming

The RiverWare Optimization solver uses linear programming at its core. Linear programming is a common optimization approach where linear objective function is maximized or minimized subject to a set of linear constraints.

Maximize

Subject to:

...

where each x is a variable in the problem. Each c is a numeric coefficient in the objective function. Each a is a numeric coefficient in a constraint. Each b is the numeric right-hand-side value of each constraint. Each constraint can be either an “equal-to,” “less-than-or-equal-to,” or “greater-than-or-equal-to” constraint. The objective function and the left-hand-side of every constraint must be a linear combination of one or more variables. Additional general information about linear programming, including approaches for solving a linear program, are covered in any text on the basics of linear programming optimization and thus are not covered here.

In RiverWare, an optimization model ultimately gets formulated as a linear program. The details about that formulation are covered in following sections.

Goal Programming

One limitation of standard linear programming is that all constraints are hard constraints. If there is not a solution that can simultaneously satisfy all constraints, then the problem is infeasible. Also, there is only a single objective function.

Often in water resources contexts, a system will have multiple objectives that need to be traded off against each other. For example, there might be an objective to maximize the value of hydropower generation, but that must also be traded off with environmental objectives and an objective to carry sufficient reserve capacity. If environmental objectives are expressed as constraints (e.g. minimum and maximum flows), cases can result in which the problem becomes infeasible. For example, low inflow inputs can produce a case in which it is not possible to simultaneously satisfy minimum reservoir level constraints and minimum outflow requirements.

One approach to handle the case of conflicting objectives or conflicting constraints is goal programming. In traditional goal programming, a penalty function is applied to any deviation from a constraint value, and the penalties are minimized as part of the objective function. Typically penalty functions are convex. Most often the penalty function is linear, piecewise linear or quadratic because of the available solution mechanisms. For example, some objectives have a term that minimizes the sum of squared violations. In order to combine terms with non-commensurate units in a single objective, the deviations are typically scaled. Additionally the penalty functions and multiple objectives in the objective function might be weighted to express the relative importance of some policies over others. One challenge of this approach is that it can be difficult to interpret the meaning of the weights applied. Also the solution can be sensitive the weights that are used, and it can be difficult to anticipate the effects of modifying weights without significant trial and error.

Rather than combining weighted penalty terms and weighted objectives in a single objective function, RiverWare Optimization uses an alternative form of goal programming referred to as preemptive goal programming, which is described in the following section.

Preemptive Goal Programming

RiverWare Optimization uses a form of goal programming referred to as preemptive goal programming. Constraints and objectives are expressed at distinct priorities. At each priority an optimization problem is solved either to maximize or minimize the stated objective at that priority. If the priority contains constraints, the objective is to maximize the satisfaction of the constraints. (In RiverWare, this derived objective to maximize constraint satisfaction is automatically formulated based on the constraints that the user specifies.) Before moving on to the next priority, the objective value is frozen. This is the equivalent of adding a constraint to the problem that sets the objective function expression equal to the objective value. See “Freezing Constraints and Variables” for a detailed explanation and example of the concept of freezing. This freezing guarantees that lower priority constraints and objectives will not degrade higher priority constraints and objectives. After the higher priority solutions, there are typically many alternative optima, multiple feasible solutions that would equally maximize the objective function. Any solution for a lower priority must come from the set of alternative optima from the preceding solution. As the solution proceeds through the priorities, the solution space is reduced by the constraints added at each priority. Another way to say this is that the set of alternative optima is reduced, or degrees of freedom are removed from the problem.

The following simple example illustrates the basic concepts of preemptive goal programming, including prioritized objectives, the shrinking solution space, alternative optima and freezing of variables and constraints.

Assume we have two variables, a and b. The problem has only two dimensions. The variables are constrained by the following (hard constraints):

These constraints limit the solution space, as illustrated in Figure 2.1. In other words, they have removed degrees of freedom from the solution.

Figure 2.1

Any feasible solution must be within the orange region (including the edges that bound the region).

The problem has two prioritized objectives.

• Objective 1 (highest priority): Maximize z1 = 3a + b

• Objective 2: (lower priority): Maximize z2 = b

First, we will solve for the highest priority objective, Maximize z1 = 3a + b.

The figure above shows the direction that the objective is pushing the solution. In this case, there are many possible solutions that will equally maximize the objective. Another way to state this is that there are alternative optima. Any point that is on the line 3a + b = 30 with a between 8 and 10 (equivalently, b between 0 and 6) satisfies all constraints and equally maximizes the objective. The alternative optima are illustrated by the orange line segment in the figure above. Given the current set of constraints and objectives we have included in the problem (we have not yet added Objective 2), there is no preference for one point over another from this set of alternative optima. If we increase a, then we must decrease b, but in all cases the objective value, z1, is 30. The simplex method for solving linear programs tends to generate extreme point solutions. In this case it would generate a solution at one of the end points of the line segment.

Now as we move on to Objective 2, we will not degrade the objective value of the higher priority Objective 1. In order to guarantee that Objective 2 does not degrade Objective 1, we will only use the solutions from the set of alternative optima from Objective 1. This is done by freezing the objective value with an “equal-to” constraint:

Note: We have frozen the constraint by changing it to an “equal to” constraint.

The new constraint reduces the solution space to the orange line segment in the figure above (i.e. remove degrees of freedom).

Now we apply Objective 2: Maximize z2 = b. This is illustrated in the next figure. Once again the large arrow shows the direction that the objective is driving the solution.

In this case, the objective evaluates to a single optimal solution with the following values for all variables:

All degrees of freedom have been removed from the solution. There are no longer any alternative optima, only a single optimal solution.

Now let’s assume we have the same problem, but we reverse the priorities of the two objectives.

Objective 1 (highest priority): Maximize z1 = b

Objective 2: (lower priority): Maximize z2 = 3a + b

In this case, Objective 1 would remove all degrees of freedom, evaluating to a single optimal solution, as illustrated in Figure 2.2.

Figure 2.2

The objective value gets frozen as.

The constraint also gets frozen, changing it to an “equal to” constraint.

In addition the constraint gets frozen.

There are no alternative optima, so there are no degrees of freedom left for Objective 2 to affect the solution. The final solution is determined after Objective 1.

Soft Constraints and Derived Objectives

In RiverWare, operational policy constraints created by the user are typically added to the optimization problem as prioritized soft constraints. (Constraints defining the physical characteristics of the system are automatically added to the optimization problem by RiverWare as hard constraints; see “Physical Constraints” for details.) RiverWare automatically converts the soft constraints at each priority into a derived objective to maximize the satisfaction of the soft constraints (minimize violations). This is done to prevent an infeasible problem in the case that it is not possible to satisfy all constraints. If it is not possible to fully satisfy all constraints at a given priority, the solution will get as close as possible, rather than return an infeasible solution. The next section provides a simple example with two variables to illustrate the conceptual use of prioritized soft constraints. This is followed by a simple example from a water resources management context. See “Satisfaction Variables in Soft Constraints” for details about how soft constraints are defined. See “Derived Objectives” for details about how derived objectives are formulated.

Prevent Infeasibilities

Two-dimensional Example

To illustrate the conceptual use of prioritized soft constraints to prevent infeasibilities, assume an optimization problem with two variables, a and b. The variables have the following formal bounds.

Figure 2.3 illustrates the solution space given these bounds.

Figure 2.3

The problem has the following soft constraints and objectives in order from highest priority to lowest priority.

1. Soft Constraint:

2. Soft Constraint:

3. Soft Constraint:

4. Objective: Maximize

5. Objective: Maximize

At priority 1, adding the constraint reduces the solution space; see Figure 2.4.

Figure 2.4

At priority 2, the constraint further reduces the solution space; see Figure 2.5.

Figure 2.5

Now when we get to priority 3, we can see that the constraint cannot be satisfied without violating one of the two higher priority constraints. If the constraints were all hard constraints, the problem would be infeasible, and there would be no solution. Using soft constraints, the solution gets as close as possible to satisfying the constraint. It does this in a way that minimizes the violation of the priority 3 constraint in a manner that does not compromise the satisfaction of the two higher priority constraints; see Figure 2.6.

Figure 2.6

In this case, priority 3 removes all degrees of freedom from the solution. All of the constraints are frozen, and there is only one optimal solution.

With no degrees of freedom remaining, the two objectives can do nothing to affect the solution.

Goal Programming With Many Dimensions

In the two dimensional examples above, we saw that a soft constraint may have one of several possible effects on the solution space:

• Cut away a portion of the 2-d solution space, leaving a smaller 2-d area as the new solution space

• Limit the solution to a 1-d line segment

• Pick a 0-d solution, a single point, which is a vertex

A soft constraint could also have no effect because it does not reduce space of feasible solutions.

If we extend the goal programming solution to a problem with three variables (three dimensions), the initial solution space is represented by a 3-d polyhedron. A soft constraint may have one of several possible outcomes:

• Cut away a portion of the 3-d polyhedron, leaving a smaller 3-d polyhedron as the new solution space

• Limit the solution to a face of the polyhedron, which is a 2-d polyhedron

• Limit the solution to a 1-d line segment on the polyhedron

• Pick a 0-d solution, a single point, which is a vertex of the polyhedron

• No effect because it does not reduce the polyhedron of feasible solutions

Goal programming in higher dimensions is similar. In n dimensions, if a constraint has an effect, it may result in a smaller polyhedron with n or fewer dimensions.

Goal programs used in a water resource management context typically have many dimensions. Each physical component (e.g. Reservoir Storage, Reservoir Outflow, Reach Outflow) at each timestep is an individual variable in the problem. Additional decision variables that do not represent physical components of the system may also be included at each timestep (e.g. Energy Value). This results in a solution space represented by a polyhedron in many dimensions.

Note: RiverWare only adds the variables to the problem that are necessary based on the specified policy. See “Constraints Define Variables” and “Physical Constraints” for details. In addition, any quantities that are known inputs are included in the problem as numeric values, not as variables. For example, the Inflow to the upstream reservoir in a basin might be provided as an input. In this case, the Inflow would not be a variable. The numeric inputs would get incorporated into problem as appropriate, in mass balance constraints for example.)

Water Resource Management Example

To illustrate how goal programming applies in a water management context, consider the following simple example.

A reservoir is modeled for a single timestep with a length of one day. The initial storage of the reservoir is 50,000 acre-ft, and the inflow over the timestep is an input at 2,000 acre-ft/day. (Assume a single inflow, a single outflow and no other gains or losses.) The reservoir has the following operational policy in priority order, highest priority to lowest.

1. Minimum Storage Constraint:

2. Minimum Outflow Constraint:

3. Maximize Storage Objective: Maximize

The priority 1 constraint can be fully satisfied and guarantees that the Storage will not go below 45,000 acre-ft when solving for the later priorities.

The priority 2 constraint cannot be fully satisfied without drafting the reservoir to 42,000 acre-ft, but priority 1 already guaranteed that the reservoir would not go below 45,000 acre-ft. So priority 2 will get as close as possible to meeting the Minimum Outflow by setting the Outflow to 7,000 acre-ft/day. This will freeze both constraints as follows:

In this case there are no degrees of freedom remaining for the priority 3 objective, so it will do nothing to the solution. If the constraints at priorities 1 and 2 were added as hard constraints, the problem would be infeasible, and there would be no solution. Using soft constraints provides a solution that gets as close to the constraints as possible based on their priorities.

Now assume that the inflow over the timestep is 7,000 acre-ft/day. Both constraints could be fully satisfied, and the objective at priority 3 would result in the following solution.

In practice, optimization problems for a water management context are far more complex, spanning many timesteps, multiple objects (physical features of the basin) and many operational policy constraints and objectives. The initial solution space is a polyhedron of many dimensions. In those contexts, the general conceptual approach is the same as for this example: at each priority get as close to satisfying the constraints as is possible (maximize satisfaction) without degrading any of the higher priority constraints or objectives. However there are multiple possible approaches to maximize satisfaction. The use of soft constraints and derived objectives to maximize soft constraint satisfaction in RiverWare’s optimization solver are described in more technical detail in the following sections.

Satisfaction Variables in Soft Constraints

This section describes how satisfaction variables are introduced to formulate soft constraints. The following section describes how those satisfaction variables are included in a derived objective to maximize the soft constraint satisfaction (minimize violations).

In RiverWare, soft constraint violations, vi, are scaled from 0 to 1 where 1 corresponds to the maximum violation from a higher priority constraint or bound. For performance reasons, the RiverWare Optimization solution actually uses a formulation based on satisfaction rather than violations.

It then maximizes satisfaction, where 1 corresponds to fully satisfied, and 0 corresponds to doing no better than the previous bound.

As an example, assume a reservoir has the following high priority minimum flow constraint.

(Technically this would translate to multiple constraints, one for each timestep.) Then assume that at a lower priority a more restrictive target minimum outflow is added.

Now assume that the high priority minimum flow constraint of 1,000 cfs was fully satisfied on all time steps, but on one time step it was only possible to get an outflow 4,000 cfs due to some other high priority constraints and low inflows. The lower priority target minimum outflow would not be fully satisfied. The satisfaction, si, for that particular constraint would be 0.75. 4,000 cfs is 75% of the way from the old lower bound of 1,000 cfs to the new constraint value of 5,000 cfs.

For a greater-than-or-equal-to constraint containing only a single variable, this can be expressed as:

In the above example,

Now assume that the high priority constraint setting a minimum of 1,000 cfs did not exist, and thus the constraint using 5,000 cfs was the first constraint with this left-had-side formulation. In this case, the OldLowerBound would be taken from the Lower Bound set on the variable (slot configuration); see “Variable Bounds” for details. Assume that the slot Lower Bound was 0 cfs. Then the satisfaction would be

More generally, a soft constraint is defined as

or

where each xn is an optimization variable in the constraint. Each an is a numeric coefficient on the corresponding variable, b is the right-hand-side numeric constraint value, and OldBound is the previous limit for the right-hand-side either from a higher priority constraint of the same form (same left-hand-side) or based on the slot bounds if there is not a higher priority constraint with the same LHS.

Note: Internally, RiverWare always rearranges all constraints to have this same canonical form, with the sum of variables and their coefficients on the LHS and all constant numeric values combined in a single RHS value.

For every priority that contains soft constraints, RiverWare will add the constraints in this form, using satisfaction variables, to Optimization problem. It will then solve the Optimization problem at that priority with a derived objective to maximize the satisfaction. The derived objective that RiverWare automatically creates to maximize the value of the satisfaction variable(s) is described in the following section.

Derived Objectives

For all priorities that contain soft constraints, RiverWare automatically generates an objective to maximize the satisfaction of the soft constraints and then solves the Optimization problem at that priority to maximize the derived objective with the new soft constraints added. The manner in which satisfaction is maximized depends on which type of derived objective is selected. Each of the derived objectives are described in the following sections. See “Soft Constraint Set” for details about how to select the derived objective to use.

There are three general types of derived objectives in RiverWare: Summation, Single Maximin and Repeated Maximin. In addition Summation with Reward Table (Reward Function) is described here as a fourth type of derived objective, though technically it is implemented by adding a “With Reward Table” statement within a Summation derived objective. See “With Reward Table” for details.

Summation

The Summation derived objective includes a separate satisfaction variable in each constraint added to the Optimization problem at the current priority p. The objective is then to maximize the sum of all of the satisfaction variables added at that priority.

where there is one satisfaction variable, sp,i, for each constraint i added at the current priority p.

After maximizing the derived objective, the objective value is frozen so that the objective (satisfaction) is not degraded by lower priority objectives. Conceptually the following constraint is added to the Optimization problem

where zp is the value from maximizing the derived objective. Technically this constraint does not get included, but the equivalent of adding this constraint is carried out by freezing select constraints and variables. See “Freezing Constraints and Variables” for details about freezing constraints and variables.

The potential downside of the Summation approach is that it can tend to place all of the deviation on one or just a few constraints. For example, if a minimum flow constraint cannot be met for every timestep, it might minimize the total violation by satisfying the constraint at all but one timestep and putting a very large violation on that one timestep. Typically, this is not the preferred solution in a water resources context.

Single Maximin

The Single Maximin derived objective applies the same satisfaction variable, sp, for all constraints added at priority p. The objective is then to maximize the value of that single satisfaction variable.

Instead of minimizing the total violation, this approach will minimize the single largest violation (formally it maximizes the minimum satisfaction). This prevents a single, very large violation by spreading the violation out over multiple variables or timesteps.

Conceptually, the following constraint is added to the Optimization problem to freeze the satisfaction.

where zp is the value from maximizing the derived objective. Technically this constraint does not get included, but the equivalent of adding this constraint is carried out by freezing select constraints and variables. The solution will freeze all constraints that are limiting the satisfaction if sp is less than 1. These are the constraints with the largest violation. See “Freezing Constraints and Variables” for details about freezing constraints and variables.

The potential downside of the Single Maximin approach is that it does nothing to improve the satisfaction of the remaining constraints that are not frozen. There might be other constraints introduced at priority p that could have a higher satisfaction that the limiting constraint(s), but this approach does nothing to enforce that higher satisfaction when moving on to solve at lower priorities. It only guarantees that they will have the same satisfaction as the least satisfied constraint. This issue is addressed by the next type of derived objective, Repeated Maximin.

Repeated Maximin

The Repeated Maximin approach begins with the single maximin. A single satisfaction variable, sp,1, is applied for the first iteration for all constraints added at the current priority p, and it solves the Optimization problem with an objective to maximize the satisfaction variable (minimize the largest violation(s)). It then conceptually freezes the satisfaction variable (satisfaction of the constraint(s) with the largest violation). It also freezes all constraints that are limiting the satisfaction if sp,1 is less than 1. These are the constraints with the largest violation. (See “Freezing Constraints and Variables” for details about freezing constraints.) It then adds a new satisfaction variable, sp,2, for all remaining constraints and solves to minimize the next largest violation (technically maximize the next smallest satisfaction). It repeats this process until either all violations have been minimized (all constraints added at the current priority p have been frozen) or all remaining constraints can be fully satisfied (sp,i) equals 1.

While sp,i-1 < 1

where sp,i is a single satisfaction variable applied to all constraints added at the current priority p that have not yet been frozen prior to the ith Repeated Maximin iteration.

If it is possible to fully satisfy all constraints added at the current priority p (i.e. sp,i = 1), there will only be a single iteration. In this case there may not be any constraints frozen, dependent on whether the goal forced any constraints to their limits.

When it is not possible to fully satisfy all constraints at a given priority, the Repeated Maximin approach tends to spread out deviations as evenly as possible, which is often the desired solution in a water resources context. We recommend Repeated Maximin as the default approach for most soft constraints. It is relatively easy to change to one of the other types of derived objectives later if this is desirable.

The potential downside of the Repeated Maximin approach is that in some cases it can require numerous iterations when it is not possible to satisfy all constraints. Depending on the size of the model this can cause a significant increase run time. The Summation approach always requires only a single solution at each priority, so it tends to be faster, but it does not, in general, provide the same solution quality as Repeated Maximin. In some cases, a reasonable balance between solution quality and run time can be provided by applying the Summation with Reward Table approach as described in the next section.

Summation with Reward Table

Summation with Reward Table is a special case of the Summation derived objective. Rather than summing all satisfaction variables at a given priority equally, this approach applies a reward function to each of the satisfaction variables. Typically this approach is used to penalize larger violations more than smaller violations (greater reward for higher satisfaction). For example, a common approach is to minimize the sum of squared violations. This tends to smooth out large violations by spreading them out over multiple time steps rather than concentrating large violations on a few time steps. Applying the appropriate reward function can often produce a result that compares to the Repeated Maximin solution in terms of solution quality but has the benefit of only requiring a single solution at the given priority and can therefore be much faster.

Note: Technically, the Summation with Reward Table approach is implemented by adding a With Reward Table statement within a Summation derived objective. See “With Reward Table” for details on implementing Summation with Reward Table.

A reward table is used to apply a piecewise function to the satisfaction variables within a Summation objective. Instead of using the standard Summation derived objective for maximizing satisfaction, the derived objective becomes

where R is the reward function for the satisfaction variables.

The reward table slot has two columns. The first column contains satisfaction values. The second column contains the corresponding reward values. The values in both columns must be between 0 and 1. The reward table must be concave. (Reward must be a concave function of Satisfaction.)

Details of the general formulation of the Summation with Reward Table derived objective are given below, followed by an example that minimizes the sum of squared violations.

The following constraint is added that defines the satisfaction Sp,i of constraint i introduced at priority p as the sum of all piecewise segments.

where xp,i,j is the length () of each segment j. The number of segments is defined by the Reward Table (# segments = # rows - 1). The maximum length of each segment is constrained by the satisfaction values sp,i,j entered in the first column of the Reward Table.

The first row in the table is indexed as row 0. The slope for each segment mp,i,j is calculated as

where each rp,i,j is the value in the Reward column of the Reward Table corresponding to the satisfaction sp,i,j.

The objective maximizes the total reward Rp, which is defined as follows.

An example is provided below for a reward table that corresponds to minimizing the sum of squared violations

Example 2.1 Example Reward Table: Minimize the Sum of Squared Violations

Conceptually the desired derived objective is to minimize the sum of squared violations of all constraints introduced at the current priority p.

where vp,i is the violation of constraint i introduced at the current priority p. Violations are scaled from 0 to 1, where 1 corresponds to the maximum violation based on a higher priority constraint or variable bound. Thus an equivalent objective to minimize the sum of squared violations is

For performance reasons, the RiverWare Optimization solution maximizes satisfaction variables rather than minimizing violations. See “Satisfaction Variables in Soft Constraints” for details about how the satisfaction variables are defined.

The maximize objective then becomes

Table 2.1 shows how this can be approximated by a piecewise linear function that linearizes the function in 10 discrete segments.

vi | vi2 | si | 1 - vi2 |
---|---|---|---|

1.0 | 1.00 | 0.0 | 0.00 |

0.9 | 0.81 | 0.1 | 0.19 |

0.8 | 0.64 | 0.2 | 0.36 |

0.7 | 0.49 | 0.3 | 0.51 |

0.6 | 0.36 | 0.4 | 0.64 |

0.5 | 0.25 | 0.5 | 0.75 |

0.4 | 0.16 | 0.6 | 0.84 |

0.3 | 0.09 | 0.7 | 0.91 |

0.2 | 0.04 | 0.8 | 0.96 |

0.1 | 0.01 | 0.9 | 0.99 |

0.0 | 0.00 | 1.0 | 1.00 |

The reward table entered in RiverWare is taken from the last two columns, as shown in Figure 2.7 and Figure 2.8.

Figure 2.7

Figure 2.8

More generally, any concave table may be used. For example, a table can be created for minimizing cubed violations. Tables with more rows may degrade performance (increase run time) and numerical stability. There is a tendency for optimal solutions to be at the discrete values in the table. This may be more noticeable when tables with fewer rows (larger segments) are used. For example, if the reward table only had three rows corresponding to satisfaction values of 0, 0.5 and 1, it might be common to see the solution at a satisfaction of either 0.5 or 1.0. Some experimentation may be required to determine the best table size for a given goal.

Freezing Constraints and Variables

After solving at each priority, the RiverWare Optimization solution guarantees that later priorities will not degrade the objective from the current priority by locking in or freezing portions of the solution. See “Preemptive Goal Programming” for conceptual examples of this. For numeric stability reasons, RiverWare does not technically freeze the objective function itself but rather freezes constraints and variables. These are constraints that are forced to their limits by the objective and variables that are forced to their upper or lower bounds. Freezing the appropriate constraints and variables guarantees that the objective will not be degraded by lower priorities. Violations of soft constraints always results in freezing that removes degrees of freedom from the solution. If there are no violations, freezing usually reduces the size of the feasible polyhedron without removing degrees of freedom.This section provides details about the freezing of constraints and variables.

Information about frozen constraints and objectives is helpful in Optimization solution analysis. Constraints that get frozen at the priority that they are introduced, which are typically soft constraints that cannot be fully satisfied, are constraints that are driving the solution at that priority. Constraints that were introduced at an earlier priority and get frozen at a lower priority are limiting the objective function at the lower priority. In the case of unsatisfied soft constraints at a given priority, the frozen constraints that were introduced at an earlier priority are preventing the constraints from being fully satisfied. See “Priority-oriented Optimization Solution Analysis Tool” for details about frozen constraint information in the Optimization Solution Analysis Tool.

Freezing always occurs automatically after each iteration of a Repeated Maximin derived objective. This is necessary given the nature of the solution. A second Repeated Maximin iteration at a given priority only makes sense when constraints and variables are frozen after the first iteration. Otherwise it would simply be re-solving the same problem over and over. For all other objective types (Maximize, Minimize, Summation, Single Maximin), an explicit Freeze statement must be added to the goal after the objective statement. See “Freeze” for details about how to apply a Freeze statement to goals. A common mistake is forgetting to add the Freeze statement after these objectives. If the Freeze statement is omitted, the solution will look the same as if the goal was never included in the optimization policy. The reason for this design is to retain the ability to have test objectives that provide information for a subsequent goal without using it to freeze the solution. This approach is not common, but when needed, it is very useful.

Freezing Constraints

Assume that at priority 1 a reservoir has a Minimum Storage constraint for every timestep.

At priority 2, the reservoir has a Minimum Outflow constraint.

Assume that, given the initial Storage and Inflow over the first three timesteps (t1, t2, t3), it is not possible to meet both the Minimum Outflow and the Minimum Storage. The Minimum Storage is at a higher priority, so the solution would satisfy those constraints, and it would get the Outflow as close to the Minimum of 5,000 cfs as possible. In doing so, it would take the Storage down to the minimum by the third timestep. Using as much water as is available from the reservoir is the means by which it would get as close to the Minimum Outflow as possible. In other words, the Minimum Outflow constraint at priority 2 forces the Minimum Storage from priority 1 to be tight on t3, and the Minimum Storage constraint on t3 is limiting the objective for priority 2.

For all priorities below priority 2, we already know that the Storage at t3 must be at the Minimum Storage in order to prevent degrading the priority 2 objective to maximize the satisfaction of the Minimum Outflow constraint. So RiverWare freezes the Minimum Storage constraint on t3 by changing it to an “equal-to” constraint.

This would remove a degree of freedom from the solution for all subsequent priorities. The Storage on t1 and t2 is still constrained to be greater-than-or-equal-to 10,000 acre-ft, but at this point they have not been forced to be equal to 10,000 acre-ft, so they are not frozen here.

Technically, the constraint would be frozen in its canonical form including the satisfaction variable; see “Satisfaction Variables in Soft Constraints” for details. Assume that the initial lower bound on Reservoir Storage before priority 1 was 0 acre-ft, then this would look like the following:

where 1.0 is the coefficient on the Reservoir Storage variable, s1 is the satisfaction variable from priority 1, which would have been frozen at a value of 1.0 when solving at priority 1, and 0 acre-ft was the previous bound on Reservoir Storage.

Note: Technically, all evaluation is done internally in RiverWare Optimization units, which are typically scaled SI units, not in user display units as shown here.

The Minimum Outflow constraints would also get frozen at priority 2 but with a satisfaction variable value less than 1. Assume that the previous bound on Outflow was 0 cfs, and the priority 2 solution was only able to get the outflow to 4,000 cfs on all three timesteps. The satisfaction would be 0.8 (80% from the old bound of 0 cfs to the new constraint value of 5,000 cfs). The Minimum Outflow constraint would be frozen as follows:

where s2 is the satisfaction variable for priority 2 and will be frozen at a value of 0.8. The Minimum Outflow constraints at t2 and t3 would be frozen in a similar manner.

RiverWare determines which constraints to freeze by evaluating the dual price for each constraint. The dual price represents the unit improvement in the objective function that would result from a unit change in the constraint right-hand-side value while holding all else constant. If a constraint’s dual price is greater than 0, it is an indication that the constraint is limiting the objective (i.e. the constraint is binding) so that constraint gets frozen. For example, assume that reducing the Minimum Storage limit on t3 from 10,000 acre-ft to 9,999 acre-ft would allow an Outflow of 4,000.2 cfs on all three timesteps. This would improve the objective value from 80% to 80.004%. The dual price of the Minimum Storage constraint on t3 would be 0.004%/acre-ft. This is greater than zero, so the Minimum Storage constraint on t3 gets frozen. If the Minimum Storage value on t1 or t2 were relaxed, the objective would still be limited by the Minimum Storage on t3. The the objective value would not be improved by changing the t1 or t2 constraint value. Thus the dual price for these constraints is zero, and the constraints do not get frozen. Internally this evaluation is always carried out in RiverWare Optimization units, and the dual price must actually be greater than a freezing tolerance of 10-6 in RiverWare Optimization units in order to freeze the constraint.

When looking at the Optimization Solution Analysis Tool for priority 2, you would see the Minimum Outflow constraints as constraints from the current priority that were frozen. See “Priority-oriented Optimization Solution Analysis Tool” for details. These constraints were driving the solution at priority 2. You would also see the Minimum Storage constraint from t3 as a constraint that was introduced earlier that was frozen at priority 2, indicating that it limited the satisfaction of the priority 2 Minimum Outflow constraints.

Freezing Variables

Variables that are binding on the solution get frozen as well. This occurs when variables are forced to their upper or lower bound by the objective. (For variables that correspond to slots, the upper and lower bounds are set in their slot configuration by the user. See “Variable Bounds” for information about setting the required bounds on variables. For variables that are added to the problem automatically by RiverWare and do not correspond to slots, RiverWare sets the bounds automatically. One example of the latter is the satisfaction variable for a soft constraint.)

For example, Regulated Spill typically has a lower bound of zero. Assume that there are no policy constraints that require Regulated Spill to be greater-than-or-equal-to a non-zero value. An objective to maximize Power generation will often drive Regulated Spill to zero in order to use as much water as possible for generation. The variable will get frozen at its lower bound of zero.

Another common case in which variables are frozen is the freezing of satisfaction variables for soft constraints. Satisfaction variables automatically have upper and lower bounds of 0 and 1. For example, assume that the goal at priority i contains a Repeated Maximin derived objective. RiverWare will add a new satisfaction variable, si, to the problem.

If the solution is able to fully satisfy all of the constraints in goal i, then it will freeze the satisfaction constraint at its upper bound of 1.

Similar to the use of dual prices for freezing constraints, reduced costs are used in the freezing of variables. RiverWare freezes all variables with a reduced cost greater than zero. The reduced cost represents the unit decrease in the objective value for a unit change in the bound on the variable (unit increase for a lower bound or unit decrease for an upper bound). In the Regulated Spill example, increasing the lower bound on Regulated Spill to be greater than zero would decrease the amount of power that could be generated. Some water would have to be used for spill rather than generation. Thus increasing the lower bound would reduce the objective value, so Regulated Spill would have a non-zero reduced cost. If the upper bound on the satisfaction variable in the second example were less than one, it would reduce the objective to maximize satisfaction, so the reduced cost on the satisfaction variable is non-zero.

In this case that the satisfaction variable is frozen at a value of 1, it is as if the objective is frozen directly. This is not the case in general, however. The satisfaction variable only gets frozen if it is at its bound. (Typically this is when the satisfaction variable is at its upper bound of 1, but it can also occur if a satisfaction variable on an individual constraint in a Summation derived objective is at its lower bound of zero.) If the satisfaction is somewhere between 0 and 1, the satisfaction will not get frozen directly. Freezing all constraints with a non-zero dual price and all variables with a non-zero reduced cost has the equivalent effect of freezing the objective value but performs much better in terms of numeric stability.

Typically information about frozen variables is not as useful as information about frozen constraints when trying to understand the Optimization solution. Often this is due to the fact that when a variable gets frozen at a bound, this is an obvious limit that the user considers intuitively. Thus it does not tend to provide the user with more information than they already had. In some cases, however, identifying unexpected frozen variables can assist in debugging an Optimization model, particularly if incorrect upper or lower bounds were set on a variable unintentionally.

Shrinking Constraints

The concept of shrinking constraints can be important for understanding some optimization solution analysis information provided by RiverWare and for understanding how the solution behaves in terms of adding new constraints to the optimization problem.

In water resource management policies, it is common to have constraints at different priorities that have the same form (same left-hand-side) and differ only in the right-hand-side constraint value. For example, assume that a reservoir Storage variable has a formal upper bound of 10,000 acre-ft. In the policy constraints, there is a high priority Maximum Storage constraint to not exceed 9,000 acre-ft. At a lower priority there is a Target Operating Range constraint that applies a more restrictive max Storage of 8,000 acre-ft. Typically it is desirable to be below this elevation, but it might not always be possible due to high inflows. Then at a lower priority there is a Target Operating Storage Point constraint that constrains the Storage equal to 7,000 acre-ft, if possible.

Note: Internally, all “equal-to” constraints are converted to an equivalent pair of constraints.

Together, in addition to the upper bound, there would be three constraints with the same left-hand-side (LHS), in order from highest priority (1) to lowest (3):

• Priority 1:

• Priority 2:

• Priority 3:

Note: In practice, there would typically be constraints on other variables at intervening priorities between the constraints with the same LHS. For simplicity here were are only looking at the constraints with common LHS.

Rather than add a new constraint to the optimization problem each time, RiverWare minimizes the size of the optimization problem by shrinking the lower priority constraints into the higher priority constraint of the same form.

The priority 1 constraint, when written as a soft constraint with a satisfaction variable would have the following form:

Assuming that the priority 1 constraint is fully satisfied, the priority 2 constraint would conceptually have the following form:

However, instead of adding a new constraint, RiverWare notices that the new constraint has the same LHS and only differs in the right-hand-side value, so it shrinks the priority 2 constraint into the priority 1 constraint in the following form.

The less-than-or-equal-to portion of the priority 3 constraint would then shrink into this constraint in the same manner.

Note: All evaluation is done internally in RiverWare Optimization units, which are typically scaled SI units, not in user display units as shown here.

More generally, constraints with shrinking have the following form:

where each xm is a variable in the LHS of each of the constraints in the shrinking sequence, each am is the corresponding coefficient on the variable, each sn is the satisfaction variable associated with the constraint at the nth priority that contains a constraint with this common LHS, and each bn is the right-hand-side constraint value at the nth priority that contains a constraint with this LHS. UpperBound is the formal upper bound on the LHS. It is calculated by evaluating the LHS with each variable with a positive coefficient replaced by the variable’s upper bound and each variable with a negative coefficient replaced by the variable’s lower bound. For variables that correspond directly to a slot, the variable bounds are taken directly from the Upper and Lower Bounds set in the slot configuration. See “Variable Bounds” for details.

The form is the same for a “greater-than-or-equal-to constraint” except that the LowerBound is used. The LowerBound is calculated by evaluating the LHS with each variable with a positive coefficient replaced by the variable’s lower bound and each variable with a negative coefficient replaced by the variable’s upper bound.

In the example above, if the priority 2 constraint were not fully satisfied, then that constraint would be frozen. (See “Freezing Constraints” for details about freezing constraints.) In that case, the priority 3 constraint (or any subsequent constraints with the same LHS) would never get added to problem. Because the LHS value was already “locked in” at priority 2, no lower priority constraints can change its value. Thus there is no need to add any new constraints with the same LHS to the problem. In other words, RiverWare identifies if a new constraint would shrink to a constraint that is already frozen. If that is the case, then the new constraint does not get added to the problem. This can be important to understand when analyzing the solution. No solution analysis information will be provided for a constraint that would shrink to a constraint that was already frozen because the new constraint never gets added to the problem. If all of the constraints at one priority would shrink to constraints that are already frozen, then no new constraints get added to the problem at that priority, and thus there is no need to solve the problem at that priority. As a result, that priority will not show up in the standard diagnostic output with an objective value (percent satisfaction), nor will that goal appear in the Optimization Solution Analysis Tool. See “Priority-oriented Optimization Solution Analysis Tool” for details.

If some constraints from a given priority would shrink to frozen constraints, but others do not (i.e. there is still a solution at that priority, but some constraints introduced at that priority are omitted because they would not change the solution), the reporting of the satisfaction for the soft constraint derived objective depends on the type of derived objective that is selected. If the derived objective is Single Maximin or Repeated Maximin, then the satisfaction only reflects the satisfaction of the constraints that were formally added to the problem. It does not reflect the satisfaction of the constraints that were omitted (and would possibly have been violated). A tilde (~) is added to the reported satisfaction value to indicate that it is greater than the actual satisfaction from the user’s perspective because it does not include the omitted constraints. For a Summation derived objective, the reported average satisfaction is calculated as if the omitted constraints had been added to the problem. Thus it reflects the satisfaction from the user’s perspective, and no special notation is required.

If a frozen constraint shrinks to a higher priority constraint, the Optimization Solution Analysis Tool lists which constraint it shrinks to as part of the frozen constraint information (see “Priority-oriented Optimization Solution Analysis Tool”). Also, if a constraint is frozen, the solution analysis tool will report that all of its “shrink to” constraints were frozen as well. Without understanding how constraints shrink to earlier constraints, this can be confusing because it appears that a higher priority constraint was frozen even though the solution was not at the limit set by the constraint. Really it is the lowest priority constraint that shrank to that higher priority constraint that was forced to its limit and was frozen.

Revised: 06/03/2019