A study on the column subtraction method applied to ship scheduling problem

Column subtraction, originally proposed by Harche and Thompson(1994), is an exact method for solving large set covering, packing and partitioning problems. Since the constraint set of ship scheduling problem(SSP) have a special structure, most instances of SSP am be solved by LP relaxation. This paper aim, at applying the column subtraction method to solve SSP which am not be solved by LP relaxation. For remained instances of unsolvable ones, we subtract columns from the finale simplex table to get another integer solution in an iterative manner. Computational results having up to 1,000 0-1 variables show better performance of the column subtraction method solving the remained instances of SSP than complex branch and-bound algorithm by LINDO.