Παρακαλώ χρησιμοποιήστε αυτό το αναγνωριστικό για να παραπέμψετε ή να δημιουργήσετε σύνδεσμο προς αυτό το τεκμήριο:
https://ruomo.lib.uom.gr/handle/7000/1537
Τίτλος: | A triangulation and fill-reducing initialization procedure for the simplex algorithm |
Συγγραφείς: | Ploskas, Nikolaos Sahinidis, Nikolaos V. Samaras, Nikolaos |
Τύπος: | Article |
Θέματα: | FRASCATI::Natural sciences::Computer and information sciences FRASCATI::Natural sciences::Mathematics::Applied Mathematics |
Λέξεις-Κλειδιά: | Linear programming Revised simplex algorithm Initial basis Crash procedure |
Ημερομηνία Έκδοσης: | 2021 |
Εκδότης: | Springer |
Πηγή: | Mathematical Programming Computation |
Τόμος: | 13 |
Τεύχος: | 3 |
Πρώτη Σελίδα: | 491 |
Τελευταία Σελίδα: | 508 |
Επιτομή: | 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. |
URI: | https://doi.org/10.1007/s12532-020-00188-1 https://ruomo.lib.uom.gr/handle/7000/1537 |
ISSN: | 1867-2949 1867-2957 |
Αλλοι Προσδιοριστές: | 10.1007/s12532-020-00188-1 |
Εμφανίζεται στις Συλλογές: | Τμήμα Εφαρμοσμένης Πληροφορικής |
Αρχεία σε αυτό το Τεκμήριο:
Αρχείο | Περιγραφή | Μέγεθος | Μορφότυπος | |
---|---|---|---|---|
crash.pdf | 4,14 MB | Adobe PDF | Προβολή/Ανοιγμα |
Αυτό το τεκμήριο προστατεύεται από Αδεια Creative Commons