A non-monotonic infleasible interior-exterior point algorithm for linear programming

Abstract

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 , σε μια προσπάθεια να ρίξει φως επάνω σε αυτήν την ασάφεια . Μπορείνα θεωρηθεί ως γενίκευση αυτού του τύπου των αλγορίθμων , δεδομένου ότιδεν πάσχει από κριτήρια εφικτότητας σχετικά με την πρώτη κορυφή καιπαράλληλα έχει εξαχθεί από δύο ήδη γνωστούς αλγορίθμους ΓραμμικούΠρογραμματισμού. Για να αποδεσμεύουμε έναν αλγόριθμο όμως από αυτούς τουςπεριορισμούς, απαιτείται μια μερικώς μη - μονοτονική σχεδίαση, ένα καθόλουεύκολο έργο. Εμπεριέχει εσωτερικά , πρωτεύων και δυικά στοιχεία πουαναμιγνύονται όλα μαζί σε ένα υβριδικό αλγόριθμο. Συγκρίνουμε τηνπρακτική του αποτελεσματικότητα κατά της μεθόδου εσωτερικών σημείων τουεμπορικού πακέτου βελτιστοποίησης MOSEK, υλοποιημένο για το υπολογιστικόπεριβάλλον του MATLAB - R2012b . Τα αποτελέσματα υποδηλώνουν ότι σεορισμένες περιπτώσεις ένας συνδυασμός εσωτερικών – εξωτερικώνμεθόδων είναι σημαντικά πιο αποτελεσματικός. Αυτό έρχεται να διαψεύσει τιςσημερινές πληροφορίες που έχουμε για τους πιο αποτελεσματικούς λύτες.