Systematic Generation of Permutations (Total Enumeration) Determine the number of Objects, n. Set np = 1, where np is the tally of the total number of permutations. Notice that np is initialized at 1 because the first permutation is given as the simple enumeration of Objects, 1...n. Set the current position under consideration, Position = n - 1. for i = 1:n Objects(i) = i {Enumerate the objects in a vector. Notice that the initial enumeration inherently places the object positions from least to greatest. These are the initial positions of the objects and the assigned values of the objects during the permutation generation process.} Selection(i) = 1 {Initialize a vector to be used in the systematic selection of Objects--1 if already selected in a permutation, else 0. In this case, all positions are assigned at the start.} end Evaluate the Current statistic/equation for the initial ordering. If a statistic is being evaluated, then initialize Index at 1 to be used to track the number of permutations yielding better/equal indices (values) than the Current (Actual) statistic. while Position > 0 if Objects(Position) > Objects(Position + 1) Position = Position - 1 continue {This pushes the Objects in the final positions towards the beginning of the permutations being generated. If the assigned value of the target in Position is greater than the assigned value of the object in the next position, then skip the "else" and try again.} else Marker = Objects(Position) {The Marker is the object in the position under consideration} for j = Position:n Selection(Objects(j)) {De-select the objects holding the higher positions.} end for j = Marker + 1:n if Selection(j) = 0 Objects(Position) = j {Set the object in Position to its next largest available value.} Selection(j) = 1 break {Prevent selection of more than 1 target.} end end Marker2 = Position {Marker2 assists in assigning unselected Objects to unoccupied positions.} for j = 1:n if Selection(j) = 0 Marker2 = Marker2 + 1 Objects(Marker2) = j Selection(j) = 1 end end np = np + 1 Evaluate the index/equation given the full permutation of Objects. If the generated permutation produced a value more extreme than the Current, then adopt the better value in the Current value. If a statistic is being evaluated, then increment Index. Position = n - 1 {If Position was decremented at the beginning of the while loop on a previous pass, then reset it to n - 1.} end end Finally, if a statistic is being calculated, calculate the one-tailed p-value. General Branch and Bound Algorithm   This algorithm assumes that the number of objects, n, has been previously determined. Three functions—EVALUATION (Real), ADJACENCYTEST (Boolean), and BOUNDTEST (Boolean)—are dependent on the criteria being implemented. The Boolean functions are fathoming rules. ADJACENCYTEST tests whether or not the objective function would be improved by exchanging permutation(Position – 1) with permutation(Position). BOUNDTEST calculates an upper bound on the possible objective function value given a partial sequence of n objects; if the upper bound is less than or equal to LowerB, then the partial sequence can not possibly lead to the optimal solution and the branch is pruned. Position = 1 : permutation(Position) = 1{Initialize position locator in first position.} for k= 2 to n {Initialize all other positions as "unchosen".} permutation (k) = 0 next k LowerB = {0 or determined by heuristic} {Set lower bound on objective function value.} while (Position <> 1 or permutation(Position) <= n) {Continue until termination criteria is met.} Position = Position + 1 {Increment position locator.} BT = false while not BT {Fathom next branch. Previous branch is pruned when BOUNDTEST is false.} permutation(Position) = permutation(Position) + 1 {Fathom next branch by incrementing value in "Position" of permutation.} Redundancy = false {Check Redundancy.} for k= 1 to p-1 if permutation(Position) = permutation(k) then Redundancy = true next k if not Redundancy then if (Position = 1 and permutation(Position) > n) then exit loop {If termination criteria are met, then exit loop and algorithm.} Retract = false if (Position > 1 and permutation(Position) > n) then {Depth retraction retries previous "Position".} Retract = true permutation(Position) = 0 Position = Position – 1 end if if not Retract {If retracted, then remainder of loop is ignored.} if Position = n – 1 then incumbent = EVALUATION {Evaluate when complete sequence is ready.} if incumbent > LowerB then LowerB = incumbent BestSolution = permutation end if else if ADJACENCYTEST then BT = BOUNDTEST {Perform fathoming tests.} end if end if /* not Retract */ end if /* not Redundancy */ loop /*BT loop */ loop /* Termination loop */ {Return BestSolution and LowerB as objective function value} General Dynamic Programming Algorithm This algorithm is given as a Visual BASIC function designed to accommodate multi objective/criterion problems. Declarations of appropriate variables and bolded comments are included.  M[q, n, n] holds q n x n matrices. Although the number of matrices q has not been set, the number of objects n is set at 22. The weights applied the matrices are denoted as w(q). The optimal solution and results are reported in a textbox "Results.Text". The results include a table illustrating the process of backtracking after the final stage of the DP process has been performed. Dim subset(22) As Integer ' subset(n) is the subset (S[k]) of the whole set of objects, S; 1 if chosen, 0 o/w. Dim subcomp(22) As Integer ' S\S(k) is stored in subcomp, the "complement" of S(k) in S Dim rowsum As Double Dim index, current_index, p As Long ' index keeps track of last-added objects and their relative contributions to the objective function Dim last_added(4194304) As Integer ' stores the last-added object to the optimal subset using the array indices for tracking Dim obj_val(4194304) As Double ' stores the optimal values of each S(k) to the objective function as per the associated index for last_added Dim AddedValue, current_val, stored_val As Double ' AddedValue is the contribution of a object to the objective function, i.e. the least-squares loss function; rowsum helps AddedValue Dim AddOn As Integer 'holds the current object in S/S(k) being considered for the next position in the sequence Dim nsum As Long ' used after recursion; it is 2^n; that's as big as the arrays get Dim CumObj(22) As Double ' CumOF holds the cumulative values of the objective function for the successive placements of the objects in the optimal permutation Dim M2(22, 22) As Double Dim ObjectTemp(22) As String nsum = power(2, n) - 1 For i = n + 1 To nsum obj_val(i) = 0 Next i For i = 1 To n 'Init the recursion for subsets of size 1 rowsum = 0 For q = 1 To mn For j = 1 To n If j <> i Then rowsum = rowsum + w(q) * M(q, i, j) Next j Next q index = power(2, i - 1) last_added(index) = i obj_val(index) = rowsum Next i For i = 1 To n 'nothing chosen yet; init w/zeros subset(i) = 0 Next i '*************************** '***** Begin Recursion ***** '*************************** stagek = False For k = 1 To (n - 1) nfirst = 0 If (stagek = False) Then mm = 0: nh = k For j = 1 To nh subset(k + j - nh) = mm + j Next j If subset(1) <> (n - k + 1) Then stagek = True End If   Do Until (stagek = False) If nfirst = 1 Then If (mm < (n - nh)) Then nh = 0 'k<=n-1; so, n-nh always >0; if mm=0: nh set to 0, then add 1 below nh = nh + 1 ' nh runs from k to 1 mm = subset(k + 1 - nh) ' need to init subset w/zeros For j = 1 To nh subset(k + j - nh) = mm + j Next j If subset(1) = (n - k + 1) Then stagek = False ' if n=(k+1) + subset(1), then done with k End If If nfirst = 0 Then nfirst = 1 '********************************* '***** Generate S\S(k) in subcomp***** '********************************* For i = 1 To n 'init subcomp subcomp(i) = 0 Next i jj = 1 For i = 1 To n ' note that subset and subcomp are integral Selected = False For j = 1 To k ' objects are loaded in subset in permuted order If subset(j) = i Then Selected = True Next j If Not Selected Then 'remaining objects are loaded in subcomp in numeric order subcomp(jj) = i: jj = jj + 1 End If Next i '**************************************************************************** '***** Add objects to the end of subset one at a time to find the best last object for S(k+1) '***************************************************************************** index = 0 For i = 1 To k index = index + power(2, subset(i) - 1) 'Used to store best values of S(k)+AddOn in the jj loop Next i nk = n - k For jj = 1 To nk AddOn = subcomp(jj) rowsum = 0 For q = 1 To mn For i = 1 To nk If AddOn <> subcomp(i) Then {Perform partial evaluation added to rowsum. This partial evaluation depends on the criterion being applied. For example, to calculate a dominance index, we would use rowsum = rowsum + (w(q) * M(q, AddOn, subcomp(i)) to complete the conditional statement.} End If Next i Next q AddedValue = rowsum current_val = obj_val(index) + AddedValue current_index = index + power(2, AddOn - 1) stored_val = obj_val(current_index) If current_val > stored_val Then obj_val(current_index) = current_val last_added(current_index) = AddOn End If Next jj Loop Next k '*************************** '***** Begin BackTrack ***** '*************************** permutation(n) = last_added(nsum) CumObj(n) = obj_val(nsum) F_val(mn + 1) = obj_val(nsum) index = nsum lastint = permutation(n) Results.Text = Results.Text & vbCrLf & "====================================================" & vbCrLf Results.Text = Results.Text & "Ind" & vbTab & "2^(n - 1)" & vbTab & "ObjF" & vbTab & "Last Added" & vbCrLf Results.Text = Results.Text & Str\$(index) & vbTab & Str\$(nsum) & vbTab & Str\$(obj_val(index)) & vbTab & Str\$(last_added(index)) & vbCrLf For i = 1 To n - 1 p = power(2, lastint - 1) index = index - p lastint = last_added(index) permutation(n - i) = lastint CumObj(n - i) = obj_val(index) Results.Text = Results.Text & Str\$(index) & vbTab & Str\$(p) & vbTab & Str\$(obj_val(index)) & vbTab & Str\$(last_added(index)) & vbCrLf Next i Function Power(x, y) Power = 1 For i = 1 To x 'Note: If x=0, then Power=1. Power = Power * y next i End Function .::Home : Monograph Programs::.