[RESOLVED] cutting sticks

jeepin81

I need some help getting pointed in the right direction... I want to do something similar to the cutting sticks problem.

For example.. I have 30 pieces of 2x4 that are 10' long and I need to cut different sizes and different amounts and I need to cut them in the most efficient way possible to save lumber...

I guess my math skills are not up to par and I am drawing a blank on how to approach this.

Any pointers would be appreciated.

Thanks,
J

jeepin81

Well, I know this is pretty straight forward but here's what I have if all the columns being cut were the same length....


if(isset($_GET['run']) && $_GET['run'] == 'yes'){
$StartColSize = $_GET['clen'];
$NumCol = $_GET['ncom'];
$EndColSize = $_GET['icom'];


//################################
//######### START MATH ###########


$TotalInches = $NumCol * $EndColSize;
$NumSticks = number_format($TotalInches / $StartColSize , 1);
$Round = ceil($NumSticks);
$LeftOver = ($StartColSize * $Round) - $TotalInches;


//######### END MATH #############
//################################


echo "I will need <strong>".$TotalInches."</strong> inches of column for my order.";

echo "<br/>";

echo "I will need <strong>";

if($Round < 2){
echo "1";
}else{
echo $Round;
}
echo "</strong> full columns to complete my order";

echo "<br/>";

echo "I will have <strong>".$LeftOver."</strong> Inches of Columns Left";



}
?>

I've been trying a little to figure this out but it's not going well. I think I need to figure out least amount of cuts to most until there are zero cuts...

I tried looking at nearest neighbor examples and cutting sticks but I'm not able to put it together..

that being said... I am researching and not trying to pawn this off for an easy fix.

Thanks Again,
j

NogDog

Unless you can find some applicable algorithm, I wouldn't have any idea how to do it other than some brute force looping sort of stuff to try all possible combinations. As that sort of thing tends to become exponentially inefficient as more "pieces" get involved, I'd recommend hitting your favorite search engine for things like "cutting stick algorithm" to see if there are any tricks to this.

jeepin81

That's what I have been doing to no avail..... I've searched "cutting sticks problem", "nearest neighbor", etc.... But all i find are complex equations that leave me in the dust... I'm not a mathematician so stuff like this link means nothing to me:

http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=111105&format=html

Here's another link:

http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

I just thought it wouldn't hurt if I post here.... I saw an article awhile back were some guy was using PHP to do some type of Disk DeFrag... type of thing and he used the same type of logic I'm looking for but I cannot find that post for the life of me.

I guess I might have to surrender or ask a mathy type of person. I have a few feelers out there with x-professors/teachers so whatever I find/given to me I will post.

Thanks for replying.
j

jeepin81

Ahh... I think this class will do the trick... I needed to check my terminology and search on "Bin Packing"... I will test n fllw up

Here is the class I found on PHP Classes:

<?php

//Copyright notice  

//(c) 2010 Chi Hoang (info@chihoang.de)
//All rights reserved

