# An Integer Linear Programming Model for Partially Ordered Sets

Authors: Elsayed Badr; I.M. Selim; Hoda Mostafa; Hala Attiya
Journal: Journal of Mathematics
 (2022)

---

## Abstract

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.


---

## Body

## 1. Introduction

Linear programming is a very rich problem-solving model which is used to represent a large class of optimization problems. Optimization problems are defined as problems whose solutions represent maximum values ​​(such as maximum profit) or minimum values ​​(such as minimum cost). There are various types of optimization problems such as constraint optimization problems and unconstraint optimization problems. On the other hand, there are many types according to the nature of the variables of the optimization problem, such as linear programming, integer linear programming, and nonlinear programming. There are various algorithms to solve linear programming problems, the most famous of which are the simplex algorithm and the interior point algorithm. The simplex algorithm is one of the ten best mathematics algorithms of the twentieth century [1]. By a common numerical example, Klee and Minty [2] proved that the simplex algorithm is not a polynomial time algorithm. Fortunately, this algorithm solves real-world problems of polynomial time complexity.Casting optimization problems into a linear program version is an art. The tools of this art are represented in the complete knowledge of the issue of optimization to be represented by a linear program. The second of these tools is the complete knowledge of the general form of the linear program (objective function–constraints–the right-hand side of the constraints (constants)–non-negative–etc). The third of these tools is the practice of formulating a set of optimization problems into a linear program version. For graph labeling problems, Badr et al. [3–5] introduced new integer linear programming models (ILPMs) to find the upper bounds of the radio number, a radio mean number, and radio mean square number for a given graph, respectively. The proposed ILPMs outperformed other algorithms according to the running time. For the metric dimension of a given graph, Chartrand et al [6] formulated the optimization problem of determining the metric dimension of a given graph (G). For the traveling salesman problem, there are different mathematical models [7–9] for the traveling salesman problems.The problem of efficient tasks scheduling is ubiquitous in many areas of computer science and engineering. We are often given a collection of tasks to complete, in which some jobs can be done in parallel, and others must be done in a predefined sequence. In general, we can formulate these problems by constructing a poset of objects (representing tasks) in which some elements are “comparable” (jobs that must be done in predefined sequence), and others are “incomparable” (jobs that can be done in parallel). If our goal is to devise an efficient task scheduling algorithm, we might be interested in finding the largest subset of tasks that can be completed in parallel (the maximum antichain problem). Or we may be interested in the related problem of distributing all the tasks between the fewest number of subgroups (e.g., for parallel processing) such that all jobs in a subgroup must be completed in a predefined sequence (the minimum chain covering problem).For more details about the history of the decomposition of the partially ordered sets posets, the reader can refer to [10–16]. On the other hand, for more details about how to formulate a problem as a mathematical model the reader is referred to [17–19]. Finally, for more details about the well know optimal PMU placement the reader is referred to [20–22].In this paper, a new integer linear programming model (ILPM) is proposed for posets. 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.The remaining of this paper is organized as follows: basic definitions and notations are introduced in Section2. In Section 3, Dilworth theorem and its mathematical formulation are proposed. In Section 4, the experimental results analysis of the proposed ILPM on fifteen benchmark posets are provided. In Section 5, conclusions are made.


## 2. Preliminaries

Before presenting Dilworth’s Theorem, we need to have a notion of comparability between elements in a set. To formalize this notion, we define some properties of binary relations to represent a partially ordered set (poset). We then illustrate how subsets of elements in a poset can have chain or antichain properties.


### 2.1. Binary Relations

Elements of a set can have relational properties such as transitivity or antisymmetry.Definition 1.
A binary relation,≺, on a set P is transitive if and only if (a ≺ b and b ≺ c) implies a ≺ c for all a, b, cϵPDefinition 2.
A binary relation≺ , on a set P is anti-symmetric if and only if (a ≠ b and a≺b) implies b ≺a for all a, bϵP.
We use binary relations with these specific properties to represent a partial order on a set of elements, in which some pairs of elements are comparable byai≺aj In context of a task scheduling problem, this means that job.ai must be completed before.Definition 3.
Apartially-ordered set, or poset, is a set of elements P, along with a binary relation ≺, having the property that ≺ is transitive and antisymmetric for all elements in P.
Note that, two elementsai and aj can also be incomparable, that is, when we have both ai⊀aj and aj⊀ai . In this case, tasks ai and aj may be completed in parallel.
We also define maximal and minimal elements in a poset:
An elementai is maximal in a subset S⊆P if it is not smaller than, any other element in S, i.e. ai⊀aj for all aj∈S . Similarly, an element ai is minimal S if it is not greater than any other element i.e. aj⊀ai for all ai∈S.Definition 4.
A subset of elements=a1,…,ak⊆P forms an antichain if and only if ai⊀aj for all i≠ j. That is all elements in A are pairwise incomparable.Definition 5.
A subset of elementsC=a1,…,ak⊆ Ƥ forms a chain if and only if they satisfy for all a1≺a2≺……≺ak for some ordering of elements in C. That is all elements in C are pairwise comparable.
For example, in a task scheduling problem, if a subset of jobs forms an antichain. Then, all these jobs may be completed in parallel. If a subset of jobs forms a chain, then these jobs must be completed in the sequence determined bya1≺a2≺……≺ak. Furthermore, it is useful to describe a covering of a poset P by chains to be a collection of chains C1,……,Ck such that every element of Ƥ is contained in the union of these chains, that is, ∪Ci=P. This is related to distributing all tasks on parallel processors C1,C2…… so that jobs assigned to any processor Ci are to be completed in a predefined sequence.


