http://qs321.pair.com?node_id=340097

stefzody has asked for the wisdom of the Perl Monks concerning the following question:

Hello everyone,

Okay, my boss has asked me to do a 'best fit' algorythm for a cuting template for sheet steel for a CAD/CAM client. Now, not knowing much about best fit geometry, and my own limitation, i am drawing a complete and utter blank on this one.

In short, a client has 3 sizes of steel (but for now, lets jst say that they use 1200x400) and they get requests to cut the steel into other rectangles, how can i minimize waste ?

I know it sounds simple, but this is jst starting to really annoy me. I have to output to SVG for display, but thats easy enough. So. anyone come across anything like this before ? I am almost willing to put a 'bounty' on the head of this one (in canadian funds). yes. i am -that- sick and tired of this fricking CAD/CAM client and my boss pestering me about it.

thanks
Stef

Replies are listed 'Best First'.
Re: Geometric Optimisation and Perl
by kvale (Monsignor) on Mar 26, 2004 at 18:55 UTC
    Although creating the best possible solutuion is NP-complete, there exist heurisic methods that are polynomial in time and usually do a fine job. An example of a heuristic method in a perl module is Algorithm::Bucketizer: 
    use Algorithm::Bucketizer;

# Create a bucketizer
my $bucketizer = Algorithm::Bucketizer->new(bucketsize => $size);

# Add items to it
$bucketizer->add_item($item, $size);

# Optimize distribution
$bucketizer->optimize(maxrounds => 100);

# When done adding, get the buckets
# (they're of type Algorithm::Bucketizer::Bucket)
my @buckets = $bucketizer->buckets();

# Access bucket content by using
# Algorithm::Bucketizer::Bucket methods
my @items  = $bucket->items();
my $serial = $bucket->serial();

    [download]
    This module only deals with linear objects inserted into linear bins, whereas you have 2D rectangles cut from rectangular plates. But the heurisitic algorithm would be the same and then modules methods could be overridden:
    • sort rectanges to be cut by area -> that is your linear measure
    • create a method to determine whether another rect can be cut from a partially used plate -> here you will have to do some thinking according to the details of your stock and set of rectangle shapes.
    To get help for the second point, look at "cutting stock problems" on the web, e.g., Two-Dimensional Cutting Stock Problem.

    -Mark

[reply]
[d/l]
Re: Geometric Optimisation and Perl
by Enlil (Parson) on Mar 26, 2004 at 18:23 UTC
    This has been discussed recently here, here, and here. But what it comes down to is that it is an NP-complete problem.

    -enlil

[reply]
Re: Geometric Optimisation and Perl
by Zero_Flop (Pilgrim) on Mar 26, 2004 at 20:06 UTC
    This can actually be big business. When I was in school I had a Prof who was well known for design optimization. Incredible guy knew 5 languages, one of those guys who are scary smart.

    Well he always said that you can take any company that has not been optimized and optimize them by at least 20%. From an Engineering standpoint (Civil/Mechanical) this is an incredible cost savings when you are dealing with volumes or high dollar items.

    He had a friend who would go to companies and offer to optimize them. His basic offer was. I will optimize your process by X %. If I succeed I will get the X% for the first year and you will then keep the difference from that point on. His friend only worked one job a year and vacationed around the world the rest of the time.
[reply]
Re: Geometric Optimisation and Perl
by Anonymous Monk on Mar 26, 2004 at 19:05 UTC
    A few years ago, a friend sent me this program. It is written in VBA for Microsoft Excel (shameful, I know, sorry). His focus was optimizing cuts in sheets of plywood. It should be possible to pick out the algorithm. It draws pretty pictures of the cuts as well. You enter a list of shapes in a few columns and a list of boards available in another few columns.
    Read more... (16 kB)

    Edit by castaway - added readmore tags

[reply]
[d/l]
Re: Geometric Optimisation and Perl
by Vautrin (Hermit) on Mar 26, 2004 at 22:06 UTC
    How strong is your calculus? That's what you're going to need to use to optimize cuttings. How much does the problem change from instance to instance? If there is a significant change from problem to problem, you may want to invest in Wolfram's Mathematica, or a similar program, to allow you to do math. (You could use Inline::C to link to their libraries from Perl, or just use straight C. And, FAIK, they've added Perl / Java / whatever bindings.
    Want to support the EFF and FSF by buying cool stuff? Click here.
[reply]
[reply]

        Have you ever used Mathematica? I'm guessing that you haven't. It is a program that not only allows calculation in symbolic logic, it can do just about any problem you throw at it, well into the graduate level. None of the modules that you have provided do that.

        The question becomes, how hairy is the optimization? If you are talking about something he can solve once on paper -- for instance the shapes that are being cut are the same each time, then he doesn't need the power of Mathematica, or another technical computing platform. If, on the other hand, you are talking about something which you can't solve once for -- for instance if all of the shapes that are being cut change, and they are irregular, there may be a need for Mathematica.

        I don't work for Wolfram, and am in no way affliliated with them, but back when I was getting my degree in Mathematics, Mathematica impressed me more then any of its competitors -- Matlab, Maple, etc. If you need a lot of power, I would recommend trying it. I am pretty sure you can get it on a 30 day trial. If there is a real need, you will be more then able to justify the cost.

        Want to support the EFF and FSF by buying cool stuff? Click here.
[reply]
Re: Geometric Optimisation and Perl
by bageler (Hermit) on Mar 26, 2004 at 19:53 UTC
    this sounds like the knapsack problem. a google search or a supersearch here should help, this question comes up a lot!
[reply]

Back to Seekers of Perl Wisdom