How to minimize the waste on a DVD?

[WalterSchrabmai]

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

[Werner_E]

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

[WalterSchrabmai]

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?

[AlanStevens]

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

Alan

[WalterSchrabmai]

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

[Werner_E · Accepted solution]

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.

[WalterSchrabmai]

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.

[Werner_E]

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.

[Werner_E]

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.

[WalterSchrabmai]

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?

[Werner_E]

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.

[WalterSchrabmai]

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?

[Werner_E]

WALTER SCHRABMAIR wrote:

you mean that way?

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

[WalterSchrabmai]

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.

[Werner_E]

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.

[WalterSchrabmai]

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

Thanks a lot.

Walter

[Werner_E]

You are welcome!

Liebe Grüße von Wien nach Graz 😉

[WalterSchrabmai]

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

[Werner_E]

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.

[WalterSchrabmai]

Thanks a lot!

I also learned a lot again.

Best regards

[AlanStevens]

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

[WalterSchrabmai]

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

[AlanStevens]

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

[WalterSchrabmai]

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

Best regards

Walter

[Werner_E]

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.

[WalterSchrabmai]

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

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

[Werner_E]

Schön, dass ich helfen konnte.

So why not post your solution here?

[WalterSchrabmai]

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