## 2.1. Binary Relations

Elements of a set can have relational properties such as transitivity or antisymmetry.Definition 1.
A binary relation,≺, on a set P is transitive if and only if (a ≺ b and b ≺ c) implies a ≺ c for all a, b, cϵPDefinition 2.
A binary relation≺ , on a set P is anti-symmetric if and only if (a ≠ b and a≺b) implies b ≺a for all a, bϵP.
We use binary relations with these specific properties to represent a partial order on a set of elements, in which some pairs of elements are comparable byai≺aj In context of a task scheduling problem, this means that job.ai must be completed before.Definition 3.
Apartially-ordered set, or poset, is a set of elements P, along with a binary relation ≺, having the property that ≺ is transitive and antisymmetric for all elements in P.
Note that, two elementsai and aj can also be incomparable, that is, when we have both ai⊀aj and aj⊀ai . In this case, tasks ai and aj may be completed in parallel.
We also define maximal and minimal elements in a poset:
An elementai is maximal in a subset S⊆P if it is not smaller than, any other element in S, i.e. ai⊀aj for all aj∈S . Similarly, an element ai is minimal S if it is not greater than any other element i.e. aj⊀ai for all ai∈S.Definition 4.
A subset of elements=a1,…,ak⊆P forms an antichain if and only if ai⊀aj for all i≠ j. That is all elements in A are pairwise incomparable.Definition 5.
A subset of elementsC=a1,…,ak⊆ Ƥ forms a chain if and only if they satisfy for all a1≺a2≺……≺ak for some ordering of elements in C. That is all elements in C are pairwise comparable.
For example, in a task scheduling problem, if a subset of jobs forms an antichain. Then, all these jobs may be completed in parallel. If a subset of jobs forms a chain, then these jobs must be completed in the sequence determined bya1≺a2≺……≺ak. Furthermore, it is useful to describe a covering of a poset P by chains to be a collection of chains C1,……,Ck such that every element of Ƥ is contained in the union of these chains, that is, ∪Ci=P. This is related to distributing all tasks on parallel processors C1,C2…… so that jobs assigned to any processor Ci are to be completed in a predefined sequence.


## 3. Dilworth’s Theorem

With these definitions in hand, we can now formulate Dilworth’s theorem [10] on the size of maximum antichains and minimum chain coverings in a poset.Theorem 1.
(Dilworth’s Theorem). The size of the largestantichain in any poset P is equal to the size of the minimum coverage of P by chains.
We can construct a proof of Dilworth’s theorem using the pigeonhole principle and Duality in linear programming. If we let:
A = max {A:A is antichain of Ƥ} (size of largest antichain in P), and B = min k:∪C1,……,Ck=P (minimum number of chains needed to cover P), then one way to prove Dilworth’s theorem is to show A≤B and B≤A.
To proveA≤B, we use the pigeonhole principle.Lemma 1.
The size of any chain in a posetP is equal to at most the minimum number of chains needed to cover P, i.e. A≤B.Proof.
As above-mentioned, letB be the minimum number of chains C1,……,CB needed to cover P. Assume, for the sake of contradiction, that an antichain A=a1,a2,…an in Ƥ has size n > B. Then, by the pigeonhole principle, at least two distinct elements ai, aj must be members of the same chain so that, by Definition 5, we have aiaj or ajai . However, by Definition 4, this means ai and aj are not in the same chain, a contradiction. Thus, no antichain in P can have size greater than B, whereby it follows the maximum size antichain in P is also no larger B.


### 3.1. Casting as a Linear Program

To proveB≤A A is more difficult. We can begin by trying to cast the objective of finding the maximum size antichain of a poset as a linear program.


#### 3.1.1. Primal Form

Assign non-negative weightsx⟶=x1,…,xn respectively to each element a1,……a1ϵP. Each chain Ck⊂Ρ will have an associated constrain inequality over the elements ai∈Ck that comprise it. Consider the following linear program in canonical form:(1)maxz=∑i=1nxi,s.t∑i:ai∈Ckxi≤1for all chainsCk⊆Ρx1≥0fori=1.……n..


#### 3.1.2. Dual Form

