subject:(Exterior point algorithms)

1. Triantafyllidis, Charalampos. A non-monotonic infleasible interior-exterior point algorithm for linear programming.

Degree: 2013, Πανεπιστήμιο Μακεδονίας

URL: http://hdl.handle.net/10442/hedi/36838

►

The vast majority of Linear Programming algorithms restrict the use of any vertex as starting basis, into being either primal feasible, dual feasible, or even… (more)

▼

The vast majority of Linear Programming algorithms restrict the use of any vertex as starting basis, into being either primal feasible, dual feasible, or even both (Primal – Dual Two path pivoting algorithms). A reasonably large amount of research has been conducted the latest decades to relax these limitations. Exterior Point algorithms, originally designed from Paparrizos K. differ versus the traditional pivoting algorithms in the sense that they construct primal infeasible bases as well along with the feasible ones. It looks ambiguous whether it would be impractical to combine exterior with interior point methods. This paper presents a variant of the exterior point algorithmic family for the linear problem, iEPSA, in an attempt to shed light upon this ambiguity. It can be considered as a generalization of this type of algorithms, since it does not suffer from feasibility criteria on the starting vertex and in parallel it was educed by two already known LP algorithms. To expunge an algorithm though from these restrictions, translates to a partially non-monotonic design, which is rather than a facile task. It embodies interior, primal and dual ingredients, all together mixed into a hybrid algorithm. We compare its practical effectiveness against the IPM (Interior Point Method) of MOSEK optimization package implemented for the computational environment of MATLAB-R2012b. The results extrapolate a significant implication that in some cases, a combination of interior-exterior methods is considerably more efficient. This comes to gainsay with the up-to-date information we have about the state-of-the-art LP solvers.

Η συντριπτική πλειοψηφία των αλγορίθμων γραμμικού προγραμματισμούπεριορίζουν τη χρήση οποιασδήποτε κορυφής ως βάσης ξεκινήματος , είτε στονα είναι πρωτεύων εφικτή , δυικά εφικτή ή ακόμα και τα δύο μαζί. Έναςαρκετά μεγάλος όγκος έρευνας έχει διεξαχθεί τις τελευταίες δεκαετίες γιανα χαλαρώσουν οι περιορισμοί αυτοί. Οι αλγόριθμοι εξωτερικών σημείων,αρχικά σχεδιασμένοι από τον κ. Παπαρρίζο Κ. [99] διαφέρουν σε σχέση μετις παραδοσιακές οικογένειες περιστροφικών αλγορίθμων υπό την έννοια ότικατασκευάζουν μη-εφικτές βάσεις μαζί με τις εφικτές. Φαίνεται διφορούμενοαν θα ήταν πρακτικό να συνδυαστούν οι περιστροφικοί αλγόριθμοι εξωτερικώνσημείων με μεθόδους εσωτερικών σημείων. Αυτή η εργασία παρουσιάζει μιαπαραλλαγή του αλγορίθμου εξωτερικών σημείων για το γραμμικό πρόβλημα , τονiEPSA , σε μια προσπάθεια να ρίξει φως επάνω σε αυτήν την ασάφεια . Μπορείνα θεωρηθεί ως γενίκευση αυτού του τύπου των αλγορίθμων , δεδομένου ότιδεν πάσχει από κριτήρια εφικτότητας σχετικά με την πρώτη κορυφή καιπαράλληλα έχει εξαχθεί από δύο ήδη γνωστούς αλγορίθμους ΓραμμικούΠρογραμματισμού. Για να αποδεσμεύουμε έναν αλγόριθμο όμως από αυτούς τουςπεριορισμούς, απαιτείται μια μερικώς μη - μονοτονική σχεδίαση, ένα καθόλουεύκολο έργο. Εμπεριέχει εσωτερικά , πρωτεύων και δυικά στοιχεία πουαναμιγνύονται όλα μαζί σε ένα υβριδικό αλγόριθμο. Συγκρίνουμε τηνπρακτική του αποτελεσματικότητα κατά της μεθόδου εσωτερικών σημείων τουεμπορικού πακέτου…

