Simplex/PDL.pm

filter: Statementstmt 34.6% 35 / 101 Branchbran 16.6% 1 / 6 Conditioncond n/a MC/DCmcdc n/a Subroutinesub 56.2% 9 / 16 Podpod 100% 6 / 6 totaltotal 39.5% 51 / 129 CC 10 SCAR 17.4
CC
10
Cov
34%
determine_simplex_pivot_columns
12.0
determine_positive_ratios
12.0
current_solution
12.0
CRAP 5.7
« Simplex/Rational.pm ↑ Summary Simplex/Float.pm »
1 package Algorithm::Simplex::PDL;
2 3 ▶use Moo;
Subroutine BEGIN: called CC=1 SCAR=0.0
3 3 ▶use MooX::Types::MooseLike::Base qw( ArrayRef Str );
Subroutine BEGIN: called CC=1 SCAR=0.0
4 3 extends 'Algorithm::Simplex';
5 3 with 'Algorithm::Simplex::Role::Solve';
6 3 ▶use PDL::Lite;
Subroutine BEGIN: called CC=1 SCAR=0.0
7 3 ▶use namespace::clean;
Subroutine BEGIN: called CC=1 SCAR=0.0
8  
9 =head1 Name
10  
11 Algorithm::Simplex::PDL - PDL model of the Simplex Algorithm
12  
13 =cut
14  
15 # TODO: Probably need EPSILON for zero approximation check like in Float model.
16  
17 has '+tableau' => (
18 12 ▶ isa => sub { $_[0]->isa('PDL') },
Subroutine __ANON__: called CC=1 SCAR=0.0
19 12 ▶ coerce => sub { PDL->pdl($_[0]) },
Subroutine __ANON__: called CC=1 SCAR=0.0
20 3 );
21  
22 has '+display_tableau' => (
23 isa => ArrayRef [ ArrayRef [Str] ],
24 0 ▶ coerce => sub { &display_piddle($_[0]) },
Subroutine __ANON__: not called CC=1 SCAR=6.9
25 3 );
26  
27 =head1 Methods
28  
29 =head2 _build_number_of_rows
30  
31 Set the number of rows. This is actually for the A matrix in Ax <= y.
32 So the number is one less than the total number of rows in the tableau.
33 The same holds for number of columns.
34  
35 =cut
36  
37 12 ▶sub _build_number_of_rows {
Subroutine _build_number_of_rows: called CC=1 SCAR=0.0
38 12 my $self = shift;
39 12 my ($number_of_columns, $number_of_rows) = ($self->tableau->dims);
40 12 return $number_of_rows - 1;
41 }
42  
43 =head2 _build_number_of_columns
44  
45 set the number of columns given the tableau matrix
46  
47 =cut
48  
49 12 ▶sub _build_number_of_columns {
Subroutine _build_number_of_columns: called CC=1 SCAR=0.0
50 12 my $self = shift;
51 12 my ($number_of_columns, $number_of_rows) = ($self->tableau->dims);
52 12 return $number_of_columns - 1;
53 }
54  
55 =head2 pivot
56  
57 Do the algebra of a Tucker/Bland pivot. i.e. Traverse from one node to and
58 adjacent node along the Simplex of feasible solutions. This pivot method
59 is particular to this PDL model.
60  
61 =cut
62  
63 sub pivot {
64 my $self = shift;
65 my $pivot_row_number = shift;
66 my $pivot_column_number = shift;
67  
68 my $pdl_A = $self->tableau;
69 my $neg_one = PDL->zeroes(1);
70 $neg_one -= 1;
71  
72 my $scale_copy =
73 $pdl_A->slice("($pivot_column_number),($pivot_row_number)")->copy;
74 my $scale = $pdl_A->slice("($pivot_column_number),($pivot_row_number)");
75 my $pivot_row = $pdl_A->slice(":,($pivot_row_number)");
76 $pivot_row /= $scale_copy;
77 $scale /= $scale_copy;
78  
79 # peform pivot algebra in non-pivot rows
80 for my $i (0 .. $self->number_of_rows) {
81 if ($i != $pivot_row_number) {
82 my $a_ic_copy = $pdl_A->slice("($pivot_column_number),($i)")->copy;
83 my $a_ic = $pdl_A->slice("($pivot_column_number),($i)");
84 my $change_row = $pdl_A->slice(":,($i)");
85 my $diff_term = $a_ic x $pivot_row;
86 $change_row -= $diff_term;
87 my $tmp = $neg_one x $a_ic_copy;
88 $a_ic .= $tmp; # $scale_copy;
89 $a_ic /= $scale_copy;
90 }
91 }
92  
93 return $pdl_A;
94 }
95  
96 # Count pivots made
97 0 ▶after 'pivot' => sub {
Subroutine __ANON__: not called CC=1 SCAR=6.9
98 0 my $self = shift;
99 0 $self->number_of_pivots_made($self->number_of_pivots_made + 1);
100 0 return;
101 3 };
102  
103 =head2 is_optimal
104  
105 Return 1 if the current solution is optimal, 0 otherwise.
106  
107 =cut
108  
109 12 ▶sub is_optimal {
Subroutine is_optimal: called CC=3 SCAR=11.1
Pod documented
110 12 my $self = shift;
111 12 my $T_pdl = $self->tableau;
112  
113 # Look at basement row to see if no positive entries exists.
114 12 my $n_cols_A = $self->number_of_columns - 1;
115 12 my $number_of_rows = $self->number_of_rows;
116 12 my $basement_row = $T_pdl->slice("0:$n_cols_A,($number_of_rows)");
117 12 my @basement_row = $basement_row->list;
118 12 foreach my $profit_coefficient (@basement_row) {
119 40 ▶ if ($profit_coefficient > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($profit_coefficient > 0) 0 40 40
120 0 return 0;
121 }
122 }
123  
124 12 return 1;
125 }
126  
127 =head2 determine_simplex_pivot_columns
128  
129 Look at the basement row to see where positive entries exists.
130 Columns with positive entries in the basement row are pivot column candidates.
131  
132 Should run optimality test, is_optimal, first to insure
133 at least one positive entry exists in the basement row which then
134 means we can increase the objective value for the maximization problem.
135  
136 =cut
137  
138 0 ▶sub determine_simplex_pivot_columns {
Subroutine determine_simplex_pivot_columns: not called CC=3 SCAR=24.8
Pod documented
139 0 my $self = shift;
140  
141 0 my @simplex_pivot_column_numbers;
142 0 my $n_cols_A = $self->number_of_columns - 1;
143 0 my $number_of_rows = $self->number_of_rows;
144 0 my $basement_row = $self->tableau->slice("0:$n_cols_A,($number_of_rows)");
145 0 my @basement_row = $basement_row->list;
146 0 my $column_number = 0;
147 0 foreach my $profit_coefficient (@basement_row) {
148  
149 0 ▶ if ($profit_coefficient > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($profit_coefficient > 0) 0 0 0
150 0 push @simplex_pivot_column_numbers, $column_number;
151 }
152 0 $column_number++;
153 }
154  
155 0 return @simplex_pivot_column_numbers;
156 }
157  
158 =head2 determine_positive_ratios
159  
160 Starting with the pivot column find the entry that yields the lowest
161 positive b to entry ratio that has lowest bland number in the event of ties.
162  
163 =cut
164  
165 0 ▶sub determine_positive_ratios {
Subroutine determine_positive_ratios: not called CC=3 SCAR=24.8
Pod documented
166 0 my $self = shift;
167 0 my $pivot_column_number = shift;
168  
169 0 my $n_rows_A = $self->number_of_rows - 1;
170 0 my $number_of_columns = $self->number_of_columns;
171 0 my $pivot_column =
172 $self->tableau->slice("($pivot_column_number),0:$n_rows_A");
173 0 my @pivot_column = $pivot_column->list;
174 0 my $constant_column =
175 $self->tableau->slice("($number_of_columns),0:$n_rows_A");
176 0 my @constant_column = $constant_column->list;
177 0 my $row_number = 0;
178 0 my @positive_ratio_row_numbers;
179 my @positive_ratios;
180  
181 0 foreach my $i (0 .. $n_rows_A) {
182 0 ▶ if ($pivot_column[$i] > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($pivot_column[$i] > 0) 0 0 0
183 0 push @positive_ratios, ($constant_column[$i] / $pivot_column[$i]);
184 0 push @positive_ratio_row_numbers, $i;
185 }
186 }
187 0 return (\@positive_ratios, \@positive_ratio_row_numbers);
188 }
189  
190 =head2 display_pdl
191  
192 Given a Piddle return it as a string in a Matrix like format.
193  
194 =cut
195  
196 0 ▶sub display_pdl {
Subroutine display_pdl: not called CC=1 SCAR=6.9
Pod documented
197 0 my $self = shift;
198 0 my $pdl = $self->tableau;
199 0 my $output = "$pdl";
200 0 return $output;
201 }
202  
203 =head2 current_solution
204  
205 Return both the primal (max) and dual (min) solutions for the tableau.
206  
207 =cut
208  
209 0 ▶sub current_solution {
Subroutine current_solution: not called CC=3 SCAR=24.8
Pod documented
210 0 my $self = shift;
211  
212 # Report the Current Solution as primal dependents and dual dependents.
213 0 my @y = @{ $self->y_variables };
214 0 my @u = @{ $self->u_variables };
215  
216 # Dependent Primal Variables
217 0 my $n_rows_A = $self->number_of_rows - 1;
218 0 my $number_of_columns = $self->number_of_columns;
219 0 my $constant_column =
220 $self->tableau->slice("($number_of_columns),0:$n_rows_A");
221 0 my @constant_column = $constant_column->list;
222 0 my %primal_solution;
223 0 for my $i (0 .. $#y) {
224 0 $primal_solution{ $y[$i]->{generic} } = $constant_column[$i];
225 }
226  
227 # Dependent Dual Variables
228 0 my $n_cols_A = $self->number_of_columns - 1;
229 0 my $number_of_rows = $self->number_of_rows;
230 0 my $basement_row = $self->tableau->slice("0:$n_cols_A,($number_of_rows)");
231 0 my @basement_row = $basement_row->list;
232 0 my %dual_solution;
233 0 for my $j (0 .. $#u) {
234 0 $dual_solution{ $u[$j]->{generic} } = $basement_row[$j] * (-1);
235 }
236  
237 0 return (\%primal_solution, \%dual_solution);
238 }
239  
240 =head2 display_piddle
241  
242 Coercion: convert a PDL into an ArrayRef[ArrayRef[Num]]
243  
244 =cut
245  
246 0 ▶sub display_piddle {
Subroutine display_piddle: not called CC=2 SCAR=17.9
Pod documented
247 0 my $piddle_tableau = shift;
248  
249 0 my @display_tableau;
250 0 my ($number_of_columns, $number_of_rows) = ($piddle_tableau->dims);
251 0 my $number_of_zero_based_rows = $number_of_rows - 1;
252 0 my $number_of_zero_based_columns = $number_of_columns - 1;
253 0 for my $i (0 .. $number_of_zero_based_rows) {
254 0 my $row =
255 $piddle_tableau->slice("0:$number_of_zero_based_columns,($i)");
256 0 my @row = $row->list;
257 0 push @display_tableau, \@row;
258 }
259  
260 0 return \@display_tableau;
261 }
262  
263 3 1;
« Simplex/Rational.pm ↑ Summary Simplex/Float.pm »