An implementation of steepest-descent augmentation for linear programs

DOI10.1016/j.orl.2020.04.004OpenAlexW3016896652MaRDI QIDQ2183215

Steffen Borgwardt, Charles Viss

Publication date: 26 May 2020

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

Full work available at URL: https://arxiv.org/abs/1911.08636

zbMATH Keywords

linear programmingpolyhedracircuits

Mathematics Subject Classification ID

Numerical analysis (65-XX) Operations research, mathematical programming (90-XX)

Related Items (4)

On circuit diameter bounds via circuit imbalances ⋮ Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs ⋮ Constructing Clustering Transformations ⋮ A note on the approximability of deepest-descent circuit steps

Uses Software

• Gurobi
• NETLIB LP Test Set

Cites Work

• Unnamed Item
• Quadratic diameter bounds for dual network flow polyhedra
• On the diameter of partition polytopes and vertex-disjoint cycle cover
• A polynomial oracle-time algorithm for convex integer minimization
• On the computational behavior of a polynomial-time network flow algorithm
• The final NETLIB-LP results
• Edges versus circuits: a hierarchy of diameters in polyhedra
• The hierarchy of circuit diameters and transportation polytopes
• \(n\)-fold integer programming in cubic time
• Circuit walks in integral polyhedra
• On the Circuit Diameter of Dual Transportation Polyhedra
• On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
• On the foundations of linear and integer linear programming I
• On the Circuit Diameter of Some Combinatorial Polytopes
• Vector Space Decomposition for Solving Large-Scale Linear Programs
• Good Clusterings Have Large Volume

This page was built for publication: An implementation of steepest-descent augmentation for linear programs