In addition, we can convert (1) to its dual form, where variables represent chains on P, and each element ai∈Ρ has an associated constrain inequality over the collection of chains that contain it (note the symmetry). Assign non-negative weights.y⟶=y1,…,yk, respectively, to each chains C1,…Ck⊆P. The dual of (1) (henceforth denoted (2)) is (2)Minimizew=∑j=1kyj,Subject to:∑j:ai∈Cjyj≥1for all elementsai∈Pyj≥0forj=1,…,k.We begin by showing that if the primal (1) and (2) have integer solutions, then the objective z in (1) gives the size of the maximum antichain in P, and the objective w in (2) gives the size of the minimum coverage of P by chains.Proposition 1.
Ifxiεℤ for all weights in x⟶, then solving primal (1) gives the maximum antichain in P.Proof.
In the case that allxi are non-negative integers, we wish to show that the objective of (1), z=∑i=1nxi , is equal to Amax, where Amax is any maximum antichain in P.
Observe that constrains in (1), ∑i:ai∈Ckxi≤1 for all chains Ck⊆P impose the following requirement on the variable xi if we assume they are all non-negative integers:Claim 1.
For all chainsCk⊆P, at most one of the weights associated with elements in Ck is equal to 1. All other weights must be 0.Proof of Claim 1.
For the sake of contradiction, assume that more than one element in chain C has a positive weight. We would then have∑i:aiεCxi>1 since all xi are non-negative integers, thereby violating constrains of the linear program.
It follows thatxi∈0,1 for all i. Now consider each xi as an indicator variable for whether element ai appears in an antichain Amax, i.e. let xi=1 if aiεAmax and xi=0 otherwise.
Since at most one indicator variable in any chain is positive, the solution to (1) satisfies the requirement that no two elements chosen for the maximum antichain come from the same chain.
Furthermore, under the indicator variable interpretation, the objective of maximizingz=∑xi corresponds to choosing the maximum number of elements to include in an antichain of P, so we have Maxz=Amax, as desired. This proves Proposition 1 that an integer solution to (1) gives the size of the maximum antichain in P.
Now, we prove the analogous proposition for the dual form.Proposition 2.
Ifyjεℤ for all weights in y⟶ then solving dual (2) gives the size of the minimum covering of P by chains.Proof.
The reasoning is analogous to that of Proposition1.
The constrains, in (2), ∑j:ai∈Cjyj≥1 for all elementsai∈P, impose the following requirement on variables yj if we assume they are all non-negative integers:Claim 2.
For allai∈P, at least one of weights associated with the set of chains containing ai is positive.Proof of Claim 2.
It follows immediately from the constrains. If, for some elementai, none of the weights associated with chains that contain ai are positive, then ∑j:ai∈Cjyj=0≯1, thereby violating the constrain of the linear program.
Furthermore, since the linear program seeks to minimize∑yj with all yj as integers, we must have that yj=1 whenever yj is chosen positive. Thus, with yjε0,1 for all j, we can again consider each yj as an indicator variable for whether chain Cj in a minimum covering of P.
Note again that for each elementai∈P, at least one indicator variable is associated with a chain containing ai equal 1, so the solution to (2) satisfies the requirement that all elements aεP appear in the minimum chain covering.
Furthermore, under the indicator variable interpretation, the objective of minimizingw=∑yj corresponds to choosing the minimum number of chains to include in a covering of P, so we have Minw=minc:C1,…,CccoversP, as desired. This proves Proposition 2 that an integer solution to (2) gives the minimum covering of P by chains.
Now, we need to show that both the primal and dual linear programs indeed have integer solutions.Lemma 2.
For any distribution of chains in a poset, (1) has an optimal solution where all variables take on integer values.Proof.
Proof is by the Well-ordering Principle and contradiction of an optimal solution to (1) with the fewest number of noninteger variables (xi weights). Let N be the set of elements in P corresponding to these noninteger weights. Some of these elements will be maximal in N, and others will be minimal (recall definitions in Section 2). We first need to verify that.Claim 3.
No elements inN can be both minimal and maximal.Proof of Claim 3.
Suppose, for the sake of contradiction, that an elementamεN is both minimal and maximal. Then, am is incomparable to all other elements in N (recall definitions in Section 2). It follows that is associated weight xm is subject only to a single constrain that xm≤1 in (1), whereby xm would be assigned a value of 1 to maximize the objective. This contradicts the assumption that xmεN is a not an integer, thus proving the claim.
Since no elements inN are both minimal and maximal, it follows that each chain C∈N has exactly one maximal element, and a different minimal element.
Suppose we add a small value∈>0 to each maximal element in N, and subtract e from each minimal in N. Since all elements in N are nonintegers we ensure that the resulting assignment of variables is feasible by choosing ∈>0 small enough so that 0≤xi≤1 is still satisfied by all xi , as required by the constraints of (1).
If we keep repeating this procedure, then at least one variable corresponding to a maximal/minimal element inN will reach a boundary value of 0 or 1. This contradicts the assumption that N has the fewest number of noninteger variables in a feasible solution. Thus, all variable assignments in an optimal solution to (1) must be integers, so Lemma 2 holds for primal (1). Next, we need to show that dual (2) also has integer solutions.Lemma 3.
For any distribution of chains in a poset, (2) has an optimal solution where all variables take on integer values.Proof.
First, we apply the result of strong duality in linear programming (see [19] for details). Which says that the primal and dual forms of a linear program have the same optimal value. We prove using induction that if kϵℤ is the optimal value to LP2 on a poset P, then P has a covering by k chains where all variables y⟶ in (2) take on integer values.
Inductive hypothesis: for any posetP having an integer optimal (2) objective value of k, the optimal solutions to the LPs associated with strict subsets of P are integers.
Base case. Consider a postP1 in which all elements form a single, with optimal objective value Minw=k=1. From the constraints of (2), this optimal solution will have a single variable y1 (corresponding to the chain containing all elements in P1) take on the value of 1, and the other y’s take on the value of 0. It follows that optimal solutions to each LP associated with subsets of P1 will also have integer weights. Thus, the inductive hypothesis holds for k=1.
Now, suppose that an optimal solution for (2) on poset P has a variable assignment yi=a that is not an integer (note that the optimal value for this LP must be an integer Minw=k∈ℤ). We can remove from P all elements in the chain Ci associated with variable yi to obtain a new poset P/C=P′⊂P.
Letw′ be the objective function value of LP2′ for this a new poset P′. We observe that Minw′ is at most k−a because all elements comprising the chain with weight yi=a were removed so that w′≤w−a=k−a. Since P′⊂P is a strict subset of P, k−a is an integer by the inductive hypothesis, so Minw′=k−1. Furthermore, the inductive hypothesis tells us that P′ has a covering by k−1 chains where all weights assignments to the chains are integers. It follows that we get a covering of P=P′∪Ci by k chains if we simply assign weight of yi=1 to Ci, achieving the desired objective the desired value of Minw=Minw′+yi=k+1+1=k. This completes the inductive argument and proof of Lemma 3.
Taking Lemma2 and 3 in conjunction with Proposition 1 and 2 gives the desired result that, for all partially-ordered sets P:Solving (1) gives the size of the largest antichain inPSolving (2) gives the size of the smallest covering ofP by chains
Again, by applying the result of strong duality [19] in linear programming, we conclude that primal (1) and dual (2) have the same optimal value. Therefore, (1) s solution for the size of the largest antichain in a poset and (2) solution for the size of the minimum chain covering of a poset are equal, proving Theorem 1 (Dilworth’s Theorem).