class binPacking {

var $BinHeight = 48;
var $ElementsCopy = array ( 4, 4, 4, 4, 4, 5, 5, 5, 9, 9, 18, 18);
var $Bins;

function sortAsc() {
	sort($this->ElementsCopy, SORT_NUMERIC);
}

function sortDesc() {
	rsort($this->ElementsCopy, SORT_NUMERIC);
}

function shuffle() {
	shuffle($this->ElementsCopy);
}

function random_float ($min,$max) {
	return ($min+lcg_value()*(abs($max-$min)));
}

function aoc() {

	$alfa = 1.0; // Importance of the previous trails
	$beta = 1.0; // Importance of the durations
	$rho = 0.1;  // Dcay rate of the pheromone trails
	$asymptoteFactor = 0.9;
	$numAnts = 20;
	$numWaves = 80;
	$numActive = $end = count($this->ElementsCopy);
	$mark = array();
	$element = 0;
	$dur = array();
	$nextPher = array();
	$bestPath  = array();

	for ($i = 0; $i < $numActive; ++$i) {
		for ($j = 0; $j < $numActive; ++$j) {
			$pher[$i][$j] = 1;
			$nextPher[$i][$j] = 0.0;
		}
	}

	for ($i = 0; $i < $numActive; ++$i) {
		for ($j = 0; $j < $numActive; ++$j) {
			if ($i != $j) {
				$dur[$i][$j] = $this->ElementsCopy[$i] + $this->ElementsCopy[$j];
			} else {
				$dur[$i][$j] = $this->ElementsCopy[$i];
			}
		}
	}

	for ($i = 0; $i < count($this->ElementsCopy); ++$i) {
		$mark[$i] = false;
	}

	for ($wave = 0; $wave < $numWaves; ++$wave) {

		$startNode = 0;
		$numActive = count($this->ElementsCopy);
		$numSteps = $numActive  - 1;
		$numValidDests = $numActive ;
		$bestTrip = 0;
		$currDist  = 0;
		$currPath = array();
		$bestPath = array();

		for ($i = 0; $i < $numActive; ++$i) {
			$visited[$i] = false;
		}

		$curr = $startNode;
		$cumProb = 0.0;

		for ($ant = 0; $ant < $numAnts; ++$ant) {

			$cumProb = 0.0;
			for ($next = 1; $next < $numValidDests; ++$next) {
				if (!$visited[$next] && !$mark[$next]) {
					$prob[$next] = pow($pher[$curr][$next], $alfa) * pow($dur[$curr][$next], 0.0 - $beta);
					$cumProb += $prob[$next];
				}
			}
			$guess = $this->random_float(0,1) * $cumProb;
			$nextI = 0;
			for ($next = 1; $next < $numValidDests; ++$next) {
				if (!$visited[$next] && !$mark[$next]) {
					$curr = $next;
					$guess -= $prob[$next];
					if ($guess < 0) {
						$curr = $next;
						break;
					}
				}
			}	

			$currDist=0;
			$currPath = array();
			$currPath[0]=$curr;
			$currDist += $dur[$curr][$curr];
			$numSteps = $numActive - 1;

			for ($step = 0; $step < $numSteps; ++$step) {

				$visited[$curr] = true;
				$cumProb = 0.0;
				for ($next = 1; $next < $numValidDests; ++$next) {
					if (!$visited[$next] && !$mark[$next]) {
						$prob[$next] = pow($pher[$curr][$next], $alfa) * pow($dur[$curr][$next], 0.0 - $beta);
						$cumProb += $prob[$next];
					}
				}
				$guess = $this->random_float(0,1) * $cumProb;
				$nextI = 0;
				for ($next = 1; $next < $numValidDests; ++$next) {
					if (!$visited[$next] && !$mark[$next]) {
						$nextI = $next;
						$guess -= $prob[$next];
						if ($guess < 0.0) {
							break;
						}
					} 
				}

				if ($currDist+$dur[$curr][$nextI]-$dur[$curr][$curr] <= $this->BinHeight && !in_array($nextI, $currPath) && !$mark[$nextI]) { 

					$currDist += $dur[$curr][$nextI]-$dur[$curr][$curr];
					$currPath[$step+1] = $nextI;
					$curr = $nextI;

					if ($currDist > $bestTrip && $currDist <= $this->BinHeight) {
						$bestPath = $currPath;
						$bestTrip = $currDist;
					}
				}
			}				
			$currPath = array_values($currPath);
			for ($i = 0; $steps = count($currPath)-1, $i < $steps; ++$i) {
				//echo "\n".$currDist - $asymptoteFactor * $bestTrip."\n";
				if ($numAnts * ($currDist - $asymptoteFactor * $bestTrip)) {
					$nextPher[$currPath[$i]][$currPath[$i+1]] += ($bestTrip - $asymptoteFactor * $bestTrip) / $numAnts * ($currDist - $asymptoteFactor * $bestTrip);
				}
			}
		}

		for ($i = 0; $i < $numActive; ++$i) {
			for ($j = 0; $j < $numActive; ++$j) {
				$pher[$i][$j] = $pher[$i][$j] * (1.0 - $rho) + $rho * $nextPher[$i][$j];
				$nextPher[$i][$j] = 0.0;
			}
		}

		if (empty($bestPath)) {
			$bestPath = $currPath;
		}

		$c=0;
		foreach ($bestPath as $k => $v) {
			if (!$mark[$v]) {
				$c++;
			}
		}
		//~ echo "\nc:".$c."\n";
		if ($c == count($bestPath)) {
			foreach ($bestPath as $k => $v) {
				$mark[$v] = true;
			}
			$this->Bins[] = $bestPath;
		}
	}

	//print_r($this->ElementsCopy);
	//print_r($bestPath);
	print_r($mark);
	//print_r($nextPher);
	//print_r($pher);
	//print_r($prob);
	//print_r($dur);		
}

function checkAoc() {
	$c=0;
	foreach ($this->Bins as $index => $bin) {
		$sum=0;
		$c++;
		foreach ($bin as $binNumber => $element) {
			$sum += $this->ElementsCopy[$element];	
		}
		echo "\nBin: $c\n";
		print_r($bin);
		echo "\nSum: $sum\n";
	}
}

function nextFit() {

	$this->Bins = array();
	$BinNumber = 0;
	$BinCount = 0;

		// Loop through each Element and place in a Bin
	for ($i = 0; $end = sizeOf($this->ElementsCopy), $i < $end; ++$i) {

		if ($BinCount + $this->ElementsCopy[$i] > $this->BinHeight) {				
			$BinNumber++;
			$BinCount = 0;
		}

			// Place task
		$this->Bins[$BinNumber][] = $this->ElementsCopy[$i];
			// Keep track of how much is stored in this bin
		$BinCount += $this->ElementsCopy[$i];
	}
}

function firstFit() {

	$this->Bins[] = array();
	$BinNumber = 0;
	$BinElement = 0;

		// Loop through each Element and place in a Bin
	for ($i = 0; $end = sizeOf($this->ElementsCopy), $i < $end; ++$i) {

		$BinCount = 0;
		$bPlaced = false;

			// Loops through each Bin to find the first available spot
		for ($j = 0; $j <= $BinNumber; ++$j) {

				// Count the amount placed in this Bin
			$BinCount = 0;
			for ($k = 0; $BinElement = sizeOf($this->Bins[$j]), $k < $BinElement; ++$k) {
				$BinCount += $this->Bins[$j][$k];			
			}
			if ($BinCount + $this->ElementsCopy[$i] <= $this->BinHeight) {
					// There's room for this Element
				$this->Bins[$j][$BinElement] = $this->ElementsCopy[$i];
				$this->Bins[$j][]=0;
				$bPlaced = true;
			}
		}

		if ($bPlaced == false) {
				//There wasn't room for the Element in any existing Bin
				//Create a new Bin
			$this->Bins[][]=$this->ElementsCopy[$i];
			$BinNumber++;
		}		
	}

		// All Elements have been place, now we go back and remove unused Elements
	foreach ($this->Bins as $bin => $element) {
		foreach ($element as $place => $value) {
			if ($value === 0) unset($this->Bins[$bin][$place]);
		}
	}
}

function worstFit() {

	$this->Bins[] = array();
	$BinNumber = 0;

		// Loop through each Element and place in a Bin
	for ($i = 0; $end = sizeOf($this->ElementsCopy), $i < $end; ++$i) {

		$WorstBin = -1;
		$WorstBinAmount = $this->BinHeight+1;

		for ($j = 0; $j <= $BinNumber; ++$j) {

				// Count the amount placed in this Bin
			$BinCount = 0;
			for ($k = 0; $BinElement = sizeOf($this->Bins[$j]), $k < $BinElement; ++$k) {
				$BinCount += $this->Bins[$j][$k];			
			}

				// Find the least full Bin that can hold this Element
			if ($WorstBinAmount > $BinCount && $BinCount + $this->ElementsCopy[$i] <= $this->BinHeight) {
				$WorstBinAmount = $BinCount;
				$WorstBin = $j;
			}
		}

		if ($WorstBin == -1) {
				//There wasn't room for the Element in any existing Bin
				//Create a new Bin
			$BinNumber++;
			$this->Bins[$BinNumber][] = $this->ElementsCopy[$i];
		} else {
				//There's room for this Element in an existing Bin
				//Place Element in "Worst Bin"
			$this->Bins[$WorstBin][] = $this->ElementsCopy[$i];
		}
	}
}

function bestFit() {

	$this->Bins[] = array();
	$BinNumber = 0;
	$BinElement = 0;

		// Loop through each Element and place in a Bin
	for ($i = 0; $end = sizeOf($this->ElementsCopy), $i < $end; ++$i) {

		$BestBin = -1;
		$BestBinAmount = -1;

		for ($j = 0; $j <= $BinNumber; ++$j) {

				// Count the amount placed in this Bin
			$BinCount = 0;
			for ($k = 0; $BinElement = sizeOf($this->Bins[$j]), $k < $BinElement; ++$k) {
				$BinCount += $this->Bins[$j][$k];			
			}

				// Find the most full Bin that can hold this Element
			if ($BestBinAmount < $BinCount && $BinCount + $this->ElementsCopy[$i] <= $this->BinHeight) {
				$BestBinAmount = $BinCount;
				$BestBin = $j;
			}
		}

		if ($BestBin == -1) {
				//There wasn't room for the Element in any existing Bin
				//Create a new Bin
			$BinNumber++;
			$this->Bins[$BinNumber][] = $this->ElementsCopy[$i];
		} else {
				//There's room for this Element in an existing Bin
				//Place Element in "Best Bin"
			$this->Bins[$BestBin][] = $this->ElementsCopy[$i];
		}
	}
}
}

