AN ADVANCED START ALGORITHM FOR ALL-INTEGER PROGRAMMING

Integer programming (IP) models have wide application in such diverse areas as product mix planning, scheduling/routing, portfolio selection, and scores of others. In this paper, the authors present an all-integer cutting plane technique called the Advanced Start Algorithm (ASA), for solving the all-integer (otherwise linear) programming problem (IP). They develop a good advanced primal-infeasible start based on the optimal solution to the LP relaxation, and use a two-stage dual/primal algorithm to obtain the optimal solution to (IP). They illustrate the operation of the ASA on three small problems, and exhibit computational results on a set of standard test problems.