Published April 25, 2022
| Version v1
Publication
Open
An Exact Algorithm Based on the Kuhn–Tucker Conditions for Solving Linear Generalized Semi-Infinite Programming Problems
Description
Optimization problems containing a finite number of variables and an infinite number of constraints are called semi-infinite programming problems. Under certain conditions, a class of these problems can be represented as bi-level programming problems. Bi-level problems are a particular class of optimization problems, in which there is another optimization problem embedded in one of the constraints. We reformulate a semi-infinite problem into a bi-level problem and then into a single-level nonlinear one by using the Kuhn–Tucker optimality conditions. The resulting reformulation allows us to employ a branch and bound scheme to optimally solve the problem. Computational experimentation over well-known instances shows the effectiveness of the developed method concluding that it is able to effectively solve linear semi-infinite programming problems. Additionally, some linear bi-level problems from literature are used to validate the robustness of the proposed algorithm.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
تسمى مشاكل التحسين التي تحتوي على عدد محدود من المتغيرات وعدد لا حصر له من القيود بمشاكل البرمجة شبه اللانهائية. في ظل ظروف معينة، يمكن تمثيل فئة من هذه المشكلات على أنها مشكلات برمجة ثنائية المستوى. المشكلات ثنائية المستوى هي فئة معينة من مشكلات التحسين، حيث توجد مشكلة تحسين أخرى مضمنة في أحد القيود. نعيد صياغة مشكلة شبه لا نهائية في مشكلة ثنائية المستوى ثم في مشكلة غير خطية أحادية المستوى باستخدام شروط كون تاكر المثلى. تسمح لنا إعادة الصياغة الناتجة بتوظيف مخطط فرعي وملزم لحل المشكلة على النحو الأمثل. تُظهر التجارب الحسابية على الحالات المعروفة فعالية الطريقة المطورة التي تستنتج أنها قادرة على حل مشاكل البرمجة الخطية شبه اللانهائية بشكل فعال. بالإضافة إلى ذلك، يتم استخدام بعض المشكلات الخطية ثنائية المستوى من الأدبيات للتحقق من قوة الخوارزمية المقترحة.Translated Description (French)
Les problèmes d'optimisation contenant un nombre fini de variables et un nombre infini de contraintes sont appelés problèmes de programmation semi-infinis. Dans certaines conditions, une classe de ces problèmes peut être représentée comme des problèmes de programmation à deux niveaux. Les problèmes à deux niveaux sont une classe particulière de problèmes d'optimisation, dans laquelle il existe un autre problème d'optimisation intégré dans l'une des contraintes. Nous reformulons un problème semi-infini en un problème à deux niveaux, puis en un problème non linéaire à un seul niveau en utilisant les conditions d'optimalité de Kuhn–Tucker. La reformulation qui en résulte nous permet d'utiliser un schéma de branche et lié pour résoudre le problème de manière optimale. L'expérimentation informatique sur des instances bien connues montre l'efficacité de la méthode développée concluant qu'elle est capable de résoudre efficacement des problèmes de programmation linéaire semi-infinie. De plus, certains problèmes linéaires à deux niveaux de la littérature sont utilisés pour valider la robustesse de l'algorithme proposé.Translated Description (Spanish)
Los problemas de optimización que contienen un número finito de variables y un número infinito de restricciones se denominan problemas de programación semiinfinitos. Bajo ciertas condiciones, una clase de estos problemas puede representarse como problemas de programación de dos niveles. Los problemas de dos niveles son una clase particular de problemas de optimización, en los que hay otro problema de optimización incrustado en una de las restricciones. Reformulamos un problema semiinfinito en un problema de dos niveles y luego en uno no lineal de un solo nivel utilizando las condiciones de optimalidad de Kuhn–Tucker. La reformulación resultante nos permite emplear un esquema de ramificación y encuadernación para resolver el problema de manera óptima. La experimentación computacional sobre instancias bien conocidas muestra la efectividad del método desarrollado concluyendo que es capaz de resolver eficazmente problemas de programación lineal semi-infinita. Además, se utilizan algunos problemas lineales de dos niveles de la literatura para validar la solidez del algoritmo propuesto.Files
1765385.pdf.pdf
Files
(15.9 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:cc68141fcd5e270434773873b1e0cf5b
|
15.9 kB | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- خوارزمية دقيقة تستند إلى شروط كون تاكر لحل مشاكل البرمجة الخطية المعممة شبه اللانهائية
- Translated title (French)
- Un algorithme exact basé sur les conditions de Kuhn–Tucker pour résoudre les problèmes de programmation linéaire généralisée semi-infinie
- Translated title (Spanish)
- Un Algoritmo Exacto Basado en las Condiciones de Kuhn–Tucker para Resolver Problemas Lineales Generalizados de Programación Semi-Infinita
Identifiers
- Other
- https://openalex.org/W4224307636
- DOI
- 10.1155/2022/1765385
References
- https://openalex.org/W137390859
- https://openalex.org/W1588628884
- https://openalex.org/W1970596092
- https://openalex.org/W2013786427
- https://openalex.org/W2034728596
- https://openalex.org/W2048922416
- https://openalex.org/W2053353266
- https://openalex.org/W2065385799
- https://openalex.org/W2075887074
- https://openalex.org/W2088111670
- https://openalex.org/W2102529199
- https://openalex.org/W2127277876
- https://openalex.org/W2481910659
- https://openalex.org/W2614367549
- https://openalex.org/W2775458963
- https://openalex.org/W2786878090
- https://openalex.org/W2799838365
- https://openalex.org/W2811476252
- https://openalex.org/W2903672366
- https://openalex.org/W2982639800
- https://openalex.org/W3009684019
- https://openalex.org/W3195475456
- https://openalex.org/W4214631981
- https://openalex.org/W83112366