(78e) Global Optimization of a Class of Large Scale Process Operations Problem through Dual Decomposition

In the process industry, integrated decision making and addressing uncertainty have been identified as two of the most important factors that affect the efficient implementation of planning and scheduling operations for the production systems. First, the integrated planning and scheduling problem can be rigorously modeled through a set of production planning constraints and a large number of scheduling constraints for all the planning periods [1]. Second, stochastic integer programming with mixed integer recourse is widely used to address uncertainty in process operations such as stochastic scheduling [2]. When the uncertainty is described with discrete distributions (scenarios), the deterministic equivalence of the stochastic programming problem takes a similar decomposable structure as the planning and scheduling integration problem.

The class of optimization problem derived from the above two process operations problems is generally in large scale and hard to be solved directly. In this work, we propose a new solution method for the global optimization of this class of problems. The proposed method follows a dual decomposition (scenario decomposition) idea, which is based on the augmented Lagrangian relaxation approach. The augmented Lagrangian optimization algorithm consists of an outer and an inner loop. In the outer loop, the method of multipliers is used to update the multipliers and penalty parameters, while the inner loop is used to compute a solution of the augmented Lagrangian relaxation problem. It is proved that if in each outer iteration, a ε_k-global optimum of the relaxation problems is found, where ε_k is a decreasing sequence with ε_k→ε, then the convergence to ε-global optimum of the original problem is ensured for the augmented Lagrangian method [3]. So to find the ε-global optimal solution for the original problem is equivalent to find the ε-global optimal solution for the augmented Lagrangian relaxation problem.

In the proposed solution framework, the solution procedure can be divided into two phases. In the first phase, the augmented Lagrangian relaxation problem is solved approximately using Block Coordinate Decent (BCD) method [4] until the norm value of the non-anticipativity constraints is small enough which means that the mulitpliers' values are close to their optimal value. In the BCD solution framework, the relaxation problem can be decomposed and solved in parallel. In the second phase, the relaxation problem is solved using global optimization method based on Branch and Bound (B&B) to ensure that the ε-global optimal solution is obtained. During the B&B step, the lower bounding problem is obtained through convex underestimation of the non-separable bilinear term, thus the lower bounding problem can be also decomposed and solved in parallel, and the upper bound is obtained by solving the relaxation problem with BCD method similar to the first phase.

Comparing to the traditional dual decomposition method [5] based on classical Lagrangian relaxation, the proposed method has the following advantages. First the feasibility of the subproblems is always ensured and second no heuristic step is necessary to evaluate an upper bound (feasible solution) for the original problem. The effectiveness of the proposed methodology is illustrated through a set of examples.

[1] Li, Z., Ierapetritou, M.G (2010). Production planning and scheduling integration through augmented Lagrangian optimization. Computers & Chemical Engineering, 34, 996.

[2] Sand, G., Engell, S (2004). Modeling and solving real-time scheduling problems by stochastic integer programming. Computers & Chemical Engineering, 28, 1087.

[3] Birgin, E.G., Floudas, C.A., & Martínez, J.M. (2009). Global minimization using an Augmented Lagrangian method with variable lower-level constraints. Math. Program., Ser. A DOI 10.1007/s10107-009-0264-y.

[4] Bertsekas, D.P., & Tsitsiklis, J.N. (1989). Parallel and Distributed Computation. Englewood Cliffs, New Jersey, Prentice-Hall.

[5] Caroe, C.C., & Schultz, R. (1999). Dual decomposition in stochastic integer programming. Operations Research Letters, 24,37.