• Please review our updated Terms and Rules here

"Best fit" Optimization software question

J

John

Member
Joined
Mar 17, 2004
Messages
32
Has anyone had any experience in sorting or "optimizing" programs? At work, we do panel processing. My company has spent loads of money on software that will sort a list of parts to determine the greatest yeild per sheet of material. An example would be:
you have 20 parts - of different sizes (length X width)
you have an unlimited supply of panels (length X width)
the problem is how to best cut the panel to produce the least waste with the least handling of the panel. The part sizes should come from a spread sheet or ther form of input and the program should take into account kerf and trim cuts. Anyone interested in trying to write a program in basic that could do this (just for fun) lets talk.
 
Sounds like fun.

I am probably a programming minnow compared to a lot of people on this forum, but I do have some sort routines.

I use them for things like updating soccer standings, finding the median, stuff like that.

Chris
 
I happen to a quite a fisherman, and I know that a school of minnows can draw in some really big fish! I welcome any and all who would like to help. Do you think any of you sort routines would suit the task as proposed?
 
Re: "Best fit" Optimization software question

"John" wrote:

> Has anyone had any experience in sorting
> or "optimizing" programs?

What sort of "Sorting" program did you have
in mind?

I've got examples of Bubble, Insertion, Shell
& Quick. Though I don't know too much
about the Shell sort & perhaps Bubble is the
best I can show in BASIC (even though I
ported it to TP).

Cheers,
CP/M User.
 
I'm not familuar with the names of sort routines. Which one would best suit the example that I gave? Maybe you could explain each one a little so I would have a better idea.
 
To me it sounds more like optimization or equation solving than pure sorting. The sort algorithms mentioned differ in how complex they are to implement and how efficient they are, in particular on large sets of data. Generally, Quicksort is the fastest but most difficult, while Bubblesort is on the other half of the scale.

I would look into min-max equation systems and everything in that world, but as usual, the hard task is to formulate your physical problem into a mathematical one. :)
 
"John" wrote:

> I'm not familuar with the names of sort routines.
> Which one would best suit the example that I
> gave? Maybe you could explain each one a
> little so I would have a better idea.

The idea of Bubble sort is you might have a series
of numbers like this:

2, 7, 3, 6, 4, 8

With Bubble sort the idea is it looks at 2 numbers
at each process & then moves whatever is the
smaller of the two. So in this case it looks at 2 & 7
which is no change, 7 & 3 - 7 is pushed down, then
7 & 6, 6 moves up, 7 & 4, 4 moves up & 7 & 8 which
remains the same. So then you've got:

