An Integer Linear Programming Model for Partially Ordered Sets
Linear programming is an important approach that is used to represent a large class of combinatorial optimization problems. The simplex algorithm is one of the algorithms for solving linear programming problems with exponential time complexity. Fortunately, this algorithm solves real-world problems...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2022-01-01
|
| Series: | Journal of Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2022/7660174 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832562356286128128 |
|---|---|
| author | Elsayed Badr I.M. Selim Hoda Mostafa Hala Attiya |
| author_facet | Elsayed Badr I.M. Selim Hoda Mostafa Hala Attiya |
| author_sort | Elsayed Badr |
| collection | DOAJ |
| description | Linear programming is an important approach that is used to represent a large class of combinatorial optimization problems. The simplex algorithm is one of the algorithms for solving linear programming problems with exponential time complexity. Fortunately, this algorithm solves real-world problems with polynomial time complexity. In particular, a new Integer Linear Programming model (ILPM) is proposed for partially ordered sets. Robert Dilworth’s Decomposition theorem is formulated by ILPM and proves its correctness using the paradigm of strong duality in linear programming. Finally, ILPM is run on fifteen benchmark partially ordered sets for finding their width. The computational experiments show the validity of the proposed model. |
| format | Article |
| id | doaj-art-5407e2b918c3492fa7cf5eb4f67a99dc |
| institution | Kabale University |
| issn | 2314-4785 |
| language | English |
| publishDate | 2022-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Mathematics |
| spelling | doaj-art-5407e2b918c3492fa7cf5eb4f67a99dc2025-02-03T01:22:48ZengWileyJournal of Mathematics2314-47852022-01-01202210.1155/2022/7660174An Integer Linear Programming Model for Partially Ordered SetsElsayed Badr0I.M. Selim1Hoda Mostafa2Hala Attiya3Scientific Computing DepartmentComputing Science DepartmentMathematics and Computer Science DepartmentBasic Science DepartmentLinear programming is an important approach that is used to represent a large class of combinatorial optimization problems. The simplex algorithm is one of the algorithms for solving linear programming problems with exponential time complexity. Fortunately, this algorithm solves real-world problems with polynomial time complexity. In particular, a new Integer Linear Programming model (ILPM) is proposed for partially ordered sets. Robert Dilworth’s Decomposition theorem is formulated by ILPM and proves its correctness using the paradigm of strong duality in linear programming. Finally, ILPM is run on fifteen benchmark partially ordered sets for finding their width. The computational experiments show the validity of the proposed model.http://dx.doi.org/10.1155/2022/7660174 |
| spellingShingle | Elsayed Badr I.M. Selim Hoda Mostafa Hala Attiya An Integer Linear Programming Model for Partially Ordered Sets Journal of Mathematics |
| title | An Integer Linear Programming Model for Partially Ordered Sets |
| title_full | An Integer Linear Programming Model for Partially Ordered Sets |
| title_fullStr | An Integer Linear Programming Model for Partially Ordered Sets |
| title_full_unstemmed | An Integer Linear Programming Model for Partially Ordered Sets |
| title_short | An Integer Linear Programming Model for Partially Ordered Sets |
| title_sort | integer linear programming model for partially ordered sets |
| url | http://dx.doi.org/10.1155/2022/7660174 |
| work_keys_str_mv | AT elsayedbadr anintegerlinearprogrammingmodelforpartiallyorderedsets AT imselim anintegerlinearprogrammingmodelforpartiallyorderedsets AT hodamostafa anintegerlinearprogrammingmodelforpartiallyorderedsets AT halaattiya anintegerlinearprogrammingmodelforpartiallyorderedsets AT elsayedbadr integerlinearprogrammingmodelforpartiallyorderedsets AT imselim integerlinearprogrammingmodelforpartiallyorderedsets AT hodamostafa integerlinearprogrammingmodelforpartiallyorderedsets AT halaattiya integerlinearprogrammingmodelforpartiallyorderedsets |