집합 패킹 문제에 적용된 컬럼 서브트랙션 해법구현에 관한 연구

Abstract

Implementation of Column Subtraction Approach

for Set Packing Problem

Set problems to be made up of special formulation among IP optimization models have various applications. One of them, ship scheduling problem has developed into set packing problem and made a key role in success of shipping management.

A great number of efforts have been made to build not only relevant optimization models, but also decision support system for ship scheduling problem. But no means are available to estimate the efficiency of those algorithms applicable to the optimization model.

This paper aims at implementing column subtraction algorithm applied to set packing problem, especially to ship scheduling problem.

A brief experiment shows that column subtraction algorithm works well with the problem, a decision support system which written by OOP computes for the efficiency of column subtraction algorithm compared to branch-and-bound algorithm and gives chance to test various algorithms.