We propose pivot methods that solve linear programs by trying to close the duality gap from both ends. The first method maintains a set $\B$ of at most three bases, each of a different type, in each iteration: a primal feasible basis $B^p$, a dual feasible basis $B^d$ and a primal-and-dual infeasible basis $B^i$. From each $B \in \B$, it evaluates the primal and dual feasibility of all primal and dual pivots to maximize lower bound $\lb{z}$ and minimize upper bound $\ub{z}$ on the optimal objective value $z^{*}$; i.e., it explores the adjacency neighborhood of the primal-dual vertex pair corresponding to $B$ in the underlying primal and dual hyperplane arrangements to minimize duality gap $\ub{z} - \lb{z}$. Among all primal feasible bases with (non-decreasing) objective $z = \lb{z}$ adjacent to any $B \in \B$, it selects the least infeasible $B'^p$ to update $B^p$. Likewise, it updates $B^d$ to the least infeasible $B'^d$ with (non-increasing) $z = \ub{z}$, and $B^i$ to the least infeasible $B'^i$ with non-monotone $z \in [\lb{z},\ \ub{z}]$. Bases $B'^p,\ B'^d$ and $B'^i$ may result from any $B \in \B$ enabling different interconnected, non-adjacent, criss-cross paths to approach a terminal basis. Ignoring $B^i$ and primal-and-dual infeasible pivots, a variant maintains and updates at most two bases $B^p$ and $B^d$. Restricting both methods to work with one customary basis yields criss-cross variants that traverse a non-monotone path visiting intermingled least infeasible bases (a) $B'^p$, $B'^d$ or $B'^i$, and (b) $B'^p$ or $B'^d$ in any order. To implement them, we outline primal and dual feasibility tests that complement the simplex minimum ratio test. Resolving the finiteness and complexity of these methods is an open problem.
Article
View Closing the gap in pivot methods for linear programming