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