Exterior point simplex-type algorithms for linear and network optimization problems

DOI10.1007/S10479-014-1769-1zbMATH Open1318.90062DBLPjournals/anor/PaparrizosSS15OpenAlexW2076410055WikidataQ57780875 ScholiaQ57780875MaRDI QIDQ492840FDOQ492840

Authors: Konstantinos Paparrizos, Nikolaos Samaras, Angelo Sifaleras 

Publication date: 21 August 2015

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-014-1769-1

Recommendations

• An exterior point simplex algorithm for (general) linear programming problems
• scientific article; zbMATH DE number 710572
• A Phase I That Solves Transportation Problems
• A dual exterior point simplex type algorithm for the minimum cost network flow problem
• Computational experience with exterior point algorithms for the transportation problem

zbMATH Keywords

linear programmingmathematical programmingnetwork flowsexterior point simplex-type algorithms

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Cites Work

• Network flows. Theory, algorithms, and applications.
• TSPLIB—A Traveling Salesman Problem Library
• The Simplex Method for Quadratic Programming
• Title not available (Why is that?)
• A new polynomial-time algorithm for linear programming
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• Assignment Problems
• A polynomial time primal network simplex algorithm for minimum cost flows
• The linear complementarity problem, sufficient matrices, and the criss- cross method
• Title not available (Why is that?)
• The stepping stone method of explaining linear programming calculations in transportation problems
• A feasible direction method for linear programming
• Pivot rules for linear programming: A survey on recent theoretical developments
• Computational techniques of the simplex method
• New Finite Pivoting Rules for the Simplex Method
• A new efficient primal dual simplex algorithm
• The \(s\)-monotone index selection rules for pivot algorithms of linear programming
• A Monotonic Build-Up Simplex Algorithm for Linear Programming
• On strongly polynomial variants of the MBU-simplex algorithm for a maximum flow problem with non-zero lower bounds
• Anstreicher–Terlaky type monotonic simplex algorithms for linear feasibility problems
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
• Title not available (Why is that?)
• A largest-distance pivot rule for the simplex algorithm
• Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
• Criss-cross methods: A fresh view on pivot algorithms
• On the existence of a short admissible pivot sequence for feasibility and linear optimization problems
• A convergent criss-cross method
• A new proof for the criss-cross method for quadratic programming
• A simple direct cosine simplex algorithm
• The Criss-Cross Method for Solving Linear Programming Problems
• The Average number of pivot steps required by the Simplex-Method is polynomial
• On the finiteness of the criss-cross method
• The generalized simplex method
• An exterior point simplex algorithm for (general) linear programming problems
• The simplex algorithm with a new primal and dual pivot rule
• A new strongly polynomial dual network simplex algorithm
• EP theorems and linear complementarity problems
• On dual minimum cost flow algorithms
• Pivot versus interior point methods: Pros and cons
• New variants of finite criss-cross pivot algorithms for linear programming
• The finite criss-cross method for hyperbolic programming
• An efficient simplex type algorithm for sparse and dense linear programs.
• A relaxation column signature method for assignment problems
• New variants of the criss-cross method for linearly constrained convex quadratic programming
• You want them to remember? Then make it memorable! Means for enhancing operations research education
• A hybrid gradient and feasible direction pivotal solution algorithm for general linear programs
• A basis-deficiency-allowing primal phase-I algorithm using the most-obtuse-angle column rule
• An exterior-point method for linear programming problems
• A computer implementation of the push-and-pull algorithm and its computational comparison with LP simplex method
• The role of pivoting in proving some fundamental theorems of linear algebra
• A fast simplex algorithm for linear programming
• On a dual network exterior point simplex type algorithm and its computational behavior
• Three nearly scaling-invariant versions of an exterior point algorithm for linear programming
• A new analysis for monotonic type simplex algorithms for feasibility problems
• A deficient-basis dual counterpart of Paparrizos, Samaras and Stephanides’ primal-dual simplex-type algorithm†
• A primal-dual exterior point algorithm for linear programming problems
• A dual exterior point simplex type algorithm for the minimum cost network flow problem
• Technical Note—A Polynomial Simplex Method for the Assignment Problem
• Efficient dual simplex algorithms for the assignment problem
• Signature Methods for the Assignment Problem
• Threshold assignment algorithm
• A non-dual signature method for the assignment problem and a generalization of the dual simplex method for the transportation problem
• A Simplex-Type Algorithm for General Transportation Problems: An Alternative to Stepping-Stone
• Title not available (Why is that?)
• The Scaling Network Simplex Algorithm
• An Advanced Dual Basic Feasible Solution for a Class of Capacitated Generalized Networks
• Title not available (Why is that?)
• Some generalizations of the criss-cross method for quadratic programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A non improving simplex algorithm for transportation problems
• An Investigation of Interior-Point Algorithms for the Linear Transportation Problem
• A parametric visualization software for the assignment problem
• The s-monotone index selection rule for criss-cross algorithms of linear complementarity problems
• Efficient Shortest Path Simplex Algorithms
• Minimum cost network flows: Problems, algorithms, and software
• Computational aspects of simplex and MBU-simplex algorithms using different anti-cycling pivot rules
• New criss-cross type algorithms for linear complementarity problems with sufficient matrices
• Letters to the Editor—Extension of Dantzig's Algorithm to Finding an Initial Near-Optimal Basis for the Transportation Problem
• Basic Dual Feasible Solutions for a Class of Generalized Networks
• Some Empirical Tests of the Criss-Cross Method
• Title not available (Why is that?)
• On the initialization methods of an exterior point algorithm for the assignment problem
• Programming of Interdependent Activities: II Mathematical Model
• On using exterior penalty approaches for solving linear programming problems
• A genuinely polynomial primal simplex algorithm for the assignment problem
• Exterior point algorithms for nearest points and convex quadratic programs
• A primal-dual simplex method for linear programs
• Polynomial dual network simplex algorithms
• Computational experience with exterior point algorithms for the transportation problem
• An infeasible (exterior point) simplex algorithm for assignment problems
• Efficient GPU-based implementations of simplex type algorithms
• An exponential example for Terlaky's pivoting rule for the criss-cross simplex method
• Worst case examples of an exterior point algorithm for the assignment problem
• An exterior simplex type algorithm for the minimum cost network flow problem
• The complex interior-boundary method for linear and nonlinear programming with linear constraints

Cited In (9)

• Simpler analysis of LP extreme points for traveling salesman and survivable network design problems
• Title not available (Why is that?)
• Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems
• Improving a primal–dual simplex-type algorithm using interior point methods
• An exterior point method for the convex programming problem
• Title not available (Why is that?)
• Computational experience with exterior point algorithms for the transportation problem
• A space decomposition-based deterministic algorithm for solving linear optimization problems
• An exterior point simplex algorithm for (general) linear programming problems

Uses Software

• TSPLIB
• MIPLIB

This page was built for publication: Exterior point simplex-type algorithms for linear and network optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q492840)