An infeasible (exterior point) simplex algorithm for assignment problems

DOI10.1007/BF01586925zbMath0734.90055OpenAlexW2058062905MaRDI QIDQ811357

Konstantinos Paparrizos

Publication date: 1991

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01586925

zbMATH Keywords

assignmentexterior point simplex methodinfeasible paths

Mathematics Subject Classification ID

Linear programming (90C05) Discrete location and assignment (90B80) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Three nearly scaling-invariant versions of an exterior point algorithm for linear programming ⋮ An improved initial basis for the simplex algorithm ⋮ A new algorithm for the assignment problem: An alternative to the Hungarian method ⋮ Resolution of the problem of degeneracy in a primal and dual simplex algorithm ⋮ On the initialization methods of an exterior point algorithm for the assignment problem ⋮ Efficient GPU-based implementations of simplex type algorithms ⋮ Worst case examples of an exterior point algorithm for the assignment problem ⋮ Exterior point simplex-type algorithms for linear and network optimization problems ⋮ Improving a primal–dual simplex-type algorithm using interior point methods ⋮ An exterior simplex type algorithm for the minimum cost network flow problem ⋮ Computational experience with exterior point algorithms for the transportation problem ⋮ Hybrid-LP: finding advanced starting points for simplex, and pivoting LP methods ⋮ The complex interior-boundary method for linear and nonlinear programming with linear constraints ⋮ On using exterior penalty approaches for solving linear programming problems ⋮ An efficient simplex type algorithm for sparse and dense linear programs. ⋮ A space decomposition-based deterministic algorithm for solving linear optimization problems ⋮ Pivot rules for linear programming: A survey on recent theoretical developments ⋮ An exterior point simplex algorithm for (general) linear programming problems ⋮ Advances in discrete optimization ⋮ An experimental investigation of a primal–dual exterior point simplexalgorithm ⋮ A comprehensive simplex-like algorithm for network optimization and perturbation analysis ⋮ A new efficient primal dual simplex algorithm

Cites Work

• Unnamed Item
• A Suggested Computation for Maximal Multi-Commodity Network Flows
• The Hirsch Conjecture for Dual Transportation Polyhedra
• Signature Methods for the Assignment Problem
• Scarf's Procedure for Integer Programming and a Dual Simplex Algorithm
• A competitive (dual) simplex method for the assignment problem
• Transportation problems which can be solved by the use of hirsch-paths for the dual problems
• A non-dual signature method for the assignment problem and a generalization of the dual simplex method for the transportation problem
• Solving the Assignment Problem by Relaxation
• A network simplex method
• The alternating basis algorithm for assignment problems