  


Closing the gap in pivot methods for linear programming
Venkat Narayan(Venkat.Narayanoutlook.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 primalanddual 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 primaldual 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 (nondecreasing) 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 (nonincreasing) $z = \ub{z}$, and $B^i$ to the least infeasible $B'^i$ with nonmonotone $z \in [\lb{z},\ \ub{z}]$. Bases $B'^p,\ B'^d$ and $B'^i$ may result from any $B \in \B$ enabling different interconnected, nonadjacent, crisscross paths to approach a terminal basis. Ignoring $B^i$ and primalanddual 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 crisscross variants that traverse a nonmonotone 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, crisscross method, duality gap Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: Download: [PDF] Entry Submitted: 07/28/2015 Modify/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  