SIAM Journal on Optimization · 1993 · 58 citations · 17 references
Natural SciencesComputer ScienceAlgorithmsOptimizationParallel ComputingAssignment ProblemsCombinatorial OptimizationConvex OptimizationDiscrete OptimizationLinear ProgrammingNetwork FlowsBipartite NetworksDegeneracyDegeneracy ReductionInterior-point Methods For FlowMinimum Cost FlowMinimum-cost Flow AlgorithmsMinimum-cost Flow ProblemNetwork Flow Problems
This paper describes an implementation of the dual affine scaling algorithm for linear programming specialized to solve minimum-cost flow problems on bipartite uncapacitated networks. This implementation uses a preconditioned conjugate gradient algorithm to solve the system of linear equations that determines the search direction at each iteration of the interior point algorithm. Two preconditioners are considered: a diagonal preconditioner and a preconditioner based on the incidence matrix of an approximate maximum weighted spanning tree of the network. Under dual nondegeneracy this spanning tree allows for early identification of the optimal solution. By applying an $\epsilon $-perturbation to the cost vector, an optimal extreme-point primal solution is produced in the presence of dual degeneracy. The implementation is tested by solving several large instances of randomly generated assignment problems, comparing solution times with the network simplex code NETFLO and the relaxation algorithm code RELAX. This interior point algorithm greatly benefits from implementation in a parallel architecture. For the largest instances tested the interior point code was competitive with both the simplex and relaxation codes.
17
An implementation of Karmarkar's algorithm for linear programming
Ilan Adler, Maurício G. C. Resende, Geraldo Veiga et al. · Mathematical Programming · 1989 · 422 citations
A new algorithm for the assignment problem
Dimitri P. Bertsekas · Mathematical Programming · 1981 · 291 citations