# On a Dual Direct Cosine Simplex Type Algorithm and Its Computational Behavior

Authors: Elsayed Badr; Sultan Almotairi
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

The goal of this paper is to propose a dual version of the direct cosine simplex algorithm (DDCA) for general linear problems. The proposed method has not artificial variables, so it is different from both the two-phase method and big-M method. Our technique solves the dual Klee–Minty problem via two iterations and solves the dual Clausen problem via four iterations. The power of the proposed algorithm is evident from the extensive experimental results on benchmark problems adapted from NETLIB. Preliminary results indicate that this dual direct cosine simplex algorithm (DDCA) reduces the number of iterations of the two-phase method.


---

## Body

## 1. Introduction

Linear programming plays an important role in the optimization theory. Many real-world problems can be formulated as linear or nonlinear mathematical models. The simplex method is the common tool for solving linear programs. It is an iterative method that was developed by Dantzig [1–3].There are many pivot rules for the simplex-type algorithm such as the exterior point simplex algorithm [4–6], primal-dual exterior point algorithm [7], and max-out-in pivot rule [8]. It is known that the application of the simplex algorithm requires at least one basic feasible solution. On the other hand, the common techniques that are used for determining an initial feasible basis are the two-phase and big-M methods. The main drawback of these techniques lies in requiring the introduction of artificial variables and increasing the dimension of the problem. Corley et al. [9] introduced the cosine simplex algorithm for solving linear programs. Yeh and Corley [10] proposed a simple direct cosine simplex algorithm (DCA) which solves the Klee–Minty Problem [11] via two iterations. They deduced that their algorithm reduced the number of iterations of simplex in most cases in their experimental results. Li and Li [12] explained the relationship between the cosine pivot rule and the most-obtuse-angle pivot rule, proposed by Pan [13]. In this paper, we propose a dual version of a simple direct cosine simplex algorithm (DDCA) which solves the dual Klee–Minty class of problems via two iterations while the two-phase method solves this class in n+1 iterations where n is the size of the problem. Our technique also solves Clausen class of problems via four iterations, but the two-phase method solves this class in 2n-1 iterations where n is the size of the problem. Our technique does not require the introduction of artificial variables.The rest of the paper is organized as follows. Section2 describes the proposed DDCA algorithm and its characteristics. Benchmark problems “Klee–Minty and Clausen problems” are presented in Section 3. In Section 4, we introduce illustrations of the proposed method with two examples. Computational experiments are proposed in Section 5. Finally, conclusions and future work are proposed in Section 6.


## 2. Dual Cosine Simplex Algorithm (DDCA)

We consider the linear programming (LP) problem in standard form:P
max
b
T
y
:
A
T
y
=
c
;
y
≥
0, where A is an m×n matrix, x and c are n-dimensional vectors, and T denotes transposition. The dual of (P) is the problem.D
min
c
T
x
:
A
x
≥
b,where y is an m-dimensional vector.For constrainti of (D), define cosθi=∑j∈Naijcj2/∑j∈Naij2 as the cosine of angle θi between the constraints i and the objective function where bi < 0 and N is the index set of the nonbasic variables (Algorithm1).Algorithm 1: Dual cosine simplex method (DCSM).
Require: infeasible basis
While
b
i < 0
Step 1 (dual feasibility condition): let N is the index set of the nonbasic variables. The leaving variable, xi, is the basic variable having the maximum cosθi for minimization problem, where cosθi=∑j∈Naijcj2/∑j∈Naij2 is the angle between the constraint i and the objective function. The tie is broken by choosing the most negative value in the right hand side.
Step 2 (dual optimality condition): given that xi is the leaving variable, the entering variable is the nonbasic variable aij < 0 that corresponds to minbi/aij:aij<0andj∈N The ties are broken arbitrary. If aij≥0 for all nonbasic variables, then the problem has no feasible solution.
Step 3: apply a pivoting
End while
The current basis is feasible
Apply the simplex algorithm.Remark 1.
There is no proof for the correctness of the above cosine criteria. Hence, it is not true for ever.


