Difference: DepthFirstSearch (3 vs. 4)

Revision 42008-05-07 - TWikiAdminUser

  META TOPICPARENT 
 name="SetPartitioning" 

 Depth-First Search for Enumeration
- META TOPICPARENT
+ name="SetPartitioning"
 reset;
-<
<
+model cutting_stock.mod;
data cutting_stock.dat;
->
>
+model cutting_stock_col.mod;
data cutting_stock_col.dat;

param TotalLength;
param Length {ROLLS} >= 0;

data;

param TotalLength := 20;

param Length :=
 A    5
 B    7
 C    9
 ;

model;
 reset data PatternYield, PATTERNS; # Remove any pattern data, we will find it automatically

# Search the possibilities for cutting patterns
-<
<
+param MinLength := min {i in ITEMS} Length[i]; # Find the minimum length of all the items
param MaxPossible {i in ITEMS} >= 0, integer # Find the maximum number of each length item
->
>
+param MinLength := min {i in ROLLS} Length[i]; # Find the minimum length of all the ROLLS
param MaxPossible {i in ROLLS} >= 0, integer # Find the maximum number of each length item
         := TotalLength div Length[i];        # that can be cut from a roll

# The current product being considered
-<
<
+param current symbolic within ITEMS;
->
>
+param current symbolic within ROLLS;
 # The number of each product being cut
-<
<
+param number {ITEMS} >= 0, integer, default 0;
->
>
+param number {ROLLS} >= 0, integer, default 0;
 # Are we still searching?
param stillSearching binary;
 param newPattern > 0, integer;

let PATTERNS := {};
-<
<
+# Start with the first product and no items being cut
let current := first(ITEMS);
->
>
+# Start with the first product and no ROLLS being cut
let current := first(ROLLS);
 let number[current] := 0;
let stillSearching := 1;
repeat {
  display current, number;
-<
<
+  if ( current <> last(ITEMS) ) and
->
>
+  if ( current <> last(ROLLS) ) and
      ( number[current] <= MaxPossible[current] ) then {
-<
<
+       let current := next(current, ITEMS);
->
>
+       let current := next(current, ROLLS);
        let number[current] := 0;
  }
  else if number[current] <= MaxPossible[current] then {
-<
<
+    # current = last(ITEMS), cutting pattern found
->
>
+    # current = last(ROLLS), cutting pattern found
     # Save the pattern
-<
<
+    if ( sum {i in ITEMS} number[i] * Length[i] <= TotalLength) and
       ( TotalLength - sum {i in ITEMS} number[i] * Length[i] < MinLength) then {
->
>
+    if ( sum {i in ROLLS} number[i] * Length[i] <= TotalLength) and
       ( TotalLength - sum {i in ROLLS} number[i] * Length[i] < MinLength) then {
       let newPattern := card(PATTERNS) + 1;
      let PATTERNS := PATTERNS union {newPattern};
-<
<
+      let {i in ITEMS} PatternYield[newPattern, i] := number[i];
      }
->
>
+      let YIELDS[newPattern] := {i in ROLLS : number[i] > 0};
      let {i in YIELDS[newPattern]} PatternYield[newPattern, i] := number[i];
     }
    # Increase the number cut
    let number[current] := number[current] + 1;
  }
  else { # Too many cut, backtrack up the tree
->
>
+    print "Problem";
    display current, number;
     let number[current] := 0;
-<
<
+    if current = first(ITEMS) then
->
>
+    if current = first(ROLLS) then
       let stillSearching := 0;
    else {
-<
<
+      let current := prev(current, ITEMS);
->
>
+      let current := prev(current, ROLLS);
       let number[current] := number[current] + 1;
    }
->
>
+    display current, number;
   }
} while stillSearching;
-<
<
+We get the maximum number of each type of roll that can be cut from the 20cm rolls from {\tt MaxPossible}. This defines the number of nodes at each level in the decision tree.
->
>
+We get the maximum number of each type of roll that can be cut from the 20cm rolls from MaxPossible. This defines the number of nodes at each level in the decision tree.
 We start at the root node and search on the first possibility at level 1 (the 5cm rolls):

View topic | History: r6 < r5 < r4 < r3 | More topic actions...