On the Integral Simplex Method for Set-Partitioning problems
Anureet Saxena, PhD student, GSIA
Oct 31, 2003, Posner 152, 3:30--5pm

Abstract:

This talk concerns set-partitioning problem P and associated linear program P'. Integral Simplex Method (ISM) was introduced by Gerald Thompson as a specialised form of simplex method in which only pivots on ones were allowed. In this talk we discuss a strict generalisation of ISM which allows pivots on $-1$ in addition to pivots-on-1. We prove that given any two basic feasible integer solutions $x^{1}$ and $x^{2}$ to a set-partitioning, $x^{2}$ can be obtained from $x^{1}$ by a sequence of $p$ pivots-on-1 (where $p$ of the number of indices $j\in N$ for which $x_{j}^{1}$ is nonbasic and $x_{j}^{2}=1$), such that each solution in the associated sequence is feasible and integer. As a by-product of our result, we show advantages of allowing pivots on $-1$. We devise a graph theoretical framework to systematically study pivoting schemes for the ISMs which allow pivots on 1 and -1, and propose two pivoting schemes for the same. The first pivoting scheme is an integral anti-cycling pivoting scheme and can be considered as a generalisation of lexicographic anti-cycling rule for conventional simplex method. The second scheme is based on {\em dynamic rule} based graph traversal and can be considered as a generalisation of {\em Bland's} rule. Computational results comparing the later pivoting scheme with other conventional schemes are presented.