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

    An Improvised Approach to Robustness in Linear Optimization

  • Mehdi Karimi
  • Somayeh Moazeni
  • Levent Tunçel
    • Categories Applications - OR and Management Sciences, Robust Optimization Tags ,

    We treat uncertain linear programming problems by utilizing the notion of weighted analytic centers and notions from the area of multi-criteria decision making. In addition to many practical advantages, due to the flexibility of our approach, we are able to prove that the robust optimal solutions generated by our algorithms are at least as desirable … 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 CitationJon Lee, “A First Course in Linear Optimization”, Third Edition, Reex Press, 2013-2017.ArticleDownload View PDF

    Benders, Nested Benders and Stochastic Programming: An Intuitive Introduction

  • James Murphy
    • Categories Stochastic Programming Tags , , , , , , ,

    This article aims to explain the Nested Benders algorithm for the solution of large-scale stochastic programming problems in a way that is intelligible to someone coming to it for the first time. In doing so it gives an explanation of Benders decomposition and of its application to two-stage stochastic programming problems (also known in this … Read more

    Conic Geometric Programming

  • Venkat Chandrasekaran
  • Parikshit Shah
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , , , , , ,

    We introduce and study conic geometric programs (CGPs), which are convex optimization problems that unify geometric programs (GPs) and conic optimization problems such as linear programs (LPs) and semidefinite programs (SDPs). A CGP consists of a linear objective function that is to be minimized subject to affine constraints, convex conic constraints, and upper bound constraints … 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

    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

    A Polynomial Time Constraint-Reduced Algorithm for Semidefinite Optimization Problems, with Convergence Proofs

  • Dianne P. O'Leary
  • Sungwoo Park
    • Categories Semi-definite Programming Tags , , , , , , , , ,

    We present an infeasible primal-dual interior point method for semidefinite optimization problems, making use of constraint reduction. We show that the algorithm is globally convergent and has polynomial complexity, the first such complexity result for primal-dual constraint reduction algorithms for any class of problems. Our algorithm is a modification of one with no constraint reduction … 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