### 3.2. A Polynomial-Size Linear Program

In this section, we introduce Proposition3 on which the proposed integer linear programming model is based.Proposition 3.
An assignment of indicator values {0, 1} tox⟶=x1,…,xn produces an antichain if and only if xi+xj1 for all edges ai,aj∈EG.Proof.
First, we show that any antichain inP satisfies the constraints. An antichain cannot contain any two elements that are comparable (Definition 4). Note that, any two comparable elements in P are connected by an edge in G. Thus, we may choose at most one vertex from each edge ai,aj∈EG, meaning that at most one of xi , xj equals 1, from which it follows that xi+xj≤1 for all edges ai,aj∈EG.
Conversely, we show that any assignment of indicator variables satisfying the constraints produces a valid antichain.
Ifxi+xj≤1 for all edges ai,aj∈EG, then most one indicator variable xi , xj is positive because xi∈0,1. Hence, at most one vertex (element in P) on each edge is chosen to be in the antichain. Since all pairwise comparable elements in P are connected by edges in our construction of E(G), it follows that no two elements chosen in the antichain will be comparable, satisfying Definition 4. This proves Proposition 3.6.


#### 3.2.1. Formulation of the Problem as a Mathematical Model

For any posetP with element set a1,…,an, we can construct an n×n comparable incidence matrix A, having entry Ai,j=1 if elements ai,aj∈Pare comparable and Ai,j=0 otherwise. Now, associated with each element ai∈P an indicator variable xi∈0,1 that corresponds to using or not using that element in an antichain of P.Now, we can formulate the problem of the decomposed posetP as follows:(3)maxz=∑i=1nxi,Subject to:A∗x≤b:x1,x2,…,xn∈0,1,where A∗∈ℜm×n is the m×n matrix which is generated from the matrix A (based on Proposition 3) such that m is the number of ones in the matrix A, x∈ℜn and b∈ℜm (all elements in vector b equal to 1).Example 1.
We show how to formulate the problem of decomposed partially ordered set (as shown in Figure1) as an integer linear programming model.
Then×n comparable incidence matrix A that is corresponding to the post P.(4)A=000011000101000110000000000000000000.
Them×n matrix A∗∈ℜm×n is generated from matrix A:(5)A∗=100010100001010100010010001100001010.
Each row in the matrixA∗∈ℜm×n represents an inequality based on Proposition 3.7.
Finally, the complete integer linear programming model is as the following:(6)maxz=∑i=16xi,Subject to:x1000x50≤1x10000x6≤10x20x400≤10x200x50≤100x3x400≤100x3000≤1x1,x2,x3,x4,x5,x6∈0,1.
We can use an available software package such as (MATLAB, Python, and LINGO) for solving the above mathematical model which returns the solution is equal to three.Figure 1
A poset with 6 elements and its width equal to three.


## 3.1. Casting as a Linear Program

To proveB≤A A is more difficult. We can begin by trying to cast the objective of finding the maximum size antichain of a poset as a linear program.


### 3.1.1. Primal Form

Assign non-negative weightsx⟶=x1,…,xn respectively to each element a1,……a1ϵP. Each chain Ck⊂Ρ will have an associated constrain inequality over the elements ai∈Ck that comprise it. Consider the following linear program in canonical form:(1)maxz=∑i=1nxi,s.t∑i:ai∈Ckxi≤1for all chainsCk⊆Ρx1≥0fori=1.……n..


### 3.1.2. Dual Form

