- Closing the gap in pivot methods for linear programming Venkat Narayan(Venkat.Narayan outlook.com) Abstract: 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. Keywords: Linear programming, hyperplane arrangement, pivot methods, simplex method, criss-cross method, duality gap Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: Download: [PDF]Entry Submitted: 07/28/2015Entry Accepted: 07/28/2015Entry Last Modified: 07/28/2015Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society. 