서지주요정보
(A) modified benders' decomposition for multiple choice mixed integer programming problems
서명 / 저자 (A) modified benders' decomposition for multiple choice mixed integer programming problems / Suk-Gwon Jang.
발행사항 [서울 : 한국과학기술원, 1981].
Online Access 원문보기 원문인쇄

소장정보

등록번호

4001208

소장위치/청구기호

학술문화관(문화관) 보존서고

MMGS 8124

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

리뷰정보

초록정보

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개의 최적해를 구하는 문제등에 확대, 응용될 수 있는데 이를 위해서는 여기에 추가하여 몇가지 수정이 필요하며 이에 대한 연구가 계속되기를 기대한다.

서지기타정보

서지기타정보
청구기호 {MMGS 8124
형태사항 [ii], 46 p. : 삽도 ; 26 cm
언어 영어
일반주기 Appendix : Computer code
저자명의 한글표기 : 장석권
지도교수의 영문표기 : Dong-Wan Tcha
지도교수의 한글표기 : 차동완
학위논문 학위논문(석사) - 한국과학기술원 : 산업공학과,
서지주기 Reference : p. 45-46
주제 혼합 정수 계획법. --과학기술용어시소러스
알고리즘. --과학기술용어시소러스
오퍼레이션 리서치. --과학기술용어시소러스
Operations research.
QR CODE qr code