Primal-dual interior point method for linear programming based on a new wide neighborhood
| dc.contributor.author | LALOUNI , Zineb | |
| dc.contributor.author | NASRI , Assala | |
| dc.contributor.author | KETTAB , Samia Supervisor | |
| dc.date.accessioned | 2026-06-30T09:48:37Z | |
| dc.date.issued | 2026 | |
| dc.description | هذا العمل مخصص للدراسة النظرية و العددية لطرق النقاط الداخلية و بشكل اكثر دقة الخوارزميات الاولية -المرادفة للمسار المركزي في البرمجة الخطية. تشتهر هذه المقاربات بتعقيدها الحدودي وسرعة تقاربها وكفاءتها العددية. و قد تم اثراء هذه الطرق من خلال ادخال جوار كبير جديد طوره دارفاي عام 2018 . الخوارزمية المقترحة هي خوارزمية حدودية و تحقق افضل حد للتعقيد المعروف حتى الآن لطرق نقاط الداخلية المطبقة على البرمجة الخطية. واخيرا ختمت هذا المذكرة بتقديم دراسة عددية تبرز الفعالية العملية للمقاربة المقترحة | |
| dc.description.abstract | This work is devoted to the theoretical and numerical study of interior-point meth- ods, and more specifically, central-path primal-dual algorithms for linear program- ming. Recognized for their polynomial complexity, convergence rate, and numerical efficiency, these approaches are enhanced here by the introduction of a new large neighborhood developed by Darvay in 2018. The proposed algorithm is polynomial in time and achieves the best complexity bound known to date for interior-point methods applied to linear programming. Finally, this dissertation concludes with a numerical study that demonstrates the practical effectiveness of the proposed approach | |
| dc.description.sponsorship | Ce travail est consacré à l’étude théorique et numérique des méthodes des points intérieurs, et plus précisément des algorithmes primaux-duaux de trajectoire centrale pour la programmation linéaire. Reconnues pour leur complexité polynomiale, leur vitesse de convergence et leur efficacité numérique, ces approches sont ici enrichies par l’introduction d’un nouveau grand voisinage développé par Darvay en 2018. L’algo- rithme proposé est polynomial et atteint la meilleure borne de complexité connue à ce jour pour les méthodes de points intérieurs appliquées à la programmation linéaire. Enfin, ce mémoire se conclut par la présentation d’une étude numérique qui met en évidence l’efficacité pratique de l’approche proposée. | |
| dc.identifier.other | MAM/0856 | |
| dc.identifier.uri | https://repository.univ-setif.dz/handle/123456789/1655 | |
| dc.language.iso | en | |
| dc.publisher | Setif 1 Unuversity Ferhat Abbas . Faculty of Sciences | |
| dc.subject | Linear programming | |
| dc.subject | Interior point methods | |
| dc.subject | Large-step algorithm• Wide neighbourhood• Polynomial complexity | |
| dc.title | Primal-dual interior point method for linear programming based on a new wide neighborhood | |
| dc.type | Thesis |