2, 3, 6, 4, 7, 8 (but hang on 6 & 4 aren't in order!).

This is when a second scan comes in which deals
with the whole process again & can occur. In an
example like this basically this sorting routine I
have checks until all the numbers are in order, if
not it goes back. So while it's a good general
purpose sorting system, for big sorting problems,
this is where it would perhaps fall down.

Insertion Sort is perhaps one which is better for
larger sorting systems, because it only needs to
do one scan of potentially an array, to deal with
sorting. Basically it checks for numbers out of
order & puts them in their rightful place & the
number greater than it are pushed down in the
array:

example:
99, 75, 46, 80, 4

75, 99, 46, 80, 4

46, 75, 99, 80, 4

46, 75, 80, 99, 4

4, 46, 75, 80, 99

Let me know if you want to know
more.

Cheers,
CP/M User.
 
If I'm not mistaken, both bubble sort and insertion sort theoretically are O(N^2), while merge sort and quick sort are O(N * log N). O stands for Ordo and means the worst case number of operations for N number of items. Of course, finer implementation details and reality will have effect on the actual performance, so two O(N^2) algorithms can differ a lot in time spent.

I still think John is closer to linear/integer/network programming, solving "optimization equations". During the weekend I can bring out my old text books and some notes and set up an example of what I mean and some solutions how to solve it.
 
"carlsson" wrote:

> If I'm not mistaken, both bubble sort and
> insertion sort theoretically are O(N^2),
> while merge sort and quick sort are
> O(N * log N). O stands for Ordo and
> means the worst case number of
> operations for N number of items. Of
> course, finer implementation details and
> reality will have effect on the actual
> performance, so two O(N^2) algorithms
> can differ a lot in time spent.

> I still think John is closer to linear/
> integer/network programming, solving
> "optimization equations". During the
> weekend I can bring out my old text
> books and some notes and set up an
> example of what I mean and some
> solutions how to solve it.

I was under the impression that John
wanted sorting number routines & what
I've discussed with him perhaps brushes
on this subject.

I've got a book here which provides a
number of sorting methods in BASIC &
each of them have their advantages &
disadvantages. Bubble is a bit more
clumbersome for sorting larger numbers
while Insertion sort would be better,
since it uses less cycles to check for
sorting.

You are correct in saying that Quick
sort is perhaps the fastest & Bubble
sort is on the other end of the scale &
I do have a Quick sort routine in BASIC,
unlike Bubblesort this is highly complicated
routine.
If John wants to look at one he can let me
know, which is why I left him on "Let me
know if you want to know more." in the
last post.

Cheers,
CP/M User.
 
Ok, let's formulate some linear programming example. John will have to verify if I'm understanding him right:

Code: 
 __________                   __   ____
|          | A panel is a    |__| |____| while parts
|          | large sheet     ___
|          | of material    |   | can have almost
|__________|                |   | any dimensions
                            |___|
To reduce the problem, let's formulate some constraints and work with only five different parts, measured in width * height:

X1 is 1*2 units, X2 is 3*2 units, X3 is 4*4 units, X4 is 1*4 units, X5 is 3*1 units and the panel is 15*20 units in total. How many parts can we make out of the panel, limiting the waste?

Code: 
Maximize    x1 + x2 + x3 + x4 + x5
Subject to: 1*x1 + 3*x2 + 4*x3 + 1*x4 + 3*x5 <= 15
            2*x1 + 2*x2 + 4*x3 + 4*x4 + 1*x5 <= 20
            2*x1 + 6*x2 + 16*x3 + 4*x4 + 3*x5 <= 300
            x1 >=0, x2 >= 0, x3 >=0, x4 >=0, x5>=0
To use the simplex method, setting up coeffecient array (tableau) means we need to invert the objective function and adding slack variables x6, x7, x8:

Code: 
   a1 a2 a3 a4 a5 a6 a7 a8 b
    1  3 (4) 1  3  1  0  0  15
    2  2  4  4  1  0  1  0  20
    2  6 16  4  3  0  0  1 300
rT -1 -1 -1 -1 -1  0  0  0  0
Calculate a1..a5/b on each row and select the element where the ratio is the smallest positive one, marked in (bold) above. Let's select and pivot (solve out) the tableau on that element:
Code: 
  a1    a2    a3     a4    a5    a6    a7    a8    b
 0.25  0.75  1.00  0.25   0.75  0.25  0.00  0.00  3.75
 1.00 -1.00  0.00 (3.00) -2.00  0.00  1.00  0.00  5.00
-2.00 -6.00  0.00  0.00  -9.00  0.00  0.00  1.00  240
 0.00  2.00  0.00  0.00   2.00  0.00  0.00  0.00  15
Pivot again, which only will affect two rows:
Code: 
  a1    a2    a3    a4     a5    a6    a7    a8    b
 0.17  0.83  1.00  0.00 (0.92)  0.25  0.00  0.00  3.33
 0.33 -0.33  0.00  1.00 -0.67   0.00  0.33  0.00  1.67
-2.00 -6.00  0.00  0.00 -9.00   0.00  0.00  1.00  240
 0.00  2.00  0.00  0.00  2.00   0.00  0.00  0.00  15
Code: 
  a1    a2    a3    a4     a5    a6    a7    a8    b
 0.18  0.90  1.08  0.00  1.00   0.27  0.00  0.00  3.62
 0.33 -0.33  0.00  1.00 -0.67   0.00  0.33  0.00  1.67
-2.00 -6.00  0.00  0.00 -9.00   0.00  0.00  1.00  240
 0.00  2.00  0.00  0.00  2.00   0.00  0.00  0.00  15

Admittingly, despite following my text book (Linear and Nonlinear Programming by David G. Luenberger), I'm terribly lost at this stage. Probably I have made a number of wrong assertions and can't recall correctly how to set up this kind of system, but in the end one is supposed to get a system with 1.00 once for all a1..a5, the slack in the extra variables and the coefficients in the bottom row. Maybe it will work if I reduce the number of parts to the number of constraints?
 
You must log in or register to reply here.
Back
Top