## 3. Benchmark Problems

In this section, we present two well-known classes of linear programming problems, Klee–Minty class of problems [11] is the first problem and the other is Clausen class of problems [14] as illustrated in the following models:(1)max∑j=1n10n−jxjsubject to2∑j=1i−110i−jxj+xi≤100i−1xj≥0,i=1,2,…n,Klee–Minty problem,max∑j=1n45jxj,x1≤1subject to2∑j=1i−154i−jxj+xi≤5i−1xj≥0,i=2,…n,Clausen problem.Klee and Minty [11, 14] proved that the simplex algorithm is an exponential algorithm in 1972 (for the worst case). An interesting result is that the dual simplex method solves the Klee–Minty problem in a polynomial number of iterations. Another challenging exponential example is shown in [14]. The advantage of Clausen’s example [14] is that the dual simplex is exponential on the dual problem, whereas the primal simplex method is exponential on the primal problem.The following examples show the superiority of our technique over the two-phase method. Example1 shows that the two-phase method requires 6 tableaus while our technique requires 3 iterations only, without including the initial one.


## 4. Illustrative Examples

Example 1.
Consider the following Random Linear Programming Problem:(2)minw=4x1+x2subject to:3x1+x2≤3;3x1+x2≥3;4x1+3x2≥6;x1+2x2≤4x1,x2≥0.
The variablesx3 and x6 are slack variables, but the variables x4 and x5 are the surplus variables for the corresponding constraints. We calculate cosθi for every i = 2, 3 (in the first iteration) as follows:(3)cosθ1=#,cosθ2=−3×−4+−1−12−32+−12=16910=16.9,cosθ3=−4×−4+−3−12−42+−32=36125=14.44,cosθ4=#.
The value ofcosθ2 is bigger than the value of cosθ3. Therefore, the variable x4 is the leaving variable. From STEP 2, the entering variable is calculated as follows.
min
b
i
/
a
i
j
:
a
i
j
<
0
and
j
∈
N
=
−
3
/
−
3
,
−
3
/
−
1
=
1, and therefore, the element x1 is the entering variable. We can construct a new simplex table by the pivoting operations (i.e., Step 3) as shown in Iteration 1 in Table 1. We repeat all above operations until all coefficients in Row 0 are nonpositive in Iteration 3, and x3 = 0, x4 = 2/5, x5 = 9/5, and x6 = 1 are optimal with z = 17/5 in the original problem.
Furthermore, the two-phase method requires 6 iterations, as shown in Table2, without including the initial one.Table 1
The solution of Example1 by the proposed DCSM.
Iteration
x
1
x
2
x
3
x
4
x
5
x
6
R.H.S
0
Z
−4
−1
0
0
0
0
0
x
3
3
1
1
0
0
0
3
x
4
−3
−1
0
1
0
0
−3
x
5
−4
−3
0
0
1
0
−6
x
6
1
2
0
0
0
1
4
1
Z
0
2
0
0
−1
0
6
x
3
0
0
1
1
0
0
0
x
4
1
1/3
0
−1/3
0
0
1
x
5
0
−5/3
0
−4/3
1
0
−2
x
6
0
5/3
0
1/3
0
1
3
2
Z
0
0
0
−8/3
1/5
0
18/5
x
3
0
0
1
1
0
0
0
x
4
1
0
0
−3/5
1/5
0
3/5
x
5
0
1
0
4/5
−3/5
0
6/5
x
6
0
0
0
−1
1
1
1
3
Z
0
0
0
−7/5
0
−1/5
17/5
x
3
0
0
1
1
0
0
0
x
4
1
0
0
−2/5
0
−1/5
2/5
x
5
0
1
0
1/3
0
−3/5
9/5
x
6
0
0
0
−1
1
1
1Table 2
The solution of Example1 by the two-phase method.
Iteration
x
1
x
2
x
3
x
4
x
5
R
1
R
2
x
6
R.H.S
0 Phase1
Z′
0
0
0
0
0
−1
−1
0
0
x
5
3
1
0
0
1
0
0
0
3
R
1
3
1
−1
0
0
1
0
0
3
R
2
4
3
0
−1
0
0
1
0
6
x
6
1
2
0
0
0
0
0
1
4
1 Phase1
Z′
7
4
−1
−1
0
0
0
0
9
x
5
3
1
0
0
1
0
0
0
3
R
1
3
1
−1
0
0
1
0
0
3
R
2
4
3
0
−1
0
0
1
0
6
x
6
1
2
0
0
0
0
0
1
4
2 Phase1
Z′
0
1.67
−1
−1
−2.33
0
0
0
2
x
1
1
0.33
0
0
0.33
0
0
0
1
R
1
0
0
−1
0
−1
1
0
0
0
R
2
0
1.67
0
−1
−1.33
0
1
0
2
x
6
0
0
0
0
−0.33
0
0
1
3
3 Phase1
Z′
0
0
−1
0
−1
0
−1
0
0
x
1
1
0
0
0.2
0.6
1
−0.2
0
0.6
R
1
0
0
−1
0
−1
0
0
0
0
x
2
0
1
0
−0.6
−0.8
0
0.6
0
1.2
x
6
0
0
0
1
1
0
−1
1
1
4 Phase2
Z′
0
0
0
0.2
1.6
Blocked
Blocked
0
3.6
x
1
1
0
0
0.2
0.6
0
−0.2
0
0.6
R
1
0
0
−1
0
−1
1
0
0
0
x
2
0
1
0
−0.6
−0.8
0
0.6
0
1.2
x
6
0
0
0
1
1
0
−1
1
1
5 Phase 2
Z′
0
0
−1.6
0.2
0
Blocked
Blocked
0
3.6
x
1
1
0
−0.6
0.2
0
0
−0.2
0
0.6
x
5
0
0
1
0
1
1
0
0
0
x
2
0
1
0.8
0.6
0
0
0.6
0
1.2
x
6
0
0
−1
1
0
0
−1
1
1
6 Phase 2
Z′
0
0
−1.4
0
0
Blocked
Blocked
−0.2
3.4
x
1
1
0
−0.4
0
0
0
−0.2
−0.2
0.4
x
5
0
0
1
0
1
1
0
0
0
x
2
0
1
0.2
1
0
0
0.6
0.6
1.8
x
4
0
0
−1
0
0
0
−1
1
1Example 2.
Dual Klee–Minty problem.
Consider the following dual Klee–Minty problem of sizen = 3:(4)minw=x1+100x2+10000x3subject to:x1+20x2+200x3≥100;x2+20x3≥10;4x3≥1,x1,x2,x3≥0.
The variablesx4, x5, and x6 are the surplus variables for the corresponding constraints. We calculate the corresponding cosθi in the Iteration 0 for every i = 1, 2, 3 as follows:(5)cosθ1=−1×−1+−20−100+−200×−100002−12+−202+−2002=4.0008×101240401=99027351.81,cosθ2=0×−1+−1−100+−20×−10000202+−12+−202=4.004001×1010401=99850399,cosθ3=0×−1+0−100+−1×−10000202+02+−12=1081=108.
The value ofcosθ3 is bigger than the values of cosθ1 and cosθ2. We choose x6 as the leaving variable. The entering variable is calculated as follows (STEP 2):(6)minbiaij:aij<0andj∈N=−100−1,−100−20,−100−200=12.
Therefore, the elementx3 is the entering variable. We can construct a new simplex table by the pivoting operations (i.e., STEP 3) as shown in Iteration 1 in Table 3. We repeat all above operations until all coefficients in Row 0 are nonpositive in Iteration 3, and x1 = 1 and x2 = x3 = 0 are optimal with z = 104 in the original problem.
On the other hand, the two-phase method requires 5 iterations, as shown in Table4, without including the initial one.Table 3
The solution of Example2 by the proposed DCSM.
Iteration
x
1
x
2
x
3
x
4
x
5
x
6
R.H.S
0
Z
−1
−10
−10000
0
0
0
0
x
4
−1
−20
−200
1
0
0
−100
x
5
0
−1
−20
0
1
0
−10
x
6
0
0
(−1)
0
0
1
−1
1
Z
−1
−10
0
0
0
−10000
10000
x
4
−1
−20
0
1
0
200
100
x
5
0
−1
0
0
1
20
10
x
3
0
0
1
0
0
−1
1Table 4
The solution of Example2 by the two-phase method.
Iteration
x
1
x
2
x
3
x
4
x
5
x
6
R
1
R
2
R
3
R.H.S
0 Phase1
Z′
0
0
0
0
0
0
−1
−1
−1
0
R
1
1
20
200
−1
0
0
1
0
0
100
R
2
0
−1
−20
0
−1
0
0
1
0
10
R
3
0
0
(−1)
0
0
−1
0
0
1
1
1 Phase1
Z′
1
21
221
−1
−1
−1
0
0
0
111
R
1
1
20
200
−1
0
0
1
0
0
100
R
2
0
1
20
0
−1
0
0
1
0
10
R
3
0
0
1
0
0
−1
0
0
1
1
2 Phase1
Z′
−0.11
−1.10
0
0.11
−1
−1
−1.11
0
0
0.50
x
3
0.01
0.10
1
−0.01
0
0
0.01
0
0
0.50
R
2
−0.10
−1
0
(0.10)
−1
0
−0.10
1
0
0
R
3
−0.01
−0.10
0
0.01
0
−1
−0.01
0
1
0.50
3 Phase1
Z′
0
−0.05
0
0
0.05
−1
−1
−1.05
0
0.50
x
3
0
0.05
1
0
−0.05
0
0
0
0
0.50
x
4
−1
−10
0
1
−10
0
−1
10
0
0
R
3
0
−0.05
0
0
0.05
−1
0
−0.05
1
0.50
4 Phase1
Z′
0
0
0
0
0
0
−1
−1
−1
0
x
3
0
0
1
0
0
−1
0
0
1
1
x
4
−1
−20
0
1
0
−200
−1
0
200
100
R
3
0
−1
0
0
1
−20
0
−1
20
10
5 Phase 2
Z′
−1
−100
0
0
0
−104
Blocked
Blocked
Blocked
10000
x
3
0
0
1
0
0
−1
0
0
1
1
x
4
−1
−20
0
1
0
−200
−1
0
200
100
x
5
0
−1
0
0
1
−20
0
−1
20
10