Subjects/Keywords: Γραμμικός προγραμματισμός; Αλγόριθμοι εξωτερικών σημείων; Υπολογιστική επιχειρησιακή έρευνα; Linear programming; Exterior-point algorithms; Computational operations research

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Triantafyllidis, C. (2013). A non-monotonic infleasible interior-exterior point algorithm for linear programming. (Thesis). Πανεπιστήμιο Μακεδονίας. Retrieved from http://hdl.handle.net/10442/hedi/36838

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Triantafyllidis, Charalampos. “A non-monotonic infleasible interior-exterior point algorithm for linear programming.” 2013. Thesis, Πανεπιστήμιο Μακεδονίας. Accessed December 09, 2019. http://hdl.handle.net/10442/hedi/36838.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Triantafyllidis, Charalampos. “A non-monotonic infleasible interior-exterior point algorithm for linear programming.” 2013. Web. 09 Dec 2019.

Vancouver:

Triantafyllidis C. A non-monotonic infleasible interior-exterior point algorithm for linear programming. [Internet] [Thesis]. Πανεπιστήμιο Μακεδονίας; 2013. [cited 2019 Dec 09]. Available from: http://hdl.handle.net/10442/hedi/36838.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Triantafyllidis C. A non-monotonic infleasible interior-exterior point algorithm for linear programming. [Thesis]. Πανεπιστήμιο Μακεδονίας; 2013. Available from: http://hdl.handle.net/10442/hedi/36838

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

2. Geranis, Georgios. A dual network exterior point simplex-type algorithm for the minimum cost network flow problem.

Degree: 2012, University of Macedonia Economic and Social Sciences; Πανεπιστήμιο Μακεδονίας Οικονομικών και Κοινωνικών Επιστημών

URL: http://hdl.handle.net/10442/hedi/28548

► The Minimum Cost Network Flow Problem (MCNFP) refers to a wide category of network flow problems and it is an important research area of Network… (more)

Subjects/Keywords: Αλγόριθμος τύπου simplex; Αλγόριθμος δικτυακού προγραμματισμού; Πρόβλημα ροής ελάχιστου κόστους; Βελτιστοποίηση δικτύων; ΠΡΕΚ; Simplex type algorithms; Exterior point algorithms; Minimum cost network flow problem; MCNFP

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Geranis, G. (2012). A dual network exterior point simplex-type algorithm for the minimum cost network flow problem. (Thesis). University of Macedonia Economic and Social Sciences; Πανεπιστήμιο Μακεδονίας Οικονομικών και Κοινωνικών Επιστημών. Retrieved from http://hdl.handle.net/10442/hedi/28548

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Geranis, Georgios. “A dual network exterior point simplex-type algorithm for the minimum cost network flow problem.” 2012. Thesis, University of Macedonia Economic and Social Sciences; Πανεπιστήμιο Μακεδονίας Οικονομικών και Κοινωνικών Επιστημών. Accessed December 09, 2019. http://hdl.handle.net/10442/hedi/28548.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Geranis, Georgios. “A dual network exterior point simplex-type algorithm for the minimum cost network flow problem.” 2012. Web. 09 Dec 2019.

Vancouver:

Geranis G. A dual network exterior point simplex-type algorithm for the minimum cost network flow problem. [Internet] [Thesis]. University of Macedonia Economic and Social Sciences; Πανεπιστήμιο Μακεδονίας Οικονομικών και Κοινωνικών Επιστημών; 2012. [cited 2019 Dec 09]. Available from: http://hdl.handle.net/10442/hedi/28548.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Geranis G. A dual network exterior point simplex-type algorithm for the minimum cost network flow problem. [Thesis]. University of Macedonia Economic and Social Sciences; Πανεπιστήμιο Μακεδονίας Οικονομικών και Κοινωνικών Επιστημών; 2012. Available from: http://hdl.handle.net/10442/hedi/28548

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

3. Samaras, Nikolaos. Υπολογιστικές βελτιώσεις και αποτελεσματική υλοποίηση περιστροφικών αλγορίθμων δύο δρόμων.

Degree: 2001, University of Macedonia Economic and Social Sciences; Πανεπιστήμιο Μακεδονίας Οικονομικών και Κοινωνικών Επιστημών

