Three articles on Integral Simplex Method

Set partitioning is an important problem in combinatorial optimisation with applications in diverse areas such rail-road crew scheduling, aircraft-crew scheduling, truck routing, political districting, switching-circuit designing and many other scheduling-type problems. Several approaches have been proposed, developed and tested to solve this problem. In this paper we look at primal approaches to the Set-partitioning problem. Primal approaches to set-partitioning problems were developed and experimented by Krabek et al [1]. A theoretical development of primal approaches is presented in a paper of Balas and Padberg [2], which further led to an algorithm [4]. These papers contained the ideas of pivot-on-1 rules and other ingredients which nally led to a branch and bound algorithm to solve set-partitioning problem without using any cutting planes. Gerald Thompson [3] gave the rst branch and bound algorithm which uses the theoretical development of the primal approaches to set-partitioning problem. Thompson discusses the idea of Integral Simplex Method(ISM) in his paper titled "An Integral Simplex Algorithm for Solving Combinatorial Optimisation Problems". The basic idea of ISM is to use a modied version of the simplex method, which he calls as Local Integral Simplex Method, in which pivot steps are made only on one entries in the simplex tableau. The method stops making further pivots when it has found a local optimum and no more improving pivots