Linear Programming

Submodular Minimization in the Context of Modern LP and MILP Methods and Solvers

  • Jon Lee
  • Siqian Shen
  • Andrew Orso
    • Categories 0-1 Programming, Combinatorial Optimization, Linear Programming Tags , , , ,

    We consider the application of mixed-integer linear programming (MILP) solvers to the minimization of submodular functions. We evaluate common large-scale linear-programming (LP) techniques (e.g., column generation, row generation, dual stabilization) for solving a LP reformulation of the submodular minimization (SM) problem. We present heuristics based on the LP framework and a MILP solver. We evaluated … Read more

    Looking for strong polynomiality in Linear Programming : Arguments, conjectures, experiments, findings, and conclusion.

  • Peter A. Bruijs
    • Categories Convex Optimization, Linear Programming

    Until now it has been an open question whether the Linear Programming (LP) problem can be solved in strong polynomial time. The simplex algorithm with its combinatorial nature does not even offer a polynomial bound, whereas the complexity of the polynomial algorithms by Khachiyan and Karmarkar is based on the number of variables n, and … Read more

    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. CitationDepartment of Mathematics, Southeast University, Nanjing, 210096, China, 12/2014ArticleDownload View PDF

    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