## 5. Computational Experiments

In this section, we present the computational results of the dual cosine simplex algorithm (DDCA) and two-phase method for dual Klee–Minty and dual Clausen classes of problems. We compare the number of iterations of the dual cosine simplex algorithm (DDCA) with the two-phase method. We used different tolerances to reduce the number of iterations for each benchmark problem. We used the two-phase method [3, 15–18] to evaluate the effectiveness of the proposed method. On the other hand, the two-phase method was used for the problems contain “≥” constraints and/or equality constraints.The programming language used was MATLAB v7.01 SP2 with default options. All codes were run under 64-bit Window 8.1 Operating System having Core (TM)i5 CPU M 460 @2.53 GHz, 4.00 GB of memory.It is clear that the basic difference between the dual cosine simplex method (DCSM) and the two-phase method  is that our technique does not involve artificial variables. From Table5, the contribution of the proposed algorithm is to solve the Klee–Minty problem and Clausen problem with 2 and 4 iterations, respectively. On the other hand, the simplex method with two-phase method spends O(n) iterations for these problems.Table 5
The Tableau obtained from the dual cosine and two-phases.
Size
Dual Klee–Minty problem
Dual Clausen problem
Dual cosine DDCA
Two-phase method
Dual cosine DDCA
Two-phase method
1
2
1
4
3
2
2
3
4
4
3
2
4
4
5
4
2
5
4
7
5
2
6
4
9
6
2
7
4
11
7
2
8
4
13
8
2
9
4
15
9
2
10
4
17
10
2
11
4
19Table6 characterizes 33 NETLIB test problems [19] were used in comparison to evaluate the effectiveness of the proposed methods. For simplicity, we converted the bounded variables and free variables into constraints. The accuracy rates of the solution obtained from the proposed algorithms were tested by LINGO software.Table 6
Properties of 33 NETLIB problems.
Problem name
No. of nonzeros
Density
New number of constraints
New number of variables
Number of variables
Number of “≤” constrains
Number of “≥” constrains
Number of “=” constrains
adlittle
465
0.0856
56
97
97
40
1
15
afiro
88
0.10185
27
32
32
19
0
8
bandm
2659
0.01847
305
472
472
0
0
305
beaconfd
3476
0.07669
173
262
262
33
0
140
brandy
2150
0.03925
220
249
249
54
0
166
etamacro
2489
0.00547
400
688
688
183
125
354
fit1d
14,430
0.0134
24
1026
1026
1038
11
1
fit1p
10,894
0.00633
627
1677
1677
399
0
627
grow15
5665
0.00976
300
645
645
600
0
300
grow22
8318
0.00666
440
946
946
880
0
440
grow7
2633
0.02083
140
301
301
280
0
140
kb2
291
0.13649
43
41
41
21
15
16
lotfi
1086
0.02305
153
308
308
42
16
95
recipelp
752
0.0198
91
180
180
77
43
91
sc105
281
0.02598
105
103
103
60
0
45
sc205
552
0.01326
205
203
203
114
0
91
sc50a
131
0.05458
50
48
48
30
0
20
sc50b
119
0.04958
50
48
48
30
0
20
scagr25
2029
0.00862
471
500
500
146
25
300
scagr7
553
0.03062
129
140
140
38
7
84
scfxm1
2612
0.01732
330
457
457
143
0
187
scfxm2
5229
0.00867
660
914
914
286
0
374
scfxm3
7846
0.00578
990
1371
1371
429
0
561
scsd1
3148
0.05379
77
760
760
0
0
77
scsd6
5666
0.02855
147
1350
1350
0
0
147
sctap1
2052
0.01425
300
480
480
0
180
120
share1b
1182
0.0449
117
225
225
28
0
89
share2b
730
0.09626
96
79
79
83
0
13
shell
4900
0.00303
536
1775
1775
119
9
784
ship04 l
8450
0.00992
402
2118
2118
40
8
354
ship04s
5810
0.00991
402
1458
1458
40
8
354
stair
3857
0.0186
356
467
467
153
0
698
stocfor1
474
0.0365
117
111
111
48
6
63
Sum
111,017
1.09377
8539
19,531
19,531
5453
454
7079
Average
3364.152
0.03315
258.758
591.849
591.849
165.242
13.7576
214.515
Max
14,430
0.13649
990
2118
2118
1038
180
784
Min
88
0.00303
24
32
32
0
0
1Table6 contains 6 categories of the problems according to the range of variable numbers as shown in Table 7.Table 7
The classification of the benchmark problems according to the variable number range.
Variable number range
30–99
100–500
501–99
1000–1500
1501–1999
Over 2000
Number of problems
6
15
5
4
2
1Table6 contains the largest nonzero number, density, number of variables (after transferring sign constraints), number of constraints (after transferring sign constraints), “≤” constraint number, “≥” constraint number, and “=” constraint number.In general, from Table8, the contribution of the proposed algorithm is that DDCA is generally better than the two-phase method (22 problems vs. 11 problems). The details of our results are as follows:(a)
Six problems with the variable numbers 30–99: DDCA is better than the two-phase method (5 problems vs. one problem)(b)
Fifteen problems with the variable numbers 100–500: DDCA is better than the two-phase method (10 problems vs. 5 problems)(c)
Five problems with the variable numbers 501–999: DDCA is better than the two-phase method (4 problems vs. one problem)(d)
Four problems with the variable numbers 1000–1500: DDCA and two-phase methods are equal (2 problems vs. 2 problems)(e)
Two problems with the variable numbers 1501–1999: the two-phase method is better than DDCA (0 problems vs. 2 problems)(f)
One problem with the variable numbers over 2000: the two-phase method is better than DDCA (0 problems vs. 1 problem)Table 8
A comparison between the two-phase method and the proposed DDCA.
Problem name
Iteration number
Difference in iteration number
DCA
Simplex
Phase I
Phase II
Phase I&II
Phase I
Phase II
Phase I&II
Phase I
Phase II
Phase I&II
adlittle
21
99
120
38
100
138
17
1
18
afiro
6
7
13
10
7
17
4
0
4
bandm
828
323
1151
1042
242
1284
214
−81
133
beaconfd
132
17
149
154
37
191
22
20
42
brandy
731
82
813
521
71
592
−210
−11
−221
etamacro
940
355
1295
944
423
1367
4
68
72
fit1d
52
1664
1716
94
1355
1449
42
−309
−267
fit1p
820
2288
3108
1441
1358
2799
621
−930
−309
grow15
285
205
490
303
485
788
18
280
298
grow22
425
245
670
443
704
1147
18
459
477
grow7
131
78
209
143
168
311
12
90
102
kb2
74
25
99
397
38
435
323
13
336
lotfi
208
164
372
126
77
203
−82
−87
−169
recipelp
300
6
306
299
28
327
−1
22
21
sc105
54
46
100
64
42
106
10
−4
6
sc205
118
110
228
128
115
243
10
5
15
sc50a
24
20
44
29
23
52
5
3
8
sc50b
32
14
46
37
21
58
5
7
12
scagr25
503
869
1372
639
218
857
136
−651
−515
scagr7
126
85
211
159
45
204
33
−40
−7
scfxm1
753
252
1005
802
211
1013
49
−41
8
scfxm2
1592
322
1914
1478
386
1864
−114
64
−50
scfxm3
1947
490
2437
2324
591
2915
377
1
378
scsd1
90
200
290
139
206
345
49
6
55
scsd6
216
184
400
170
447
617
−46
263
217
sctap1
453
161
614
705
163
868
252
2
254
share1b
352
224
576
363
158
521
11
−66
−55
share2b
125
50
175
112
27
139
−13
−23
−36
shell
795
264
1059
843
209
1052
48
−55
−7
ship04 l
700
143
843
728
78
806
28
−65
−37
ship04s
488
106
594
499
58
557
11
−48
−37
stair
1019
323
1342
1203
265
1468
184
−58
126
stocfor1
81
12
93
90
29
119
9
17
26
Sum
14421
9433
23854
16467
8385
24852
Average
437
285.848
722.848
499
254.091
753.091
Max
1947
2288
3108
2324
1358
2915
Min
6
6
13
10
7
17


## 6. Conclusions

We proposed a dual version of the direct cosine simplex algorithm (DDCA) for general linear problems. The proposed method has not artificial variables, so it is different from both the two-phase method and big-M method. Our technique solved the dual Klee–Minty problem via two iterations and solved the dual Clausen problem via four iterations. The power of the proposed algorithm is evident from the extensive experimental results on benchmark problems adapted from NETLIB. Preliminary results indicate that this dual direct cosine simplex algorithm (DDCA) reduces the number of iterations of the two-phase method. In future work, we can improve this work by using different algorithms [20–24] with other combinations between them.



---

*Source: 7361092-2020-05-11.xml*