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...

Full description

Saved in:
Bibliographic Details
Main Authors: Elsayed Badr, I.M. Selim, Hoda Mostafa, Hala Attiya
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!
Description
Summary: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.
ISSN:2314-4785