Premium
Vector processing approach to constrained network problems
Author(s) -
Venkataramana M. A.,
Dinkel John J.,
Mote John
Publication year - 1991
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199102)38:1<71::aid-nav3220380108>3.0.co;2-6
Subject(s) - computer science , vectorization (mathematics) , mathematical optimization , constraint (computer aided design) , scalar (mathematics) , algorithm , theoretical computer science , mathematics , parallel computing , geometry
Modification of algorithms designed for scalar computing, to take advantage of vector processing, raises several challenges. This article presents the vectorization of the primal simplex based network algorithm and results in a 50% improvement in computational time. One of the major contributors to this improvement is the matching of the size of the pricing candidate list to the vector register size. The side constraints are relaxed into a single surrogate constraint. The single constraint network algorithm is vectorized and used as the basis for solving large‐scale constrained network problems. Computational experiments are presented which illustrate the vectorization of the network code as well as the ability of the surrogate constraint approach to deal with large constrained network problems.