When applied to Mixed Integer Programming (MIP) problems, Benders' iterative scheme considers two types of problem ; (1) an LP subproblem determined by fixing integer variables iteratively to a solution, (2) the relaxed pure integer program for solving the equivalent version of the original MIP problem. From the computational point of view, one major drawback of this method is that is requires solving (2) at each iteration. But when the integer part of MIP is of multiple choice type, (2) can be solved efficiently by sum-ranking method. This ranking-based modification is exploited in this paper. It assigns the priorities to the integer variables, which are determined by the amount of possible contribution to the objective value and it also defines another LP subproblem which calculates the decrease in the objective value due to the change in the righthand side. The modification is explained in comparison with the original Benders' Decomposition and finally an illustrative example and limited computational results are given.
혼합정수 계획문제에 적용된 BENDER 알고리즘은 문제를 선형계획문제와 정수계획문제로 분해하여 그들을 번갈아 풀므로써 최적해에 접근하는 방법을 택한다.
본 연구는 다중 선택혼합정수 계획문제에 BENDER 알고리즘을 수정, 적용함으로써 계산효율을 개선 시키고자 하는데 그 목적이 있다. 수정된 알고리즘은 위의 정수 계획문제를 매단계에서 직접푸는 대신 목적함수에의 기여가능정도에 따라 각 정수변수에 순위를 부여하며 그 순위에 따라 정수변수를 특정해에 고정시킴으로써 해를 개선해 나가는 방식을 택한다.
본 연구에서 수정된 기법으로 14개의 문제를 풀어본 결과 30-80개의 정수변수, 10-20개의 실수변수, 20-30개의 제약식을 가진 문제를 최대 26초에, 대개는 10초이내에 풀수 있었다. 이 결과는 매우 고무적인 것이나 수정된 알고리즘을 완전하게 분석하기 위해서는 더 큰 규모의 다양한 문제를 많이 풀어볼 필요가 있다. 이 기법은 첫째 일반화된 다중선택 혼합정수계획문제, 둘째 혼합정수계획문제의 실수부분이 수송문제와 같은 특수한 형태를 갖는 문제, 세째 k개의 최적해를 구하는 문제등에 확대, 응용될 수 있는데 이를 위해서는 여기에 추가하여 몇가지 수정이 필요하며 이에 대한 연구가 계속되기를 기대한다.
