Optimization Online


Closing the gap in pivot methods for linear programming

Venkat Narayan(Venkat.Narayan***at***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 )


Download: [PDF]

Entry Submitted: 07/28/2015
Entry Accepted: 07/28/2015
Entry Last Modified: 07/28/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society