Get Help

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Community
- :
- PTC Mathcad
- :
- PTC Mathcad
- :
- How to minimize the waste on a DVD?

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

Showing results for

Highlighted

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
10:05 AM

02-24-2014
10:05 AM

Hi,

I have here a simple optimation problem. I would like to minimize the free space (= waste) on a DVD by given file with their filesizes.

but I have a problem in defining the Minimize function.

Any help are very welcome!#

the a should be only 0 or 1

Solved! Go to Solution.

1 ACCEPTED SOLUTION

Accepted Solutions

Highlighted

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
10:37 AM

02-24-2014
10:37 AM

Well this problem is defined as (1 dimensional) bin packing problem.

Well, there may be more than one name for the problem. The problem can be read about as knapsack problem back to the end of the 18th century, but the name is assumed to be used in folkolore even earlier.

"Bin packing problem" is something similar and would mean fo your CDs that you have a number of files with different size, pack them ALL on CDs and the goal is to minimize the number of CDs used. But both problems often are mixed up and in German "Packproblem" is very often used for both of them.

or how can I define that a1 to a4 is only integer?

You can't. And if you could the LM algorith behind Minimize wouldn't work.

You are trying to solve an NP-hard combinatorical problem. As long as you stay with a five element vector to chose from you may find an optimal solution using some kind of brute force algorithm. For larger vector you would have to resort to one of the heuristic/approximation algorithms (look up the literature) to get a good (but most certainly not optimal) solution.

27 REPLIES 27

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
10:19 AM

02-24-2014
10:19 AM

Re: How to minimize the waste on a DVD?

I don't think that you can you minimize() for this knapsack problem. The LM algorithm needs a continuous function to work with.

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
10:21 AM

02-24-2014
10:21 AM

Re: How to minimize the waste on a DVD?

Well this problem is defined as (1 dimensional) bin packing problem.

If I could define that a1 to a4 is only 0 or 1 then it would work.

or how can I define that a1 to a4 is only integer?

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
10:25 AM

02-24-2014
10:25 AM

Re: How to minimize the waste on a DVD?

From the Help file for Minimze * If you are solving for n variables, the solve block must have n equations.*

Alan

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
10:28 AM

02-24-2014
10:28 AM

Re: How to minimize the waste on a DVD?

thanks, what about that? The a are still float and not 0 or 1

Highlighted

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
10:37 AM

02-24-2014
10:37 AM

Well this problem is defined as (1 dimensional) bin packing problem.

Well, there may be more than one name for the problem. The problem can be read about as knapsack problem back to the end of the 18th century, but the name is assumed to be used in folkolore even earlier.

"Bin packing problem" is something similar and would mean fo your CDs that you have a number of files with different size, pack them ALL on CDs and the goal is to minimize the number of CDs used. But both problems often are mixed up and in German "Packproblem" is very often used for both of them.

or how can I define that a1 to a4 is only integer?

You can't. And if you could the LM algorith behind Minimize wouldn't work.

You are trying to solve an NP-hard combinatorical problem. As long as you stay with a five element vector to chose from you may find an optimal solution using some kind of brute force algorithm. For larger vector you would have to resort to one of the heuristic/approximation algorithms (look up the literature) to get a good (but most certainly not optimal) solution.

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
10:42 AM

02-24-2014
10:42 AM

Re: How to minimize the waste on a DVD?

thanks Werner!

Now it is clear. I found a comercial (1dnest) program on the net, that do the bin packing problem.

And indeed, I would like to minimize the used DVDs for my many files with fixed size.

I thought I could resolve that with Mathcad. 1dnest do a great job, I could arrange about 990 files/directories with it. What a pity that I can not reproduce the algorithm with mathcad.

Thanks very much for your help and successful answer.

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
11:06 AM

02-24-2014
11:06 AM

Re: How to minimize the waste on a DVD?

What a pity that I can not reproduce the algorithm with mathcad.

You probably could - its just some work to code it yourself 😉

Something like tghe greedy algorith would be quite easy to implement. More sohisticated ones like an annealing algo would take more time (but better results).

