(12b) Uncertainty Analysis of Milp Problems

Uncertainty is a very important factor in process operations. While uncertainty arises in some of the parameters, the optimal schedule of deterministic model could become infeasible. Therefore, the consideration of uncertainty in scheduling problem becomes of great importance in order to preserve plant feasibility and viability during operations. In our work, a systematic framework is developed to address the problem of accounting for uncertainty in the scheduling decision-making process.

A number of problems from the area of process design and operations are commonly formulated as Mixed Integer Linear Programming (MILP) problems. One way to incorporate uncertainty into these problems is using MILP sensitivity analysis and parametric programming methods. The main limitation of most existing methods is they can only be applied to problems with a single uncertain parameter or several uncertain parameters varying in a single direction. Acevedo and Pistikopoulos [1] proposed a parametric programming approach for the analysis of linear programming problems under uncertainty. The procedure is based on the solution of Multiparametric Linear Programming (mpLP) at each node of the Branch and Bound tree. It then compares and identifies the different optimal integer solutions and their corresponding optimal value functions. Pertsinidis et al. [3] developed an algorithm for MILP sensitivity analysis. At each iteration, the LP sensitivity analysis results and a cut that excludes the current integer solution are incorporated into a MILP problem so as to find the breaking point and the successor optimal integer solution. Their ideas were extended by Dua and Pistikopoulos [2], by decomposing the mp-MILP into two subproblems and then iterating between them. The first subproblem is obtained by fixing the integer variables, resulting in a mpLP problem, whereas the second subproblem is obtained by relaxing the parameters as variables, leading to a MILP problem.

In this work, a novel framework is developed to deal with multiple uncertain parameters that can vary independently. Assume that the problem is a minimization problem and we want to investigate two RHS (right-hand-side) parameters, a and b, changing in the range of [a0, a0 + a'] and [b0, b0 + b']. The first step of the procedure is to solve the MILP problem at its nominal values (a0, b0) using branch and bound algorithm and the optimal solution is found at an arbitrary node, which is denoted as node 0. Other leaf nodes of the B&B tree are denoted as node 1, node 2, ..., node n.

In the next step, a mpLP is solved at each of the leaf nodes including node 0, so as to identify the optimal value functions and their corresponding critical regions in the region of [a0, a0 + a'] and [b0, b0 + b']. A new algorithm is proposed for the solution of mpLP. For the case of RHS uncertain parameters, the original LP problems at the leaf nodes are first converted to its dual form, so that the uncertain parameters appear in the objective function. Starting from the nominal point (a0, b0), a linear expression for the objective value changing with respect to the uncertain parameters is identified as z = z0 + λ0*a + β0*b and then incorporated in a nonlinear programming problem. In this NLP problem, the objective function is to maximize the gap between the optimal objective value (cx) at any point (a, b) in the uncertain range and the maximum value of the linear expressions (max {zk + λk*a + βk*b }), and therefore takes the form (cx ? z). The constraints contain the original constraints and the current linear expressions (z ≥ zk + λk*a + βk*b), hence all the constraints of the NLP problem are linear. If the objective value of the NLP model is nonzero, it means that there exists at least one point (a', b') at which its real objective value cannot be represented by any of the current objective value functions. Therefore, the objective value function at that point is z = z' + λ'*a + β'*b and should be included in the next iterations. At each iteration, a NLP problem is solved in order to identify any uncovered region. This procedure terminates when the objective value for this NLP problem is 0, which means that the entire uncertain parameter range is covered by the existing objective value functions.

The following step is to compare these critical regions of all these leaf nodes and finally identify a set of new critical regions and objective value functions. Two objective value functions are comparable only in the same region and a redundancy test is used for the comparison procedure [1]. Assuming from the previous step - that at node 1 it is found that the optimal objective value function is z = z1 + λ1*a + β1*b in critical region CR1 and at node 2 z = z2 + λ2*a + β2*b in critical region CR2. CR1 and CR2 have intersection CRint. In order to determine the objective value function in CRint, a new constraint z1 + λ1*a + β1*b ≥ z2 + λ2*a + β2*b is defined. If the problem is infeasible, it implies z = z2 + λ2*a + β2*b for CRint. If the new constraint is found to be redundant, it means z = z2 + λ2*a + β2*b for CRint. If the new constraint is not redundant, it means CRint is divided into two parts by the new constraint, z1 + λ1*a + β1*b provides a better solution on one side and z2 + λ2*a + β2*b gives a better solution on the other side.

Therefore, for a given range of uncertain parameters in a MILP problem, the output of this proposed framework is a set of optimal integer solutions and their corresponding critical regions and objective value functions.

Comparing to the existing approach [1], the proposed method solves the mpLP at the only leaf nodes in the B&B tree instead of every node during the branching and bounding procedure, and consequently reduces the computational efforts significantly.

A number of numerical examples are presented to illustrate the proposed ideas. The proposed approach is also applied to scheduling problems, where the binary variables represent the sequences of tasks being performed in the units. Given the range of uncertain parameters, such as processing time, demands, etc., a set of alternative schedules can be identified and the optimal objective value (makespan, cost etc.) can be expressed by a number of linear expressions in terms of the uncertain parameters.

Reference: [1] J. Acevedo and E.N. Pistikopoulos. A multiparametric programming approach for linear process engineering problems under uncertainty, Ind. Eng. Chem. Res. 36 (1997).

[2] V. Dua and E.N. Pistikopoulos. An algorithm for the solution of multiparametric mixed integer linear programming problems, Ann. Oper. Res. 99 (2000).

[3] A. Pertsinidis, I.E.Grossmann and G.I.McRae. Parametric optimization of MILP programs and a framework for the parametric optimization of MINLPs, Comput. Chem. Eng. 22Suppl. (1998).