Linear Programming

Equivalence and Strong Equivalence between Sparsest and Least $\ell_1hBcNorm Nonnegative Solutions of Linear Systems and Their Application

  • Yun-Bin Zhao
    • Categories Applications - Science and Engineering, Convex Optimization, Linear Programming Tags , , , ,

    Many practical problems can be formulated as $\ell_0$-minimization problems with nonnegativity constraints, which seek the sparsest nonnegative solutions to underdetermined linear systems. Recent study indicates that $\ell_1$-minimization is efficient for solving some classes of $\ell_0$-minimization problems. From a mathematical point of view, however, the understanding of the relationship between $\ell_0$- and $\ell_1$-minimization remains incomplete. In … Read more

    Equivalence and Strong Equivalence between Sparsest and Least l1-Norm Nonnegative Solutions of Linear Systems and Their Application

  • Yun-Bin Zhao
    • Categories Convex Optimization, Global Optimization, Linear Programming Tags , , , ,

    Many practical problems can be formulated as $\ell_0$-minimization problems with nonnegativity constraints, which seek the sparsest nonnegative solutions to underdetermined linear systems. Recent study indicates that $\ell_1$-minimization is efficient for solving some classes of $\ell_0$-minimization problems. From a mathematical point of view, however, the understanding of the relationship between $\ell_0$- and $\ell_1$-minimization remains incomplete. In … Read more

    A First Course in Linear Optimization, version 3.0

  • Jon Lee
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Other Topics Tags , ,

    This is the “front matter” of a new open-source book on Linear Optimization. The book and associated Matlab/AMPL/Mathematica programs are freely available from: https://sites.google.com/site/jonleewebpage/home/publications/#book Citation Jon Lee, “A First Course in Linear Optimization”, Third Edition, Reex Press, 2013-2017. Article Download View A First Course in Linear Optimization, version 3.0

    Survivable Network Coding

  • Cédric Bentz
  • Sourour Elloumi
  • Eric Gourdin
  • Thibaut Lefebvre
    • Categories Linear Programming, Network Optimization, Telecommunications

    Given a telecommunication network, modeled by a graph with capacities, we are interested in comparing the behavior and usefulness of two information propagation schemes, namely multicast and network coding, when the aforementioned network is subject to single arc failure. We consider the case with a single source node and a set of terminal nodes. The … Read more

    Strengthened Bounds for the Probability of k-Out-Of-n Events

  • Shabbir Ahmed
  • Santanu S. Dey
  • Feng Qiu
    • Categories Linear Programming Tags , ,

    Abstract: Given a set of n random events in a probability space, represented by n Bernoulli variables (not necessarily independent,) we consider the probability that at least k out of n events occur. When partial distribution information, i.e., individual probabilities and all joint probabilities of up to m (m< n) events, are provided, only an ... Read more

    A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially

  • Volker Kaibel
  • Stefan Weltge
    • Categories Linear Programming, Polyhedra Tags , , , ,

    We establish that the extension complexity of the nXn correlation polytope is at least 1.5^n by a short proof that is self-contained except for using the fact that every face of a polyhedron is the intersection of all facets it is contained in. The main innovative aspect of the proof is a simple combinatorial argument … Read more

    Large-scale optimization with the primal-dual column generation method

  • Jacek Gondzio
  • Pedro Munari
  • Pablo Gonzalez-Brevis
    • Categories Convex Optimization, Linear Programming, Optimization Software and Modeling Systems Tags , , , , , ,

    The primal-dual column generation method (PDCGM) is a general-purpose column generation technique that relies on the primal-dual interior point method to solve the restricted master problems. The use of this interior point method variant allows to obtain suboptimal and well-centered dual solutions which naturally stabilizes the column generation. A reduction in the number of calls … Read more

    Steepest Edge as Applied to the Standard Simplex Method

  • Gavriel Yarmish
    • Categories Linear Programming Tags , , , , , , ,

    In this paper we discuss results and advantages of using steepest edge column choice rules and their derivatives. We show empirically, when we utilize the steepest edge column choice rule for the tableau method, that the density crossover point at which the tableau method is more efficient than the revised method drops to 5%. This … Read more

    RSP-Based Analysis for Sparsest and Least $\ell_1hBcNorm Solutions to Underdetermined Linear Systems

  • Yun-Bin Zhao
    • Categories Global Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , ,

    Recently, the worse-case analysis, probabilistic analysis and empirical justification have been employed to address the fundamental question: When does $\ell_1$-minimization find the sparsest solution to an underdetermined linear system? In this paper, a deterministic analysis, rooted in the classic linear programming theory, is carried out to further address this question. We first identify a necessary … Read more

    Optimization of Demand Response Through Peak Shaving

  • D. Craigie
  • Michael J. Todd
  • Andrew B. Philpott
  • Golbon Zakeri
    • Categories Applications - OR and Management Sciences, Linear Programming Tags , ,

    We consider a model in which a consumer of a resource over several periods must pay a per unit charge for the resource as well as a peak charge. The consumer has the ability to reduce his consumption in any period at some given cost, subject to a constraint on the total amount of reduction … Read more