My Math Forum  

Go Back   My Math Forum > Math Forums > Math Events

Math Events Math Events, Competitions, Meetups - Local, Regional, State, National, International

LinkBack Thread Tools Display Modes
September 20th, 2007, 04:53 AM   #1
Joined: Sep 2007

Posts: 1
Thanks: 0

Creating Optimizer - What's the correct Math Model to use?


I am an application developer and need to create a computer application which output should be the best possible combination of orders that would fit in a a metal stick.

I have tried by sorting the order qty in descending order, but found
that this approach was very simplistic. I need to know if there is
any Math model or formula to make this calculation.

Example of what I need to accomplish:

I have a metal sticks of 2100 MM (Stick are always the same length)

The orders could be of different lengths:

1210 MM
860 "
320 "
650 "
540 "

The goal is to cut the orders using the 2100 MM stick by scrapping the list qty of material. In this case the ideal recomendation would be:

To cut the stick like this: One order: 1,210 MM &
One order: 860 MM
Total qty used: 2,070 MM
Scrap Qty: 30 MM

Someone recomended me to use the Monte Carlo simulation, but I found
that this will not work for this scenario. Someone else told me this would be a combinatory analysis, but I am not sure either of this one.

I hope you can point me to the right direction.


roddy1212 is offline  
September 20th, 2007, 08:47 AM   #2
Global Moderator
CRGreathouse's Avatar
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Your problem seems similar to benathan's.

This is a bin-packing problem, which is NP-hard. There are many algorithms that can solve it. In particular, there are PTAS for this problem, so although you can't guarantee that your solution is optimal in 'reasonable' time you can get as close to optimal as desired without spending too long.

How many lengths do you have to fit at a time? How many different lengths?
CRGreathouse is offline  

  My Math Forum > Math Forums > Math Events

correct, creating, math, model, optimizer

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Need help creating a formula lowena Computer Science 25 January 2nd, 2013 02:19 PM
A Good Model for our Math Expo girishpaiv New Users 1 September 13th, 2012 12:59 PM
Need help creating formula for:Fn-1 + Fn-2 + ... + Fn-k JohnBartle Number Theory 11 June 2nd, 2010 04:06 PM
Pick the correct number from the correct group balste Advanced Statistics 2 September 3rd, 2009 11:20 AM
A Good Model for our Math Expo girishpaiv Algebra 0 December 31st, 1969 04:00 PM

Copyright © 2019 My Math Forum. All rights reserved.