URL: http://hdl.handle.net/10442/hedi/30472

►

Linear Programming deals with the optimization (minimization or maximization) of an objective function under certain linear (equality or inequality) constraints. Great progress has been made… (more)

▼

Linear Programming deals with the optimization (minimization or maximization) of an objective function under certain linear (equality or inequality) constraints. Great progress has been made in mathematical programming since the introduction of the simplex algorithm in 1947 by Dantzig. Researchers' interest turned to polynomial complexity algorithms in order to solve large-scale linear problems since the moment that the worst-case complexity of the simplex algorithm proved to be exponential. In the early 1990s, a new class of simplex type algorithms appeared in the international bibliography. The algorithms of this class are called exterior point or two-path algorithms. The first paper, in which an exterior point algorithm was presented, published in 1991 by Paparrizos. The primal exterior point algorithm has two main computational drawbacks: 1.It is difficult to construct "good moving directions". The two paths depend on the initial feasible direction and the initial feasible vertex. 2.There is no known way of moving into the interior of the feasible region. This movement achieves the search for computationally good directions.Forcing the exterior path of an exterior point algorithm to become a dual feasible simplex path results in an algorithm free of the above-mentioned computational drawbacks.In this thesis, a computational improvement of the primal dual two-path simplex algorithm proposed by Paparrizos is presented. More specifically, the new algorithm that was implemented moves in the interior of the feasible region and not in its' frontier. Moving to the interior of the feasible region results in an algorithm free of the stalling and cycling phenomena. Extensive computations studies were conducted in order to study the practical effectiveness of the algorithm. More specifically, three different computational studies were conducted. Presolve techniques, scaling techniques, tolerances and explicit inverse of the basis when needed were applied in order to solve large-scale linear problems. In the computational studies, the problems that were used are randomly generated sparse linear problems with a dual feasible initial basic solution, randomly generated sparse linear problems with an initial basic solution that is neither primal nor dual feasible and benchmark linear problems (www.netlib.org). The computational results for the new algorithm are encouraging. More specifically, in randomly generated sparse linear problems of size 1200x1200 with an initial basic solution that is neither primal nor dual feasible and density 2.5%, 5% and 10%, the new algorithm is 169, 126 and 128 times faster than the original simplex algorithm and 1.16, 1.10 and 1.15 times faster than the primal dual two-path simplex algorithm, respectively. This improvement is translated to CPU time as follows. The new algorithm is 108, 97 and 98 times faster than the original simplex algorithm and 1.14, 1.08 and 1.17 times faster than the primal dual two-path simplex algorithm, respectively.

Ο Γραμμικός Προγραμματισμός ασχολείται με τη…

Subjects/Keywords: Γραμμικός προγραμματισμός; Αλγόριθμοι τύπου Simplex; Αλγόριθμοι εξωτερικών σημείων; Υπολογιστική μελέτη; Linear programming; Simplex type algorithms; Exterior point algorithms; Computational study

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Samaras, N. (2001). Υπολογιστικές βελτιώσεις και αποτελεσματική υλοποίηση περιστροφικών αλγορίθμων δύο δρόμων. (Thesis). University of Macedonia Economic and Social Sciences; Πανεπιστήμιο Μακεδονίας Οικονομικών και Κοινωνικών Επιστημών. Retrieved from http://hdl.handle.net/10442/hedi/30472

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Samaras, Nikolaos. “Υπολογιστικές βελτιώσεις και αποτελεσματική υλοποίηση περιστροφικών αλγορίθμων δύο δρόμων.” 2001. Thesis, University of Macedonia Economic and Social Sciences; Πανεπιστήμιο Μακεδονίας Οικονομικών και Κοινωνικών Επιστημών. Accessed December 09, 2019. http://hdl.handle.net/10442/hedi/30472.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Samaras, Nikolaos. “Υπολογιστικές βελτιώσεις και αποτελεσματική υλοποίηση περιστροφικών αλγορίθμων δύο δρόμων.” 2001. Web. 09 Dec 2019.

Vancouver:

