Παράλληλος προγραμματισμός αλγόριθμων για προβλήματα γραμμικού προγραμματισμού

Περίληψη

Η μέθοδος Simplex, η δημοφιλέστερη μέθοδος για τα γραμμικά προγράμματα (LPs), έχει δύο σημαντικές παραλλαγές. Είναι η αναθεωρημένη μορφή η μορφή του πλήρους tableau ή πλήρους πίνακα. Σήμερα, ουσιαστικά όλες οι σημαντικές υλοποιήσεις χρησιμοποιούν την αναθεωρημένη μορφή επειδή είναι περισσότερο αποτελεσματική σε αραιά LPs που είναι τα πιο κοινά. Ωστόσο, η μέθοδος έχει επίσης πλεονεκτήματα. Κατ' αρχήν, ο πλήρης πίνακας μπορεί να είναι πολύ αποτελεσματικός για τα πυκνά προβλήματα. Δεύτερον, η μέθοδος του πλήρη πίνακα μπορεί εύκολα και αποτελεσματικά να επεκταθεί σε έναν κατανεμημένο αλγόριθμο. Ενώ τα πυκνά προβλήματα συναντιούνται σπάνια στην πράξη , εμφανίζονται συχνά σε μερικές σημαντικές εφαρμογές όπως στον ψηφιακό σχεδιασμό φίλτρων, την κατηγοριοποίηση κειμένων, την επεξεργασία εικόνας και την επίλυση προβλημάτων χρονοδρομολόγησης με τη μέθοδο των χαλαρώσεων των περιορισμών. Υλοποιούμε δύο αλγορίθμους πλήρους πίνακα. Ο πρώτος, μια σειριακή εφαρμογή, είναι αποτελεσματικός για μικρά κα ...
περισσότερα

Περίληψη σε άλλη γλώσσα

The Simplex Method, the most popular method for solving Linear Programs (LPs), has two major variants. They are the revised method and the standard, or full tableau method. Today, virtually all serious implementations are of the revised method because it is more efficient for sparse LPs which are the most common. However, the full tableau method has advantages as well. First, the full tableau can be very effective for dense problems. Second, a full tableau method can easily and effectively be extended to a coarse grained distributed algorithm. While dense problems are uncommon in general, they occur frequently in some important applications such as digital filter design, text categorization, image processing and relaxations of scheduling problems. We implement two full tableau algorithms. The first, a serial implementation, is effective for small to moderately sized dense problems. The second, a simple extension of the first, is a distributed algorithm. We implement an algorithm which ...
περισσότερα
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/14246
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/14246
Εναλλακτικός τίτλος
Parallel progrmming algorithms for linear programming problems
Συγγραφέας
Badr, El-Said
Ημερομηνία
2006
Ίδρυμα
Πανεπιστήμιο Μακεδονίας Οικονομικών και Κοινωνικών Επιστημών. Τμήμα Εφαρμοσμένης Πληροφορικής
Εξεταστική επιτροπή
Παπαρρίζος Κωνσταντίνος
Μαργαρίτης Κωνσταντίνος
Σατρατζέμη Μαρία
Επιστημονικό πεδίο
Φυσικές Επιστήμες
Επιστήμες Ηλεκτρονικών Υπολογιστών & Πληροφορικής
Λέξεις-κλειδιά
Γραμμικός προγραμματισμός; Αλγόριθμος Simplex; Παράλληλος προγραμματισμός
Χώρα
Ελλάδα
Γλώσσα
Ελληνικά
Άλλα στοιχεία
149 σ., εικ.