In addition, we can convert (1) to its dual form, where variables represent chains on P, and each element ai∈Ρ has an associated constrain inequality over the collection of chains that contain it (note the symmetry). Assign non-negative weights.y⟶=y1,…,yk, respectively, to each chains C1,…Ck⊆P. The dual of (1) (henceforth denoted (2)) is (2)Minimizew=∑j=1kyj,Subject to:∑j:ai∈Cjyj≥1for all elementsai∈Pyj≥0forj=1,…,k.We begin by showing that if the primal (1) and (2) have integer solutions, then the objective z in (1) gives the size of the maximum antichain in P, and the objective w in (2) gives the size of the minimum coverage of P by chains.Proposition 1.
Ifxiεℤ for all weights in x⟶, then solving primal (1) gives the maximum antichain in P.Proof.
In the case that allxi are non-negative integers, we wish to show that the objective of (1), z=∑i=1nxi , is equal to Amax, where Amax is any maximum antichain in P.
Observe that constrains in (1), ∑i:ai∈Ckxi≤1 for all chains Ck⊆P impose the following requirement on the variable xi if we assume they are all non-negative integers:Claim 1.
For all chainsCk⊆P, at most one of the weights associated with elements in Ck is equal to 1. All other weights must be 0.Proof of Claim 1.
For the sake of contradiction, assume that more than one element in chain C has a positive weight. We would then have∑i:aiεCxi>1 since all xi are non-negative integers, thereby violating constrains of the linear program.
It follows thatxi∈0,1 for all i. Now consider each xi as an indicator variable for whether element ai appears in an antichain Amax, i.e. let xi=1 if aiεAmax and xi=0 otherwise.
Since at most one indicator variable in any chain is positive, the solution to (1) satisfies the requirement that no two elements chosen for the maximum antichain come from the same chain.
Furthermore, under the indicator variable interpretation, the objective of maximizingz=∑xi corresponds to choosing the maximum number of elements to include in an antichain of P, so we have Maxz=Amax, as desired. This proves Proposition 1 that an integer solution to (1) gives the size of the maximum antichain in P.
Now, we prove the analogous proposition for the dual form.Proposition 2.
Ifyjεℤ for all weights in y⟶ then solving dual (2) gives the size of the minimum covering of P by chains.Proof.
The reasoning is analogous to that of Proposition1.
The constrains, in (2), ∑j:ai∈Cjyj≥1 for all elementsai∈P, impose the following requirement on variables yj if we assume they are all non-negative integers:Claim 2.
For allai∈P, at least one of weights associated with the set of chains containing ai is positive.Proof of Claim 2.
It follows immediately from the constrains. If, for some elementai, none of the weights associated with chains that contain ai are positive, then ∑j:ai∈Cjyj=0≯1, thereby violating the constrain of the linear program.
Furthermore, since the linear program seeks to minimize∑yj with all yj as integers, we must have that yj=1 whenever yj is chosen positive. Thus, with yjε0,1 for all j, we can again consider each yj as an indicator variable for whether chain Cj in a minimum covering of P.
Note again that for each elementai∈P, at least one indicator variable is associated with a chain containing ai equal 1, so the solution to (2) satisfies the requirement that all elements aεP appear in the minimum chain covering.
Furthermore, under the indicator variable interpretation, the objective of minimizingw=∑yj corresponds to choosing the minimum number of chains to include in a covering of P, so we have Minw=minc:C1,…,CccoversP, as desired. This proves Proposition 2 that an integer solution to (2) gives the minimum covering of P by chains.
Now, we need to show that both the primal and dual linear programs indeed have integer solutions.Lemma 2.
For any distribution of chains in a poset, (1) has an optimal solution where all variables take on integer values.Proof.
Proof is by the Well-ordering Principle and contradiction of an optimal solution to (1) with the fewest number of noninteger variables (xi weights). Let N be the set of elements in P corresponding to these noninteger weights. Some of these elements will be maximal in N, and others will be minimal (recall definitions in Section 2). We first need to verify that.Claim 3.
No elements inN can be both minimal and maximal.Proof of Claim 3.
Suppose, for the sake of contradiction, that an elementamεN is both minimal and maximal. Then, am is incomparable to all other elements in N (recall definitions in Section 2). It follows that is associated weight xm is subject only to a single constrain that xm≤1 in (1), whereby xm would be assigned a value of 1 to maximize the objective. This contradicts the assumption that xmεN is a not an integer, thus proving the claim.
Since no elements inN are both minimal and maximal, it follows that each chain C∈N has exactly one maximal element, and a different minimal element.
Suppose we add a small value∈>0 to each maximal element in N, and subtract e from each minimal in N. Since all elements in N are nonintegers we ensure that the resulting assignment of variables is feasible by choosing ∈>0 small enough so that 0≤xi≤1 is still satisfied by all xi , as required by the constraints of (1).
If we keep repeating this procedure, then at least one variable corresponding to a maximal/minimal element inN will reach a boundary value of 0 or 1. This contradicts the assumption that N has the fewest number of noninteger variables in a feasible solution. Thus, all variable assignments in an optimal solution to (1) must be integers, so Lemma 2 holds for primal (1). Next, we need to show that dual (2) also has integer solutions.Lemma 3.
For any distribution of chains in a poset, (2) has an optimal solution where all variables take on integer values.Proof.
First, we apply the result of strong duality in linear programming (see [19] for details). Which says that the primal and dual forms of a linear program have the same optimal value. We prove using induction that if kϵℤ is the optimal value to LP2 on a poset P, then P has a covering by k chains where all variables y⟶ in (2) take on integer values.
Inductive hypothesis: for any posetP having an integer optimal (2) objective value of k, the optimal solutions to the LPs associated with strict subsets of P are integers.
Base case. Consider a postP1 in which all elements form a single, with optimal objective value Minw=k=1. From the constraints of (2), this optimal solution will have a single variable y1 (corresponding to the chain containing all elements in P1) take on the value of 1, and the other y’s take on the value of 0. It follows that optimal solutions to each LP associated with subsets of P1 will also have integer weights. Thus, the inductive hypothesis holds for k=1.
Now, suppose that an optimal solution for (2) on poset P has a variable assignment yi=a that is not an integer (note that the optimal value for this LP must be an integer Minw=k∈ℤ). We can remove from P all elements in the chain Ci associated with variable yi to obtain a new poset P/C=P′⊂P.
Letw′ be the objective function value of LP2′ for this a new poset P′. We observe that Minw′ is at most k−a because all elements comprising the chain with weight yi=a were removed so that w′≤w−a=k−a. Since P′⊂P is a strict subset of P, k−a is an integer by the inductive hypothesis, so Minw′=k−1. Furthermore, the inductive hypothesis tells us that P′ has a covering by k−1 chains where all weights assignments to the chains are integers. It follows that we get a covering of P=P′∪Ci by k chains if we simply assign weight of yi=1 to Ci, achieving the desired objective the desired value of Minw=Minw′+yi=k+1+1=k. This completes the inductive argument and proof of Lemma 3.
Taking Lemma2 and 3 in conjunction with Proposition 1 and 2 gives the desired result that, for all partially-ordered sets P:Solving (1) gives the size of the largest antichain inPSolving (2) gives the size of the smallest covering ofP by chains
Again, by applying the result of strong duality [19] in linear programming, we conclude that primal (1) and dual (2) have the same optimal value. Therefore, (1) s solution for the size of the largest antichain in a poset and (2) solution for the size of the minimum chain covering of a poset are equal, proving Theorem 1 (Dilworth’s Theorem).


