Please use this identifier to cite or link to this item:
Title: A triangulation and fill-reducing initialization procedure for the simplex algorithm
Authors: Ploskas, Nikolaos
Sahinidis, Nikolaos V.
Samaras, Nikolaos
Type: Article
Subjects: FRASCATI::Natural sciences::Computer and information sciences
FRASCATI::Natural sciences::Mathematics::Applied Mathematics
Keywords: Linear programming
Revised simplex algorithm
Initial basis
Crash procedure
Issue Date: 2021
Publisher: Springer
Source: Mathematical Programming Computation
Volume: 13
Issue: 3
First Page: 491
Last Page: 508
Abstract: The computation of an initial basis is of great importance for simplex algorithms since it determines to a large extent the number of iterations and the computational effort needed to solve linear programs. We propose three algorithms that aim to construct an initial basis that is sparse and will reduce the fill-in and computational effort during LU factorization and updates that are utilized in modern simplex implementations. The algorithms rely on triangulation and fill-reducing ordering techniques that are invoked prior to LU factorization. We compare the performance of the CPLEX 12.6.1 primal and dual simplex algorithms using the proposed starting bases against CPLEX using its default crash procedure over a set of 95 large benchmarks (NETLIB, Kennington, Mészáros, Mittelmann). The best proposed algorithm utilizes METIS (Karypis and Kumar in SIAM J Sci Comput 20:359–392, 1998), produces remarkably sparse starting bases, and results in 5% reduction of the geometric mean of the execution time of CPLEX’s primal simplex algorithm. Although the proposed algorithm improves CPLEX’s primal simplex algorithm across all problem types studied in this paper, it performs better on hard problems, i.e., the instances for which the CPLEX default requires over 1000 s. For these problems, the proposed algorithm results in 37% reduction of the geometric mean of the execution time of CPLEX’s primal simplex algorithm. The proposed algorithm also reduces the execution time of CPLEX’s dual simplex on hard instances by 10%. For the instances that are most difficult for CPLEX, and for which CPLEX experiences numerical difficulties as it approaches the optimal solution, the best proposed algorithm speeds up CPLEX by more than 10 times. Finally, the proposed algorithms lead to a natural way to parallelize CPLEX with speedups over CPLEX’s dual simplex of 1.2 and 1.3 on two and four cores, respectively.
ISSN: 1867-2949
Other Identifiers: 10.1007/s12532-020-00188-1
Appears in Collections:Department of Applied Informatics

Files in This Item:
File Description SizeFormat 
crash.pdf4,14 MBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons