일반 할당 문제에 대한 변형된 열 생성 기법

Abstract

분지한계법은 정수계획법 문제를 푸는 가장 기본적인 알고리즘이다. 분지한계법에서는 각 마디에서 제공되는 한계값이 중요한 역할을 한다. 이 논문에서는 정수계획법 문제의 선형완화문제 한계값을 개선시키려고 한다. 일반 할당 문제를 여기에서 다룬다. 가장 대표적인 정수계획법 문제이고, 많은 연구가 이뤄지고 있기 때문이다. 일반 할당 문제는 에이전트들의 업무량 제한을 넘지 않으면서 각 작업들을 최소의 비용으로 할당하는 문제이다. 일반 할당 문제는 주로 분지평가법으로 해결한다. 분지평가법에서는 선형완화 문제를 열 생성 기법으로 푼다. 이 논문에서는 변형된 수리모형을 제시하여 일반 할당 문제에 대한 열 생성 기법의 한계값을 개선시킬 것이다. 이는 부문제에서 복수의 에이전트들을 동시에 고려하는 것으로 이뤄질 것이다. 기존의 열 생성 기법과 변형된 열 생성 기법을 비교하는 계산 결과를 첨부하였다.