Algoritma Branch and Cut untuk Program Stokastik Biner Campuran

Abstract

Decomposition has proved to be one of the more effective tools for the solution of large-scale problems, especially those arising in stochastic programming.A decom position method with wide applicability is Benders decomposition, which has been applied to both stochastic programming as well as integer programming problems. However, this method of decomposition relies on convexity of the value function of linear programming subproblems. This paper is devoted to a class of problems in which the second-stage subproblem(s) may impose integer restrictions on some variables. The value function of such integer subproblem(s) is not convex, and new approaches must be designed. In this paper, discuss alternative decomposition methods in which the second-stage integer subproblems are solved using branch and-cut methods. One of the main advantages of our decomposition scheme is that Stochastic Mixed-Integer Programming (SMIP) problems can be solved by dividing a large problem into smaller MIP subproblems that can be solved in parallel. This paper lays the foundation for such decomposition methods for two-stage stochastic mixed-integer programs.

Dekomposisi telah terbukti menjadi salah satu alat yang lebih efektif untuk me mecahkan masalah dalam skala besar, terutama yang timbul dalam program stokastik. Metode dekomposisi dengan aplikasi yang luas disebut dekomposisi Benders, yang diterapkan untuk kedua program stokastik sebagai masalah pro gram integer. Namun, metode dekomposisi bergantung pada sifat convexity dari nilai fungsi submasalah program linier. Penelitian ini ditujukan untuk kelas ma salah pada submasalah tahap kedua (s) yang memberlakukan pembatasan integer pada beberapa variabel. Nilai fungsi setiap submasalah integer (s) tidak con vex, maka pendekatan baru harus dirancang. Dalam penelitian ini, membahas metode alternatif dekomposisi di mana submasalah integer tahap kedua disele saikan dengan menggunakan metode branch and cut. Salah satu keuntungan utama skema dekomposisi ini adalah bahwa masalah program stokastik integer campuran (SMIP) dapat diselesaikan dengan membagi masalah yang besar men jadi submasalah MIP yang kecil yang dapat diselesaikan secara paralel. Penelitian ini meletakkan dasar untuk setiap metode dekomposisi untuk program stokastik integer campuran tahap kedua.