criss-cross method

Closing the gap in pivot methods for linear programming

  • Venkat Narayan
    • Categories Linear Programming Tags , , , , ,

    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 … Read more

    The s-Monotone Index Selection Rule for Criss-Cross Algorithms of Linear Complementarity Problems

  • Nagy Adrienn
  • Zsolt Csizmadia
  • Tibor Illés
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper we introduce the s-monotone index selection rules for the well-known crisscross method for solving the linear complementarity problem (LCP). Most LCP solution methods require a priori information about the properties of the input matrix. One of the most general matrix properties often required for finiteness of the pivot algorithms (or polynomial complexity … Read more