$lkw = new binPacking();
//~ $lkw->sortDesc();
//~ $lkw->sortAsc();
//~ $lkw->shuffle();
//~ print_r($lkw->ElementsCopy);
//~ $lkw->nextFit();
//~ $lkw->firstFit();
//~ $lkw->worstFit();
//~ $lkw->bestFit();
$lkw->aoc();
$lkw->checkAoc();
//~ print_r($lkw->Bins);
?>

will follow-up...

jeepin81

So, I collaborated w/ another local PHP dev. and we completely simplified this process and came up w/ a cool solution and simple:


<?php

$Cuts = array(7,7,7,7,7,12,12,12,12,24,24,24,18,21);
$BoardLength = 48;
$SawSize = .125;

$Boards = array();
arsort($Cuts);
print_r($Cuts);
foreach ($Cuts as $ThisCut){

	$Found = false;
	foreach ($Boards as $id=>$ThisBoard){
		if ($BoardLength - $Boards[$id]['Used'] > $ThisCut + $SawSize){
			$Boards[$id]['Cuts'][] = $ThisCut;
			$Boards[$id]['Used'] += $ThisCut + $SawSize;
			$Found=true;
			break;
		}
	}
	if ($Found==true){continue;}

	$id = count($Boards);
	$Boards[$id]['Cuts'][] = $ThisCut;
	$Boards[$id]['Used'] += $ThisCut + $SawSize;
}

print_r($Boards);

?>

Will mark as resolved.
j

NogDog

Thanks for updating what you did in case anyone's web search leads them here. 🙂