Exact solutions to linear programming problems

DOI10.1016/J.ORL.2006.12.010zbMath1177.90282DBLPjournals/orl/ApplegateCDE07OpenAlexW2109742527WikidataQ95137695 ScholiaQ95137695MaRDI QIDQ2467437

Sanjeeb Dash, William Cook, David L. Applegate, Daniel G. Espinoza

Publication date: 21 January 2008

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2006.12.010

zbMATH Keywords

linear programmingsimplex algorithmrational arithmetic

Mathematics Subject Classification ID

Linear programming (90C05) Extreme-point and pivoting methods (90C49)

Related Items (33)

A Safe Computational Framework for Integer Programming Applied to Chvátal’s Conjecture ⋮ Algorithm 1021: SPEX Left LU, Exactly Solving Sparse Linear Systems via a Sparse Left-looking Integer-preserving LU Factorization ⋮ Solving Multiscale Linear Programs Using the Simplex Method in Quadruple Precision ⋮ Local cuts for mixed-integer programming ⋮ Revisiting a cutting-plane method for perfect matchings ⋮ A review of computation of mathematically rigorous bounds on optima of linear programs ⋮ Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates ⋮ Numerically Safe Lower Bounds for the Capacitated Vehicle Routing Problem ⋮ Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems ⋮ On a computationally ill-behaved bilevel problem with a continuous and nonconvex lower level ⋮ Maximum-weight stable sets and safe lower bounds for graph coloring ⋮ Certifying feasibility and objective value of linear programs ⋮ Certifying algorithms ⋮ Rigidity of spherical codes ⋮ An Exact Rational Mixed-Integer Programming Solver ⋮ Safe Lower Bounds for Graph Coloring ⋮ On the exact separation of mixed integer knapsack cuts ⋮ Using massively parallel computations for absolutely precise solution of the linear programming problems ⋮ Improved WLP and GWP lower bounds based on exact integer programming ⋮ Sign conditions for injectivity of generalized polynomial maps with applications to chemical reaction networks and real algebraic geometry ⋮ Roundoff-Error-Free Algorithms for Solving Linear Systems via Cholesky and LU Factorizations ⋮ Computational experience with general cutting planes for the set covering problem ⋮ Testing cut generators for mixed-integer linear programming ⋮ A computational status update for exact rational mixed integer programming ⋮ Linear programming using limited-precision oracles ⋮ A computational status update for exact rational mixed integer programming ⋮ On the safety of Gomory cut generators ⋮ A hybrid branch-and-bound approach for exact rational mixed-integer programming ⋮ A Duality-Based Method for Identifying Elemental Balance Violations in Metabolic Network Models ⋮ Iterative Refinement for Linear Programming ⋮ Exact Solution of Sparse Linear Systems via Left-Looking Roundoff-Error-Free LU Factorization in Time Proportional to Arithmetic Work ⋮ Computing Linear Extensions for Polynomial Posets Subject to Algebraic Constraints ⋮ Algorithms for finding generalized minimum aberration designs

Uses Software

• Unnamed Item
• Unnamed Item
• CPLEX
• QSopt_ex
• QSopt
• QSopt-Exact
• Performance Libraries

Cites Work

• Unnamed Item
• An efficient algorithm for the minimum capacity cut problem
• A linear programming bound for orthogonal arrays with mixed levels
• Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
• The final NETLIB-LP results
• Safe bounds in linear and mixed-integer linear programming
• Exact arithmetic at low cost. -- A case study in linear programming
• K-Cuts: A Variation of Gomory Mixed Integer Cuts from the LP Tableau
• Solving sparse linear equations over finite fields
• A Computational Study of Search Strategies for Mixed Integer Programming
• Rigorous Lower and Upper Bounds in Linear Programming
• Data Structures for Traveling Salesmen

This page was built for publication: Exact solutions to linear programming problems