An Integer Linear Programming Model for Partially Ordered Sets
Copyright policy )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 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.
- Bani-Suef University Egypt
- Beni-Suef University Egypt
- Scienion (Germany) Germany
- Menoufia University Egypt
- University of Sadat City Egypt
Criss-cross algorithm, Computational Complexity, Optical Code Division Multiple Access, Engineering, Linear-fractional programming, Linear programming, QA1-939, FOS: Electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Electrical and Electronic Engineering, Graph Labeling and Dimension Problems, Mathematical optimization, Integer programming, Discrete mathematics, Branch and cut, Algorithm, Computational Theory and Mathematics, Branch and price, Time complexity, Fixed-Parameter Algorithms, Duality (order theory), Computer Science, Physical Sciences, Simplex algorithm, Linear programming relaxation, Correctness, Approximation Algorithms, Mathematics, Graph Theory and Algorithms, Parameterized Complexity
Criss-cross algorithm, Computational Complexity, Optical Code Division Multiple Access, Engineering, Linear-fractional programming, Linear programming, QA1-939, FOS: Electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Electrical and Electronic Engineering, Graph Labeling and Dimension Problems, Mathematical optimization, Integer programming, Discrete mathematics, Branch and cut, Algorithm, Computational Theory and Mathematics, Branch and price, Time complexity, Fixed-Parameter Algorithms, Duality (order theory), Computer Science, Physical Sciences, Simplex algorithm, Linear programming relaxation, Correctness, Approximation Algorithms, Mathematics, Graph Theory and Algorithms, Parameterized Complexity
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).3 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!