Linear Programming

A polynomial algorithm for linear optimization which is strongly polynomial under certain conditions on optimal solutions

  • Sergei Chubanov
    • Categories Linear Programming Tags , ,

    This paper proposes a polynomial algorithm for linear programming which is strongly polynomial for linear optimization problems $\min\{c^Tx : Ax = b, x\ge {\bf 0}\}$ having optimal solutions where each non-zero component $x_j$ belongs to an interval of the form $[\alpha_j, \alpha_j\cdot 2^{p(n)}],$ where $\alpha_j$ is some positive value and $p(n)$ is a polynomial of … Read more

    Generalized Dual Face Algorithm for Linear Programming

  • Ping-Qi Pan
    • Categories Applications - OR and Management Sciences, Linear Programming Tags , ,

    As a natural extension of the dual simplex algorithm, the dual face algorithm performed remarkably in computational experiments with a set of Netlib standard problems. In this paper, we generalize it to bounded-variable LP problems via local duality. Citation Department of Mathematics, Southeast University, Nanjing, 210096, China, 12/2014 Article Download View Generalized Dual Face Algorithm … Read more

    Clustering-Based Preconditioning for Stochastic Programs

  • Yankai Cao
  • Carl D. Laird
  • Victor M. Zavala
    • Categories Linear Programming, Quadratic Programming, Stochastic Programming

    We present a clustering-based preconditioning strategy for KKT systems arising in stochastic programming within an interior-point framework. The key idea is to perform adaptive clustering of scenarios (inside-the-solver) based on their influence on the problem as opposed to cluster scenarios based on problem data alone, as is done in existing (outside-thesolver) approaches. We derive spectral … Read more

    Primal-Dual Entropy Based Interior-Point Algorithms for Linear Optimization

  • Mehdi Karimi
  • Shen Luo
  • Levent Tunçel
    • Categories Linear Programming

    We propose a family of search directions based on primal-dual entropy in the context of interior-point methods for linear optimization. We show that by using entropy based search directions in the predictor step of a predictor-corrector algorithm together with a homogeneous self-dual embedding, we can achieve the current best iteration complexity bound for linear optimization. … Read more

    Simplex Algorithm for Countable-state Discounted Markov Decision Processes

  • Marina A. Epelman
  • H. Edwin Romeijn
  • Ilbin Lee
  • Robert L. Smith
    • Categories Dynamic Programming, Infinite Dimensional Optimization, Linear Programming Tags , ,

    We consider discounted Markov Decision Processes (MDPs) with countably-infinite state spaces, finite action spaces, and unbounded rewards. Typical examples of such MDPs are inventory management and queueing control problems in which there is no specific limit on the size of inventory or queue. Existing solution methods obtain a sequence of policies that converges to optimality … Read more

    Improvement of Kalai-Kleitman bound for the diameter of a polyhedron

  • Tomonari Kitahara
  • Noriyoshi Sukegawa
    • Categories Linear Programming Tags , ,

    Recently, Todd got a new bound on the diameter of a polyhedron using an analysis due to Kalai and Kleitman in 1992. In this short note, we prove that the bound by Todd can further be improved. Although our bound is not valid when the dimension is 1 or 2, it is tight when the … Read more

    Decomposition theorems for linear programs

  • Jacques Desrosiers
  • Jean-Bertrand Gauthier
  • Marco E. Lübbecke
    • Categories Linear Programming, Network Optimization Tags , , , ,

    It is well known that any feasible arc-flow solution to a network problem defined on a graph $G = (N, A)$, where $N$ is the set of nodes whereas $A$ is the set of arcs, can be expressed using at most $|A| + |N|$ paths and cycles having nonzero flow, out of these, at most … Read more

    Tools for primal degenerate linear programs: IPS, DCA, and PE

  • Jacques Desrosiers
  • Jean-Bertrand Gauthier
  • Marco E. Lübbecke
    • Categories Linear Programming Tags , , , , , ,

    This paper describes three recent tools for dealing with primal degeneracy in linear programming. The first one is the Improved Primal Simplex (IPS) algorithm which turns degeneracy into a possible advantage. The constraints of the original problem are dynamically partitioned based on the numerical values of the current basic variables. The idea is to work … Read more

    Efficient First-Order Methods for Linear Programming and Semidefinite Programming

  • James Renegar
    • Categories Linear Programming, Semi-definite Programming Tags , , ,

    We present a simple transformation of any linear program or semidefinite program into an equivalent convex optimization problem whose only constraints are linear equations. The objective function is defined on the whole space, making virtually all subgradient methods be immediately applicable. We observe, moreover, that the objective function is naturally “smoothed,” thereby allowing most first-order … Read more