Improving Dual Bound for Stochastic MILP Models Using Sensitivity Analysis

Large scale stochastic integer or mixed-integer linear programming models arise in various areas such as asset/liability management, unit commitment, power management, capacity planning, water resource management, and supply chain management. One possible way to tackle such models is to represent the model as a combination of several scenario subproblems by duplicating the variables that are common in those scenarios and adding the equality of the duplicated variables into the model. After such a reformulation, every scenario is represented by a block of constraints and variables, and the rows that link scenario subproblems denote non-anticipativity constraints. To solve such problems, a dual decomposition method has been proposed by Carøe and Schultz (1999) where the non-anticipativity constraints are dualized so that every scenario problem can be solved independently. The relaxed bound coming from the solution of individual scenario problems is improved by updating the multipliers using a non-smooth optimization method such as subgradient (Fisher, 1985), incremental subgradient (Nedic and Bertsekas, 2001), dual ascent (Erlenkotter, 1978), or bundle methods (Lemarechal, 1974). The bottleneck when using these methods is that in order to update the search direction and the step size, every scenario subproblem has to be optimized at every iteration. An exception is the method by Zhao et al. (1997) where only a subset of scenarios is optimized to update search direction. Although there have been many improvements on the bound generation, in case of large size stochastic integer or mixed-integer models, it is still very time consuming to improve the dual bound by using nonsmooth optimization methods.

This work deals with improving the dual bound during the solution of a stochastic mixed-integer linear programming model using Dual decomposition (Carøe and Schultz, 1999). It proposes extracting relevant sensitivity information from the branch and bound or branch and cut tree of every scenario subproblem and use that information in a linear programming model to improve the dual bound. The idea is based on the mixed integer linear programming sensitivity analysis method proposed by Dawande and Hooker (2000). Two numerical examples have been presented that show that the proposed method can produce very significant computational savings when compared to the conventional subgradient method.

References:

Carøe, C. C., Schultz, R., 1999. Dual decomposition in stochastic integer programming. Operations Research Letters 24, 37–45.

Dawande, M. W., Hooker, J. N., 2000. Inference-based sensitivity analysis for mixed integer/linear programming. Operations Research 48 (4), 623–634.

Erlenkotter, D., 1978. A dual-based procedure for uncapacitated facility location. Operations Research 26 (6), 992–1009.

Fisher, M. L., 1985. An applications oriented guide to lagrangian relaxation. Interfaces 15 (2), 10–21.

Lemarechal, C., 1974. An algorithm for minimizing convex functions. In: IFIP Congress. pp. 552–556.

Nedic, A., Bertsekas, D. P., 2001. Incremental subgradient methods for nondifferentiable optimization. SIAM Journal on Optimization 12 (1), 109–138.

Zhao, X., Luh, P. B., Wang, J., 1997. The surrogate gradient algorithm for Lagrangian relaxation method. In: Proceedings of the 36th IEEE Conference. pp. 305–310.