In designing an efficient decentralized resource allocation mechanism, decomposition theory is widely used as an organizing device. Recent developments in parallel processing technology for large-scale computation revive the research interests in decomposition methods. We pay particular attention to the implementability issues of the decomposition-based coordination mechanisms. In this study, we suggest two kinds of new decomposition method to enhance the implementability. To analyze the conflicts between the center and the divisions, a new analysis framework is introduced.
Most of decomposition methods utilize either primal (resource) information or dual (price) information, not both, as a control signal from the center. The implied information exchange process between the center and the divisions has been assumed to be in a predetermined fashion regardless existing informational structure. To resolve this rigidity, we propose a mixed decomposition method, where the center can select an arbitrary combination of price and quantity controls for common resources to each division. This is realized in two ways; i) two master problems are introduced so that one generates price signals and the other quantity signals, and ii) one hybrid master problem deals with both price and quantity information. The suggested methods are well justified in terms of the flexibility in information flow pattern choice (some prices and other quantities).
An organization is often considered as composed of a master or headquarters that is solely responsible for an optimal and feasible resource allocation and selfish divisions giving no attention to the rest of the system. Nevertheless, in the context of conflicts between the center and the divisions, there has been virtually no proper model to describe the real world situation within the decomposition framework. Such questions can be answered by a variety of plausible behavioral assumptions in the decentralized decision making procedure. To analyze the divisional attitude toward cooperation, we suggest two different frameworks. One is such that a few positive divisions cooperate to obtain a globally optimal resource allocation without an explicit master. Here it is quite natural that the cooperating division's optimum is compatible with the system-wide optimum, which often lacks in conventional decomposition methods such as Dantzig-Wolfe's. Though the model is rather normative to explain the reality, we think it can serve as a reference framework for an ideal situation. The other is more descriptive in nature, where we assume that divisions could have local objective function different from the central one. Informational decentralization assumption is still preserved in the framework so that the myopic cheating behavior of divisions can be analyzed more naturally.
Parallel implementation of the decomposition method on a network environment is accomplished to identify the comparative merits of the various decomposition alternatives. As a result, a set of tentative conclusions on the performance of decomposition methods are provided. Generally speaking, a decomposition method in parallel processing can be a powerful alternative for large-scale problems. Our proposed mixed decomposition shows a distinct superiority in reducing the central loss under divisional cheating. Cooperative decomposition reveals faster convergence in terms of iterations and solution time. Finally, possible extensions in the proposed decomposition methods are reviewed and future research directions are identified.
수리계획법의 분해해법은 단순히 계산상의 효율을 증대시키기 위한 수단으로서만이 아니라 분권화된 자원배분과정의 조정기구를 분석하는 이론적 틀로서 많은 연구의 대상이 되어 왔다. 그러나 분해해법에 근거한 조정기구로서 현실 문제를 분석할 때 그 실용성에 관해서는 많은 의문이 제기되어 왔다. 본 논문에서는 분권화된 조직의 다양한 정보교환구조와 각 하위부문의 다양한 행태적 특성에 관하여 융통성 있게 적용될 수 있는 분해해법을 개발하여 이의 실용성에 관하여 분석하고, 컴퓨터 모의실험에 의해 확인 하였다.
본 연구에서는 탄력적인 분해해법의 개발과 그 분석을 위하여 전형적인 블록대각 구조를 갖는 선형계획법 모형으로 자원배분문제를 표현하였으며 이 문제를 분해해법으로 푸는 과정을 분권화된 자원배분과정의 조정기구로 해석하였다. 본 연구에서 다루어진 주요한 내용은 다음과 같다.
첫째, 기존의 가격통제형 (Dantzig-Wolfe) 및 자원통제형 (Ten Kate) 분해해법이 실제 조직의 다양한 정보교환구조에 적용되기 어렵고 이를 해결하기 위해 제시된 혼합형 분해해법도 (Obel) 충분한 일반성을 갖지 못하므로, 이 문제를 해결하는 새로운 혼합형 분해해법을 개발하였다. 여기에서는 Master문제에서 공통자원에 대한 가격과 할당량을 모두 계산하여 하위부문문제의 구조적 특성에 따라 필요한 대로 가격/수량 정보를 선택적으로 제공한다. 하위부문문제에서는 Master가 가격을 제시한 자원에 대하여는 사용량을, 수량을 제시한 자원에 대해서는 가격을 계산하는 방식으로 반복적 정보교환이 이루어지며 이에 의하여 전 시스템의 최적해에 수렴할 수 있는 해법을 제시하였다. 이 해법은 하위부문의 수량정보를 다루는 Master와 가격정보를 다루는 Master의 두 문제를 이용하고 있으며, 두 문제를 절충식으로 결합한 하나의 Master문제를 푸는 변형도 제시 하였다. 이에 의하여 분권화된 조직의 기존 정보교환구조를 그대로 표현할 수 있으면서 최적해를 반드시 찾아가는 조정기구를 이론적으로 완성하였다.
둘째, 조직분권화이론에서는 자율성을 갖는 각 하위부문과 상위조정부서 사이의 협조와 갈등관계를 매우 중요하게 다루고 있으나 기존의 수리적 모형들은 이를 체계적으로 고려하지 못했다. 본 연구에서는 하위부문이 조직전체의 이익을 위해 협조적인 경우와, 조직전체의 이익보다는 부문만의 이익을 추구하는 상반된 두 가지 행태적 특성을 가정하여 이를 분해해법의 틀 안에서 수리적으로 분석하였다. 전자의 경우, Dantzig-Wolfe의 분해해법을 확장하여 협조형 분해해법을 제시하였으며 유한 수렴성을 증명하였다. 이 때에는 명시적인 Master문제의 조정이 없이도 최적해를 얻을 수 있다는 점이 특색이다. 후자의 경우에는 이기적인 하위부문이 정보교환과정에서 자신의 상위조정부서에 허위정보를 제공할 (Cheating) 가능성을 별도의 목적함수로 표현함으로써 기존이론의 (Jennergren) 비현실적 가정을 상당히 완화하였다. 이 때에는 조직전체의 이익은 허위정보가 없는 경우에 비하여 감소하지만 반드시 하위부문의 이익이 증대된다는 보장은 없음을 예제를 통하여 확인하였다. 이러한 두 가지 모형은 조직의 현실 상황에 따라 탄력적으로 적용될 수 있을 것이다.
셋째, 최근 컴퓨터의 병렬처리기술이 급속히 발전함에 따라 분해해법을 쉽게 병렬 처리 환경에 적용할 수 있게 되었는 바 이는 두 가지 의미를 갖는다. 그 하나는 계산측면으로 분해해법은 계산 효율상 아주 열등한 것으로 인정되어 왔으나, 병렬처리에 의하여 새로운 각광을 받게 되었다. 그러나 이에 관한 경험적 연구는 아직 충분하지 못한 상태이다. 다른 하나는 병렬처리 환경에서 분해해법을 적용하는 것이야 말로 조직분권화의 실제를 가장 근사하게 모의하는 것 (Simulation) 이 된다는 점이다. 본 연구에서는 이러한 배경에서 Workstation의 Network를 이용하여 기존의 Dantzig-Wolfe 및 Ten Kate해법, 본 연구를 통해 제안한 혼합형 및 협조형 해법을 체계적으로 비교하였다. 또한 하위부문의 정보왜곡이 (Cheating 또는 Information Misrepresentation) 있을 때의 효과도 실험을 통해 검토하였다. 실험결과 수렴속도의 측면에서는 협조형 해법이, 정보왜곡에 의한 손실의 방지와, 정보왜곡현상의 확인이라는 측면에서는 혼합형 해법이 우수함을 확인하였다.