## 3.1.1. Primal Form

Assign non-negative weightsx⟶=x1,…,xn respectively to each element a1,……a1ϵP. Each chain Ck⊂Ρ will have an associated constrain inequality over the elements ai∈Ck that comprise it. Consider the following linear program in canonical form:(1)maxz=∑i=1nxi,s.t∑i:ai∈Ckxi≤1for all chainsCk⊆Ρx1≥0fori=1.……n..


## 3.1.2. Dual Form

In addition, we can convert (1) to its dual form, where variables represent chains on P, and each element ai∈Ρ has an associated constrain inequality over the collection of chains that contain it (note the symmetry). Assign non-negative weights.y⟶=y1,…,yk, respectively, to each chains C1,…Ck⊆P. The dual of (1) (henceforth denoted (2)) is (2)Minimizew=∑j=1kyj,Subject to:∑j:ai∈Cjyj≥1for all elementsai∈Pyj≥0forj=1,…,k.We begin by showing that if the primal (1) and (2) have integer solutions, then the objective z in (1) gives the size of the maximum antichain in P, and the objective w in (2) gives the size of the minimum coverage of P by chains.Proposition 1.
Ifxiεℤ for all weights in x⟶, then solving primal (1) gives the maximum antichain in P.Proof.
In the case that allxi are non-negative integers, we wish to show that the objective of (1), z=∑i=1nxi , is equal to Amax, where Amax is any maximum antichain in P.
Observe that constrains in (1), ∑i:ai∈Ckxi≤1 for all chains Ck⊆P impose the following requirement on the variable xi if we assume they are all non-negative integers:Claim 1.
For all chainsCk⊆P, at most one of the weights associated with elements in Ck is equal to 1. All other weights must be 0.Proof of Claim 1.
For the sake of contradiction, assume that more than one element in chain C has a positive weight. We would then have∑i:aiεCxi>1 since all xi are non-negative integers, thereby violating constrains of the linear program.
It follows thatxi∈0,1 for all i. Now consider each xi as an indicator variable for whether element ai appears in an antichain Amax, i.e. let xi=1 if aiεAmax and xi=0 otherwise.
Since at most one indicator variable in any chain is positive, the solution to (1) satisfies the requirement that no two elements chosen for the maximum antichain come from the same chain.
Furthermore, under the indicator variable interpretation, the objective of maximizingz=∑xi corresponds to choosing the maximum number of elements to include in an antichain of P, so we have Maxz=Amax, as desired. This proves Proposition 1 that an integer solution to (1) gives the size of the maximum antichain in P.
Now, we prove the analogous proposition for the dual form.Proposition 2.
Ifyjεℤ for all weights in y⟶ then solving dual (2) gives the size of the minimum covering of P by chains.Proof.
The reasoning is analogous to that of Proposition1.
The constrains, in (2), ∑j:ai∈Cjyj≥1 for all elementsai∈P, impose the following requirement on variables yj if we assume they are all non-negative integers:Claim 2.
For allai∈P, at least one of weights associated with the set of chains containing ai is positive.Proof of Claim 2.
It follows immediately from the constrains. If, for some elementai, none of the weights associated with chains that contain ai are positive, then ∑j:ai∈Cjyj=0≯1, thereby violating the constrain of the linear program.
Furthermore, since the linear program seeks to minimize∑yj with all yj as integers, we must have that yj=1 whenever yj is chosen positive. Thus, with yjε0,1 for all j, we can again consider each yj as an indicator variable for whether chain Cj in a minimum covering of P.
Note again that for each elementai∈P, at least one indicator variable is associated with a chain containing ai equal 1, so the solution to (2) satisfies the requirement that all elements aεP appear in the minimum chain covering.
Furthermore, under the indicator variable interpretation, the objective of minimizingw=∑yj corresponds to choosing the minimum number of chains to include in a covering of P, so we have Minw=minc:C1,…,CccoversP, as desired. This proves Proposition 2 that an integer solution to (2) gives the minimum covering of P by chains.
Now, we need to show that both the primal and dual linear programs indeed have integer solutions.Lemma 2.
For any distribution of chains in a poset, (1) has an optimal solution where all variables take on integer values.Proof.
Proof is by the Well-ordering Principle and contradiction of an optimal solution to (1) with the fewest number of noninteger variables (xi weights). Let N be the set of elements in P corresponding to these noninteger weights. Some of these elements will be maximal in N, and others will be minimal (recall definitions in Section 2). We first need to verify that.Claim 3.
No elements inN can be both minimal and maximal.Proof of Claim 3.
Suppose, for the sake of contradiction, that an elementamεN is both minimal and maximal. Then, am is incomparable to all other elements in N (recall definitions in Section 2). It follows that is associated weight xm is subject only to a single constrain that xm≤1 in (1), whereby xm would be assigned a value of 1 to maximize the objective. This contradicts the assumption that xmεN is a not an integer, thus proving the claim.
Since no elements inN are both minimal and maximal, it follows that each chain C∈N has exactly one maximal element, and a different minimal element.
Suppose we add a small value∈>0 to each maximal element in N, and subtract e from each minimal in N. Since all elements in N are nonintegers we ensure that the resulting assignment of variables is feasible by choosing ∈>0 small enough so that 0≤xi≤1 is still satisfied by all xi , as required by the constraints of (1).
If we keep repeating this procedure, then at least one variable corresponding to a maximal/minimal element inN will reach a boundary value of 0 or 1. This contradicts the assumption that N has the fewest number of noninteger variables in a feasible solution. Thus, all variable assignments in an optimal solution to (1) must be integers, so Lemma 2 holds for primal (1). Next, we need to show that dual (2) also has integer solutions.Lemma 3.
For any distribution of chains in a poset, (2) has an optimal solution where all variables take on integer values.Proof.
First, we apply the result of strong duality in linear programming (see [19] for details). Which says that the primal and dual forms of a linear program have the same optimal value. We prove using induction that if kϵℤ is the optimal value to LP2 on a poset P, then P has a covering by k chains where all variables y⟶ in (2) take on integer values.
Inductive hypothesis: for any posetP having an integer optimal (2) objective value of k, the optimal solutions to the LPs associated with strict subsets of P are integers.
Base case. Consider a postP1 in which all elements form a single, with optimal objective value Minw=k=1. From the constraints of (2), this optimal solution will have a single variable y1 (corresponding to the chain containing all elements in P1) take on the value of 1, and the other y’s take on the value of 0. It follows that optimal solutions to each LP associated with subsets of P1 will also have integer weights. Thus, the inductive hypothesis holds for k=1.
Now, suppose that an optimal solution for (2) on poset P has a variable assignment yi=a that is not an integer (note that the optimal value for this LP must be an integer Minw=k∈ℤ). We can remove from P all elements in the chain Ci associated with variable yi to obtain a new poset P/C=P′⊂P.
Letw′ be the objective function value of LP2′ for this a new poset P′. We observe that Minw′ is at most k−a because all elements comprising the chain with weight yi=a were removed so that w′≤w−a=k−a. Since P′⊂P is a strict subset of P, k−a is an integer by the inductive hypothesis, so Minw′=k−1. Furthermore, the inductive hypothesis tells us that P′ has a covering by k−1 chains where all weights assignments to the chains are integers. It follows that we get a covering of P=P′∪Ci by k chains if we simply assign weight of yi=1 to Ci, achieving the desired objective the desired value of Minw=Minw′+yi=k+1+1=k. This completes the inductive argument and proof of Lemma 3.
Taking Lemma2 and 3 in conjunction with Proposition 1 and 2 gives the desired result that, for all partially-ordered sets P:Solving (1) gives the size of the largest antichain inPSolving (2) gives the size of the smallest covering ofP by chains
Again, by applying the result of strong duality [19] in linear programming, we conclude that primal (1) and dual (2) have the same optimal value. Therefore, (1) s solution for the size of the largest antichain in a poset and (2) solution for the size of the minimum chain covering of a poset are equal, proving Theorem 1 (Dilworth’s Theorem).


