(496f) Monitoring the Performance of Lp Optimization with Uncertain Parameters

Linear Programming (LP) remains the workhorse of applied optimization, having process applications such as production planning, inventory scheduling and steady-state determination at each execution of a Model Predictive Controller (MPC). The LP model usually contains some parameters that are certain, e.g., ones and zeros in a material balance, and some that are uncertain, e.g., yields in a chemical reactor model. When the parameters are uncertain, the values of the decision variables and the objective function are uncertain. This presentation discusses methods for characterizing the objective function in uncertain LP optimization.

UNCERTAINTY: A method for analyzing LP uncertainty should be general. First, multiple, uncertain parameters in a linear program are often correlated. For example, the yields of products from a chemical reactor are uncertain, but the sum of the yield parameters must be 1.0, because of material balance. Therefore, the analysis of an uncertain model should be general enough to handle either interval or correlated uncertainty. Second, uncertain parameters can appear in both equality and inequality constraints; the analysis should not be limited to the type of constraint equation. Third, the parameters should not be limited to the ?rim? of the LP, e.g., the cost coefficients and right hand sides of constraints; the method should address uncertainties that are multiplied by variables, the left hand coefficients. Finally, the method should not be restricted to ?small? parameter uncertainty, for which the optimal basis remains unchanged. The method presented here addresses all of these issues.

LP FEEDBACK: An additional important issue is whether the LP is implemented without feedback correction or with feedback. Most classical operations research presentations discuss LPs without feedback, while the recursion approach discusses a single correction based on perfect knowledge for the second solution. On the other hand, the LP solved for the steady state in MPC is corrected at every execution by feedback. Many other applications of LP have feedback, which is similar to the MPC application but implemented manually on a scheduled basis (per shift or day). Therefore, this presentation presents results for uncertain LPs in both situations, without feedback and with feedback. The feedback is of a simple nature, correcting the predicted right hand side value based on its measurement. Feedback is considered for the cost coefficients or for the left hand side coefficients.

ANALYSIS: The results of uncertainty can be characterized in many ways. Here, we will consider the effects on the objective function. We will consider two key effects on the objective function; the range between the maximum and minimum values (gap) and the expected value. Naturally, a large gap indicates the potential for a large loss, and a user who is risk sensitive would like to have a small gap. Also, a large difference between the nominal (error free) objective and the expected value of the uncertain objective is not desired. However, the expected value is more robust because it would not be sensitive to a large degradation in objective which could occur for only a very unlikely uncertainty at the extreme of the distribution.

METHODS WITHOUT FEEDBACK: In this approach, the LP solution must satisfy all constraints for every value within specified ranges for the uncertain parameters. Most of the results in this category can be obtained by methods previously available. However, one new method is presented, and the comparison with LP with feedback is also illuminating.

1. Objective Gap: The maximum objective gap for interval uncertainties in LP can be determined using the method by Chinneck and Ramadan (2000). When uncertainties appear in equalities, their method requires enumeration schemes.

A new method is presented here which determines the maximum gap in one solution for correlated uncertainties characterized by an ellipse. The method involves a bilevel optimization, with the difference between objectives (maximum and minimum) maximized by adjusting the values of the uncertain parameters.

2. Expected Objective: Under the assumption of normally distributed parameter uncertainty, this value is obtained using the method by Darlington et.al (1999). The key aspect of this problem that simplifies the calculations is the fact that the LP has only one basis, because the solution ?backs off? from the inequality constraints sufficiently to ensure that the solution is feasible for all values of the uncertain parameters. The solution can be found with one solution of a second-order cone program (Ben-Tal and Nemirovski, 1998).

The proposed method in this work can be tailored to determine the expected value of the gap in a bilevel optimization problem, which is solved without enumerative or iterative procedures.

METHOD FEEDBACK: In this approach, the converged LP solution, e.g., the solution after sufficient iterations with feedback, must satisfy all constraints for every value within specified ranges for the uncertain parameters. (This is essentially the LP problem in the MPC controller.) We note that these methods allow basis changes over the range of uncertain parameters. To our knowledge, the formulation and solutions are unique with this work.

1. Objective gap: The meaningful gap in this case is between true optimum objective (obtained with a perfect model) and the worst objective obtained with feedback. This is determined using a bilevel optimization, which evaluates the profit for each case and maximizes the difference in solution by adjusting the parameters within their uncertainty region. This is the cost for uncertainty in the final, converged solution of an LP with feedback.

2. Expected objective: Again, the assumption of normally distributed parameter uncertainty is made. In this case, two approaches are possible. In one, the ?size? of the ellipse describing the parameters uncertainty is changed by taking several values of the significance level of the parameters, and at each level, the objective gap is evaluated. Then, the expected value is determined by numerical integration. In the second method, the same approach is taken, but the result is obtained in a single solution. We note that the number of samples of the significance level is much smaller than the number of parameter value samples required if a Monte Carlo approach were taken to evaluate the expected value.

Both of the cases with feedback result in a bilevel optimization that contains complementarity constraints. The problem is non-convex, but computational results are very promising. The good results are facilitated by the use of an interior point optimization method in the IPOPT software (Raghunathan and Biegler, 2003).

Numerical results will be presented for problems with and without feedback. Cases will be from the previous literature and from gasoline blending. The use of the expected value is recommended for most process applications. The use of ?without? or ?with? feedback depends on the actual situation; for the LP in MPC, the use of ?with feedback? is essential.

The presentation will close with a brief discussion of the use of these monitoring approaches in the process industries and methods available to reduce parameter mismatch and improve LP optimization performance.

References

Ben-Tal, A. and Nemirovski, A. (1998) Robust Convex Optimization. Mathematics of Operations Research, 23 (4), 769-805.

Chinneck, J.W. and Ramadan, K. (2000) Linear Programming with Interval Coefficients. J.Opl.Res.Soc., 51, 209-220.

Darlington, J., Pantelides, C.C., Rustem, B. and Tanyi, B.A. (1999) An Algorithm for Constrained Nonlinear Optimization under Uncertainty. Automatica, 35, 217-228.

Raghunathan, A.U. and Biegler, L.T. (2003) Mathematical Programs with Equilibrium Constraints (MPECs) in Process Engineering. Comp. chem..Engng., 27, 1381-1392.