Skip to main content
W
WalterSchrabmai12-Amethyst
12-Amethyst
February 24, 2014
Solved

How to minimize the waste on a DVD?

  • February 24, 2014
  • 3 replies
  • 11558 views

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

Best answer by Werner_E

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.

3 replies

W
Werner_E25-Diamond I
25-Diamond I
February 24, 2014

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

W
WalterSchrabmai12-AmethystAuthor
12-Amethyst
February 24, 2014

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?

A
AlanStevens19-Tanzanite
19-Tanzanite
February 24, 2014

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

Alan

W
Werner_E25-Diamond I
25-Diamond I
February 24, 2014

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.

W
WalterSchrabmai12-AmethystAuthor
12-Amethyst
February 24, 2014

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?

W
Werner_E25-Diamond I
25-Diamond I
February 24, 2014

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.

W
WalterSchrabmai12-AmethystAuthor
12-Amethyst
April 10, 2014

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

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

W
Werner_E25-Diamond I
25-Diamond I
April 10, 2014

Schön, dass ich helfen konnte.

So why not post your solution here?

W
WalterSchrabmai12-AmethystAuthor
12-Amethyst
April 11, 2014

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

Terms & ConditionsAccessibility statement