Linear Programming – Page 18 – Optimization Online

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

Published: 2013/07/17

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

Published: 2013/07/05

Applications - OR and Management Sciences, Linear Programming electricity planning, linear programming, monotonicity

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

A polynomial projection algorithm for linear programming

Published: 2013/07/05

Sergei Chubanov

Linear Programming

We propose a polynomial algorithm for linear programming. The algorithm represents a linear optimization or decision problem in the form of a system of linear equations and non-negativity constraints. Then it uses a procedure that either finds a solution for the respective homogeneous system or provides the information based on which the algorithm rescales the … Read more

Some preconditioners for systems of linear inequalities

Published: 2013/06/21

Javier F. Peña

Vera Roshchina

Negar Soheili

Convex Optimization, Linear Programming

We show that a combination of two simple preprocessing steps would generally improve the conditioning of a homogeneous system of linear inequalities. Our approach is based on a comparison among three different but related notions of conditioning for linear inequalities. ArticleDownload View PDF

Updating LU Factors of LP Simplex Bases

Published: 2013/05/29, Updated: 2015/11/28

Sande Gordon

Linear Programming bartels and golub method, fletcher and matthews method, updating lu factors, updating simplex bases

Methods for updating the LU factors of simplex basis matrices are reviewed. An alternative derivation of the Fletcher and Matthews method is given. This leads to generalizations of their method which avoids problems with both the Bartels and Golub method and the Fletcher and Matthews method. The improvements are to both numerical stability and data … Read more

An analogue of the Klee-Walkup result for Sonnevend’s curvature of the central path

Published: 2013/04/10

Murat Mut

Tamás Terlaky

Linear Programming

For linear optimization (LO) problems, we consider a curvature integral ﬁrst introduced by Sonnevend et al. (1991). Our main result states that in order to establish an upper bound for the total Sonnevend curvature of the central path, it is sufficient to consider only the case when n = 2m. This also implies that the … Read more

Which Nonnegative Matrices Are Slack Matrices?

Published: 2013/03/31

Linear Programming, Polyhedra extended formulation, polyhedral verification problem, polytope, slack matrices

In this paper we characterize the slack matrices of cones and polytopes among all nonnegative matrices. This leads to an algorithm for deciding whether a given matrix is a slack matrix. The underlying decision problem is equivalent to the polyhedral verification problem whose complexity is unknown. CitationApril 2013ArticleDownload View PDF

Computational aspects of simplex and MBU-simplex algorithms using different anti-cycling pivot rules

Published: 2013/02/24

Nagy Adrienn

Tibor Illés

Linear Programming, Optimization Software Benchmark index selection rules, linear programming, monotonic build-up simplex algorithm, primal simplex method

Several variations of index selection rules for simplex type algorithms for linear programming, like the Last-In-First-Out or the Most-Often-Selected-Variable are rules not only theoretically finite, but also provide significant flexibility in choosing a pivot element. Based on an implementation of the primal simplex and the monotonic build-up (MBU) simplex method, the practical benefit of the … Read more

Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimization

Published: 2013/02/19

Nicolas Gillis

Robert Luce

Data-Mining, Linear Programming hyperspectral unmixing, linear programming, nonnegative matrix factorization, pure-pixel assumption, robustness, separability

Nonnegative matrix factorization (NMF) has been shown recently to be tractable under the separability assumption, under which all the columns of the input data matrix belong to the convex cone generated by only a few of these columns. Bittorf, Recht, R\’e and Tropp (`Factoring nonnegative matrices with linear programs’, NIPS 2012) proposed a linear programming … Read more

Novel update techniques for the revised simplex method

Published: 2013/02/14

J. A. Julian Hall

Qi Huangfu

Linear Programming

This paper introduces three novel techniques for updating the invertible representation of the basis matrix when solving practical sparse linear programming (LP) problems using a high performance implementation of the dual revised simplex method, being of particular value when suboptimization is used. Two are variants of the product form update and the other permits multiple … Read more