Branch and bound algorithm is the most basic algorithm to solve the interger programming problem. In branch and bound algorithm, the bound provided at each node is perform important role. In this paper, we will enhance the bound of linear relaxation problem of the integer programming problem. The generalized assignment problem is considered here because it is one of the most important problem in intger programming problem and considerable body of literature exists about it. The problem examines the minimum cost assignment of jobs to agents such that each job is assigned to exactly one agent subject to capacity restrictions on the agents. Branch and price algorithm is usually applied to solve the generalized assignment problem. In branch and price algorithm, the master problem is solved by column generation. We propose the modified model to improve the bound of the column generation for the generalized assignment problem. It will be done by considering multiple agents at once in sub-problems. Computational results that compares the standard column generation bound and proposed column generation bound are reported.
분지한계법은 정수계획법 문제를 푸는 가장 기본적인 알고리즘이다. 분지한계법에서는 각 마디에서 제공되는 한계값이 중요한 역할을 한다. 이 논문에서는 정수계획법 문제의 선형완화문제 한계값을 개선시키려고 한다. 일반 할당 문제를 여기에서 다룬다. 가장 대표적인 정수계획법 문제이고, 많은 연구가 이뤄지고 있기 때문이다. 일반 할당 문제는 에이전트들의 업무량 제한을 넘지 않으면서 각 작업들을 최소의 비용으로 할당하는 문제이다. 일반 할당 문제는 주로 분지평가법으로 해결한다. 분지평가법에서는 선형완화 문제를 열 생성 기법으로 푼다. 이 논문에서는 변형된 수리모형을 제시하여 일반 할당 문제에 대한 열 생성 기법의 한계값을 개선시킬 것이다. 이는 부문제에서 복수의 에이전트들을 동시에 고려하는 것으로 이뤄질 것이다. 기존의 열 생성 기법과 변형된 열 생성 기법을 비교하는 계산 결과를 첨부하였다.