## 3.2. A Polynomial-Size Linear Program

In this section, we introduce Proposition3 on which the proposed integer linear programming model is based.Proposition 3.
An assignment of indicator values {0, 1} tox⟶=x1,…,xn produces an antichain if and only if xi+xj1 for all edges ai,aj∈EG.Proof.
First, we show that any antichain inP satisfies the constraints. An antichain cannot contain any two elements that are comparable (Definition 4). Note that, any two comparable elements in P are connected by an edge in G. Thus, we may choose at most one vertex from each edge ai,aj∈EG, meaning that at most one of xi , xj equals 1, from which it follows that xi+xj≤1 for all edges ai,aj∈EG.
Conversely, we show that any assignment of indicator variables satisfying the constraints produces a valid antichain.
Ifxi+xj≤1 for all edges ai,aj∈EG, then most one indicator variable xi , xj is positive because xi∈0,1. Hence, at most one vertex (element in P) on each edge is chosen to be in the antichain. Since all pairwise comparable elements in P are connected by edges in our construction of E(G), it follows that no two elements chosen in the antichain will be comparable, satisfying Definition 4. This proves Proposition 3.6.


### 3.2.1. Formulation of the Problem as a Mathematical Model

For any posetP with element set a1,…,an, we can construct an n×n comparable incidence matrix A, having entry Ai,j=1 if elements ai,aj∈Pare comparable and Ai,j=0 otherwise. Now, associated with each element ai∈P an indicator variable xi∈0,1 that corresponds to using or not using that element in an antichain of P.Now, we can formulate the problem of the decomposed posetP as follows:(3)maxz=∑i=1nxi,Subject to:A∗x≤b:x1,x2,…,xn∈0,1,where A∗∈ℜm×n is the m×n matrix which is generated from the matrix A (based on Proposition 3) such that m is the number of ones in the matrix A, x∈ℜn and b∈ℜm (all elements in vector b equal to 1).Example 1.
We show how to formulate the problem of decomposed partially ordered set (as shown in Figure1) as an integer linear programming model.
Then×n comparable incidence matrix A that is corresponding to the post P.(4)A=000011000101000110000000000000000000.
Them×n matrix A∗∈ℜm×n is generated from matrix A:(5)A∗=100010100001010100010010001100001010.
Each row in the matrixA∗∈ℜm×n represents an inequality based on Proposition 3.7.
Finally, the complete integer linear programming model is as the following:(6)maxz=∑i=16xi,Subject to:x1000x50≤1x10000x6≤10x20x400≤10x200x50≤100x3x400≤100x3000≤1x1,x2,x3,x4,x5,x6∈0,1.
We can use an available software package such as (MATLAB, Python, and LINGO) for solving the above mathematical model which returns the solution is equal to three.Figure 1
A poset with 6 elements and its width equal to three.