For very earlier versions of Mathcad there was an addon pack "numerical recipes" based on the famous book available which had some good heuristic algorithms for that kind of problems (like the travelling salesman or the bin packing) built in (e.g. annealing algorithm. But I guess this addon won't work with newer mathcad versions anymore.

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
11:47 AM

02-24-2014
11:47 AM

Re: How to minimize the waste on a DVD?

OK, never say never 🙂

Here is your file and minimze() is working well with your test data, Nevertheless I still think that the result of Mathcads optimization algorithm for continuous functions will give that optimal results for real world data. But feel free to give it a try.

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
11:57 AM

02-24-2014
11:57 AM

Re: How to minimize the waste on a DVD?

Great! Its really sophisticated in a simple manner.

I will thest that with more filesizes.

thanks a lot.

walter

PS: would it be possibel to put DVD as vector and show a Matrix with all the solutions over DVD?

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
12:32 PM

02-24-2014
12:32 PM

Re: How to minimize the waste on a DVD?

You could try adding the DVD size as a parameter of waist(), turn the solve block into a function of DVD and then call the function vectorized with your DVD vector as parameter. Not sure if this will work as expected, though.

Furthermore I guess the result will not be what you are looking for as all values will be availale for all DVDs. Its the knapsack problem, not the packed bin.

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
12:39 PM

02-24-2014
12:39 PM

Re: How to minimize the waste on a DVD?

you mean that way?

Could you give me a hit how to do that?

Thanks

I can not define the MINIMIZE als function. What do I wrong?

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
01:29 PM

02-24-2014
01:29 PM

Re: How to minimize the waste on a DVD?

WALTER SCHRABMAIR wrote:

you mean that way?

No, something like that attached, but I can't get it to work now either 😞

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
01:36 PM

02-24-2014
01:36 PM

Re: How to minimize the waste on a DVD?

Maybe you must use FIND instead of Minimize.

But the results are wrong.

PS: I got it, with Quasi Newton as FIND ALgo it works again.

BUT unfortunately the results are wrong.

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
02:28 PM

02-24-2014
02:28 PM

Re: How to minimize the waste on a DVD?

You could rather use MinErr() - it may be worth a try.

Find attached a working version using Minimize. Still I am convinced that the solutions found with that method often are mediocre, but see yourself.

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
03:36 PM

02-24-2014
03:36 PM

Re: How to minimize the waste on a DVD?

Wonderfull! I just learned a lot again. Even you are right, your sheets are quite sophisticated.

Thanks a lot.

Walter

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
03:42 PM

02-24-2014
03:42 PM

Re: How to minimize the waste on a DVD?

You are welcome!

Liebe Grüße von Wien nach Graz 😉

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
03:50 PM

02-24-2014
03:50 PM

Re: How to minimize the waste on a DVD?

Danke!

Moreover I relized that the optimizing variables must be the first parameter in the Minimizing solve block.

That was the reason, that your sheet did not work the first time.

Nice evening!

Best regards

Walter

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
04:02 PM

02-24-2014
04:02 PM

Re: How to minimize the waste on a DVD?

Moreover I relized that the optimizing variables must be the first parameter in the Minimizing solve block.

That was the reason, that your sheet did not work the first time.

I think the main reason my first attempt failed was because we need to supply ALL parameters of the function to minimize as parameters of f. This is not the case with other solve block like Find() or MinErr(). But Minimize is a bit special in other respects, too. It uses a function normally defined outside the solve block and it can also be used as a standalone function w/o given. Anyway, I have learned something new, too - hope I will rember it if some days I should need it.

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-24-2014
04:28 PM

02-24-2014
04:28 PM

Re: How to minimize the waste on a DVD?

Thanks a lot!

I also learned a lot again.

Best regards

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-25-2014
03:42 AM

02-25-2014
03:42 AM

Re: How to minimize the waste on a DVD?

It is possible I've not fully understood the problem here (a common occurrence!), but, if there are just 5 components to 'a', each of which can be either 0 or 1, then there are only 32 possible combinations for 'a'. These are easily searched to find the one that minimises 'waste' (while keeping it non-negative). - see attached.

Alan

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-25-2014
03:54 AM

02-25-2014
03:54 AM

Re: How to minimize the waste on a DVD?

thanks Alan,

but these filesizes are only a sample. I have about 990 Files. So there it would be a much greater dim of a. (2^990). But for small a your sheet is good. Thanks

walter

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-25-2014
04:42 AM

02-25-2014
04:42 AM

Re: How to minimize the waste on a DVD?

WALTER SCHRABMAIR wrote:

thanks Alan,

but these filesizes are only a sample. I have about 990 Files. So there it would be a much greater dim of a. (2^990). But for small a your sheet is good. Thanks

walter

Yes, 990 is too many for an exhaustive evaluation. I don't think Minimize will do a good job of a 2^990 degrees of freedom optimisation either! A Monte-Carlo approach might be of some use (see attached), though it doesn't guarantee a globally optimum solution.

Alan

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-25-2014
04:56 AM

02-25-2014
04:56 AM

Re: How to minimize the waste on a DVD?

Thank you. Monte Carlo could be a kind of solution.

Best regards

Walter

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

02-25-2014
04:57 PM

02-25-2014
04:57 PM

Re: How to minimize the waste on a DVD?

Yes, I consider Monte Carlo a good way to go here.

I guess most ways are better than using minimize, even the simple greedy algorithm (see attached).

You may also combine the two. First use the greedy and feed the results a sinitial values to the Monte Carlo routine an look if it can refine the results.

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

04-10-2014
02:44 AM

04-10-2014
02:44 AM

Re: How to minimize the waste on a DVD?

danke, nochmals für Ihre Ausschlussreiche Antworten, Hr Enzinger.

The Problem could be solved by help of few answers and advices.

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

04-10-2014
11:57 AM

04-10-2014
11:57 AM

Re: How to minimize the waste on a DVD?

Schön, dass ich helfen konnte.

So why not post your solution here?

Highlighted
##

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

04-11-2014
02:29 AM

04-11-2014
02:29 AM

Re: How to minimize the waste on a DVD?

Dear WE,

thanks for your reply. Well, the solution is based on a commerial add on, which makes the optimization by use of an excel in and output sheet. This commercially add-on is the base of this application.

Generally I wanted to verify this by a mathcad sheet, which is not optimized used and solveable.

the application works fine and it is used for interenally use only.

thanks

walter