Linear Programming and Extensions

By P. Nicola. 2000

2,565 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks (2017, methodology): “The simplex method [5] is a standard and highly efficient decision procedure for determining the TR-satisfiability of conjunctions of linear atoms.”
Reach for A*: Efficient Point-to-Point Shortest Path Algorithms (2006, methodology): “We say that d(v) is exact if it is equal to the distance from s to v. Dijkstra [5] (and independently Dantzig [3]) observed that if ` is nonnegative and v is a labeled vertex with the smallest distance label, then d(v) is exact and each vertex is scanned once.”
Semi-Supervised Semantic Role Labeling (2009, methodology): “In our study, we used the simplex algorithm (Dantzig, 1963).”
A New Method for Finding an Optimal Solution for Transportation Problems (2012, methodology): “Again in 1951 Dantzig [3] formulated the transportation problem as linear programming problem and also provided the solution method.”
Global inference for sentence compression : an integer linear programming approach (2008, background): “The simplex algorithm (Dantzig, 1963) solves LPs by exploring the extreme points of a polyhedral set.”
Numerical optimization (2004, methodology): “We refer the reader to Dantzig [86] and Fourer, Gay, and Kernighan [112] for more comprehensive discussion of this issue.”
Bayesian Quantile Regression for Ordinal Models (2016, methodology): “Classical techniques include the simplex algorithm (Dantzig 1963; Dantzig and Thapa 1997, 2003; Barrodale and Roberts 1973; Koenker and d’Orey 1987), and the interior point algorithm (Karmarkar 1984; Mehrotra 1992; Portnoy and Koenker 1997), whereas Bayesian methods relying on Markov chain Monte Car”
Introduction to Global Optimization (2006, neutral): “The most celebrated algorithm for solving such problems is the Simplex Algorithm, proposed by Dantzig in the late 40s/early 50s [Dan63]; its worst-case complexity is exponential in the number of problem variables, but it performs extremely eﬃciently in most practical instances.”
Multiple Object Tracking Using K-Shortest Paths Optimization (2011, positive): “Second, we demonstrate that this Linear Programming problem can be solved very effectively using the k-shortest paths algorithm [6].”
Optimization for machine learning (2010, background): “, 1994) and their ability to compete with a much older rival, the simplex method (Dantzig, 1963).”
Routing, flow, and capacity design in communication and computer networks (2004, background): “, the pioneering work of the American mathematician George Dantzig [Dan63], the simplex method has become a standard and extremely successful approach, commonly available in commercial and freeware software tools.”
A Brief History of Linear and Mixed-Integer Programming Computation (2012, methodology): “In [11] it is reported that the first application of Dantzig’s simplex algorithm to the solution of a non-trivial LP was Laderman’s solution of a 21 constraint, 77 variable instance of the classical Stigler Diet Problem [41].”
The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate (2011, methodology): “The last two statements of the lemma were given in [32] whose proofs were based on Dantzig [5] [6] and Veinott [29] .”
A tutorial on support vector regression (2004, positive): “The (cid:2)rst step consists of solving a linear approximation of the QP problem by the simplex algorithm [Dantzig, 1962].”
ETSAP-TIAM: the TIMES integrated assessment model Part I: Model structure (2008, methodology): “The formulation described here is based on Dantzig (1963), also summarized in Kanudia and Loulou (1998), and uses the expected cost criterion.”
Linear Programming (2018, positive): “The first operations research programs have been modelled by using linear objective function and constraints, and, to date, the Simplex Method for solving LPs is one of the most practically efficient and powerful algorithms in Operations Research [Dan63].”