## 3.2.1. Formulation of the Problem as a Mathematical Model

For any posetP with element set a1,…,an, we can construct an n×n comparable incidence matrix A, having entry Ai,j=1 if elements ai,aj∈Pare comparable and Ai,j=0 otherwise. Now, associated with each element ai∈P an indicator variable xi∈0,1 that corresponds to using or not using that element in an antichain of P.Now, we can formulate the problem of the decomposed posetP as follows:(3)maxz=∑i=1nxi,Subject to:A∗x≤b:x1,x2,…,xn∈0,1,where A∗∈ℜm×n is the m×n matrix which is generated from the matrix A (based on Proposition 3) such that m is the number of ones in the matrix A, x∈ℜn and b∈ℜm (all elements in vector b equal to 1).Example 1.
We show how to formulate the problem of decomposed partially ordered set (as shown in Figure1) as an integer linear programming model.
Then×n comparable incidence matrix A that is corresponding to the post P.(4)A=000011000101000110000000000000000000.
Them×n matrix A∗∈ℜm×n is generated from matrix A:(5)A∗=100010100001010100010010001100001010.
Each row in the matrixA∗∈ℜm×n represents an inequality based on Proposition 3.7.
Finally, the complete integer linear programming model is as the following:(6)maxz=∑i=16xi,Subject to:x1000x50≤1x10000x6≤10x20x400≤10x200x50≤100x3x400≤100x3000≤1x1,x2,x3,x4,x5,x6∈0,1.
We can use an available software package such as (MATLAB, Python, and LINGO) for solving the above mathematical model which returns the solution is equal to three.Figure 1
A poset with 6 elements and its width equal to three.


## 4. Computational Experiments

In this section, we evaluate the proposed ILPM by fifteen benchmark posets. These posets are characterized by some characteristics such as (various widthswP, various sizes (n), and various heights h(P)) Figure 2 contains fifteen benchmark posets with their width and jump number.Figure 2
15-Benchmark partially ordered sets with their width and jump number.The used environment is a 64-bit Windows 8.1 Operating System with Core (TM) i5 CPU M 460 @2.53 GHz, 4.00 GB of memory, and MATLAB v7.01 Software Package.From Table1 and Figure 3, it is obvious that the results of the proposed mathematical model (ILPM) coincide with the standard results for all fifteen benchmark posets.Table 1
A comparison between the standard width and directed acyclic graph (DAG).
PosetnStandardwPProposed model MATLABwPCPU timeP14220.073318P26220.089859P36220.101679P46330.102334P56330.104611P65330.108036P77330.123854P88330.146553P95330.166726P108440.207229P118440.328825P127440.471679P137440.47268P147440.546337P157440.649021Figure 3
Shows that the relation between posets and standard width, (DAG).It is also evident from Table1 and Figure 4 that the execution time of ILPM increases as the width of the poset increases. That is, the running time of ILPM is directly proportional to the width of the post. Fortunately, the behavior of the simplex algorithm used to solve ILPM is a polynomial time to solve real-world applications, regardless of being exponential time as proven in [2]. For this reason, we have done our best to create a poset in the form of the examples provided by Klee and Minty in 1972 in which they proved that the simplex algorithm is exponential time, but we have failed to do.Figure 4
Shows that the relation between posets and CPU Time.Because the examples presented by Klee and Minty depend on (right-hand side constants, the coefficients of the constraint matrix, and the coefficients of the objective function), rarely, do these problems exist as real-world problems. We conclude from this that the presented model will be implemented in a polynomial time. It is well-known that the complexity of the simplex algorithm isO(n2) for real-world applications in the average case where n is the number of elements of a poset.


## 5. Conclusion

A new integer linear programming model (ILPM) has been proposed for posets. Robert Dilworth’s Decomposition theorem is formulated by ILPM and proved 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 showed the validity of the proposed model. On the other hand, CPU Time has been calculated for fifteen benchmark partially ordered sets. From computational experiments, it was concluded that the CPU time increases as the width increases. In future work, the proposed ILPM will be evaluated by using special posets such as interval posets, lattice, crown posets, andk-tower poset. ILPM will be applied on the jump-critical ordered sets [23].



---

*Source: 7660174-2022-09-10.xml*