An Integer Linear Programming Model for Partially Ordered Sets

被引：3

作者：

Badr, Elsayed ^{[1
]}

Selim, I. M. ^{[2
]}

Mostafa, Hoda ^{[3
]}

Attiya, Hala ^{[4
]}

机构：

[1] Benha Univ, Fac Comp & Artificial Intelligence, Sci Comp Dept, Banha, Egypt

[2] Univ Sadat City, Fac Comp & Artificial Intelligence, Comp Sci Dept, Sadat City, Egypt

[3] Fac Sci Menoufia Univ, Math & Comp Sci Dept, Shibin Al Kawm, Egypt

[4] Beni Suef Univ, Fac Technol & Educ, Basic Sci Dept, Bani Suwayf, Egypt

来源：

JOURNAL OF MATHEMATICS | 2022年 / 2022卷

关键词：

PHASOR MEASUREMENT UNITS; PLACEMENT;

D O I：

10.1155/2022/7660174

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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.

引用

页数：9

共 23 条

[1]

[Anonymous], 2002, Traveling Salesman Problems and its Variations

[2]

Badr E., 2014, J ADV APPL COMPUTATI, V1, P8, DOI [10.15377/2409-5761.2014.01.01.2, DOI 10.15377/2409-5761.2014.01.01.2]

[3]

Badr E.M., 2020, INDONESIAN J ELECT E, V19, P492, DOI [10.11591/ijeecs.v19.i1.pp492-504, DOI 10.11591/IJEECS.V19.I1.PP492-504]

[4] A Novel Mathematical Model for Radio Mean Square Labeling Problem [J].

Badr, Elsayed ;

Nada, Shokry ;

Ali Al-Shamiri, Mohammed M. ;

Abdel-Hay, Atef ;

ELrokh, Ashraf .

JOURNAL OF MATHEMATICS, 2022, 2022

[5] An Integer Linear Programming Model for Solving Radio Mean Labeling Problem [J].

Badr, Elsayed ;

Almotairi, Sultan ;

Eirokh, Ashraf ;

Abdel-Hay, Atef ;

Almutairi, Badr .

IEEE ACCESS, 2020, 8 :162343-162349

[6] On a Dual Direct Cosine Simplex Type Algorithm and Its Computational Behavior [J].

Badr, Elsayed ;

Almotairi, Sultan .

MATHEMATICAL PROBLEMS IN ENGINEERING, 2020, 2020

[7] An upper bound of radiok-coloring problem and its integer linear programming model [J].

Badr, Elsayed M. ;

Moussa, Mahmoud I. .

WIRELESS NETWORKS, 2020, 26 (07) :4955-4964

[8]

Bazaraa MS., 2010, Linear programming and network flows, V4

[9]

By Barry A Cipra., 2000, SIAM News, V33, P20

[10] Resolvability in graphs and the metric dimension of a graph [J].

Chartrand, G ;

Eroh, L ;

Johnson, MA ;

Oellermann, OR .

DISCRETE APPLIED MATHEMATICS, 2000, 105 (1-3) :99-113

← 1 2 3 →