Samaras N. Υπολογιστικές βελτιώσεις και αποτελεσματική υλοποίηση περιστροφικών αλγορίθμων δύο δρόμων. [Internet] [Thesis]. University of Macedonia Economic and Social Sciences; Πανεπιστήμιο Μακεδονίας Οικονομικών και Κοινωνικών Επιστημών; 2001. [cited 2019 Dec 09]. Available from: http://hdl.handle.net/10442/hedi/30472.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Samaras N. Υπολογιστικές βελτιώσεις και αποτελεσματική υλοποίηση περιστροφικών αλγορίθμων δύο δρόμων. [Thesis]. University of Macedonia Economic and Social Sciences; Πανεπιστήμιο Μακεδονίας Οικονομικών και Κοινωνικών Επιστημών; 2001. Available from: http://hdl.handle.net/10442/hedi/30472

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

4. Σιφαλέρας, Άγγελος. Ανάπτυξη και υλοποίηση αλγόριθμων εξωτερικών σημείων τύπου simplex για προβλήματα δικτυακής βελτιστοποίησης.

Degree: 2006, University of Macedonia Economic and Social Sciences; Πανεπιστήμιο Μακεδονίας Οικονομικών και Κοινωνικών Επιστημών

URL: http://hdl.handle.net/10442/hedi/14452

Subjects/Keywords: Δικτυακή βελτιστοποίηση; Αλγόριθμοι εξωτερικών σημείων τύπου simplex; Πρόβλημα ροής ελάχιστου κόστους; Υπολογιστικές μελέτες; Μαθηματικός προγραμματισμός; Σχεδίαση αλγορίθμων; Ανάλυση αλγορίθμων; Δομές δεδομένων; Εκπαιδευτικό λογισμικό; Network optimization; Exterior point simplex type algorithms; Minimum cost network flow problem; Computational studies; Mathematical programming; Algorithms design; Algorithms analysis; Data structures; Educational software

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Σιφαλέρας, . �. (2006). Ανάπτυξη και υλοποίηση αλγόριθμων εξωτερικών σημείων τύπου simplex για προβλήματα δικτυακής βελτιστοποίησης. (Thesis). University of Macedonia Economic and Social Sciences; Πανεπιστήμιο Μακεδονίας Οικονομικών και Κοινωνικών Επιστημών. Retrieved from http://hdl.handle.net/10442/hedi/14452

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Σιφαλέρας, Άγγελος. “Ανάπτυξη και υλοποίηση αλγόριθμων εξωτερικών σημείων τύπου simplex για προβλήματα δικτυακής βελτιστοποίησης.” 2006. Thesis, University of Macedonia Economic and Social Sciences; Πανεπιστήμιο Μακεδονίας Οικονομικών και Κοινωνικών Επιστημών. Accessed December 09, 2019. http://hdl.handle.net/10442/hedi/14452.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Σιφαλέρας, Άγγελος. “Ανάπτυξη και υλοποίηση αλγόριθμων εξωτερικών σημείων τύπου simplex για προβλήματα δικτυακής βελτιστοποίησης.” 2006. Web. 09 Dec 2019.

Vancouver:

Σιφαλέρας �. Ανάπτυξη και υλοποίηση αλγόριθμων εξωτερικών σημείων τύπου simplex για προβλήματα δικτυακής βελτιστοποίησης. [Internet] [Thesis]. University of Macedonia Economic and Social Sciences; Πανεπιστήμιο Μακεδονίας Οικονομικών και Κοινωνικών Επιστημών; 2006. [cited 2019 Dec 09]. Available from: http://hdl.handle.net/10442/hedi/14452.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Σιφαλέρας �. Ανάπτυξη και υλοποίηση αλγόριθμων εξωτερικών σημείων τύπου simplex για προβλήματα δικτυακής βελτιστοποίησης. [Thesis]. University of Macedonia Economic and Social Sciences; Πανεπιστήμιο Μακεδονίας Οικονομικών και Κοινωνικών Επιστημών; 2006. Available from: http://hdl.handle.net/10442/hedi/14452

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

		in
And / Or
		in
And / Or
		in
And / Or
		in

Open Access Theses and Dissertations