Excel Solver

I'm developing a "Greedy Algorithm" in C++.    The purpose is to maximize the number of items added to a "Knapsack".

To determine the optimal solution (for testing my C++ version), I've used Excel's Solver to determine the best solution.    Please see attached XLS.

Something doesn't seem to be working out in the Excel though.    If my weight constraint = 900 weight units and I want to maximize "value", why does the Excel solution "select" the following?

Excel:
- 9 times item #1.    As item number 1 weighs 100 units each, it now meets the weight constraint.   However, the maximized total value equals 1350 (9* 150).

- Currently, my C++ version picks the following (I want to proof that both platforms -- Excel & C++ -- provide the same solution):
- (4 times item #3) + (1 times item #1).
- This results in a value of 1950 value units (4*450 + 1*150).... which obviously is the more optimal solution.

So, my question... what's missing in my Excel Solver solution (resulting in 1,350 vs. 1,950 value units)?

Thx,
EEH

Test----Weight-Alone.xls
ExpExchHelpAsked:
Who is Participating?
 
Christian de BellefeuilleConnect With a Mentor ProgrammerCommented:
Here's your solution ExpExchHelp.

If i properly understood your need, you need to find the best match ...
the highest value for a shipment based on it's weight ratio.

If i didn't understood your need properly, could you point me out where i'm wrong?

Thanks
CdebelVersion.xlsm
0
 
Christian de BellefeuilleProgrammerCommented:
Hummmm... i've checked your sheet, and i don't see any VBA code.  And the only functions that i see in your sheet is at E17 and F15.  They only do SUMPRODUCT, and there's nothing to test every possible combinations...

Is there anything i'm missing?  If you are using Office 2007 or more recent, make sure to save your workbook in XLSM format because in XLS it strip every VBA code.
0
 
Christian de BellefeuilleProgrammerCommented:
And by the way, if you type 4 in B6 and 1 in B4, you get 1950 as objective... not 1350.  You get 1350 only if you type 9 at B4 and 0 in every other cells unther B column.
0
Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

 
patrickabCommented:
ExpExchHelp,

Perhaps the way I've set up Solver in the attached file is a bit better. I still don't think it maximises the number of items as the result should be 18 of item 5 which weighs 50/item.

Patrick
Weight-Alone-01.xls
0
 
patrickabCommented:
ExpExchHelp,

There an array formula in B14 =SUM(B4:B13*D4:D13) in the attached file. Solver produces the correct result in this instance - 18 of item 5

Patrick
Weight-Alone-02.xls
0
 
Christian de BellefeuilleProgrammerCommented:
i'm mixed up Patrickab.  Where do you see items which weights 50 / item?
0
 
Christian de BellefeuilleProgrammerCommented:
wow, seriously, i'm mixed up.  Perhaps i don't understand the problem

I thought that for a combination of items should have a maximum of 900 units, with the highest possible value.

Pat, your sample show 9800 weight unit...
0
 
patrickabCommented:
>Where do you see items which weights 50 / item?

Please have another look at the table provided by the OP.

Patrick
0
 
patrickabCommented:
cdebel,

>Pat, your sample show 9800 weight unit...

Nope, you're reading it incorrectly. Please run Solver and look at how it's set up and see the results.

However as this is not your question, perhaps you'd like to leave the questions to the original OP rather than taking on the role yourself.

Patrick
0
 
Christian de BellefeuilleProgrammerCommented:
Patrick, i didn't wanted to bug you, i was just showing how confused i am.   And i see that i'm not so confused after all.

I also checked at the file from the OP.  There's no item which weight 50 units.    The smallest is 100 units.  

So perhaps you should calm yourself.  I'm here to help too.
0
 
Christian de BellefeuilleProgrammerCommented:
Oh and by the way, this is people like you Pat who made me say months ago: "f-off e-e... i'm paying my subscription.  I'm tired of all this answering bashing"
0
 
Christian de BellefeuilleProgrammerCommented:
(i was wrong, there's one item 50 weight at line 8)

By the way, the only way to do this would be to:
1- Produce an array which contain ratio (based on value/WeightUnit)
2- Sort this array to find the highest possible values
3- Try different combinations by starting by the highest ratio first
0
 
patrickabCommented:
cdebel,

There is no answering bashing here. I am just trying to encourage you not to take over this question from ExpExchHelp. He asked the question, so it's important that we don't take it away from him.

I have no doubt that you pay for your subscription to EE. However that still means we need to ensure that we don't turn someone else's question into a forum of its own.

If you are a Premium Service Member you can always ask a question yourself - perhaps even using the files provided so far.

Meanwhile:

>I also checked at the file from the OP.  There's no item which weigh[s] 50 units.    The smallest is 100 units.

Please have another look at the Value(V) column for the item weights in the original file.

Patrick
0
 
patrickabCommented:
cdebel,

Perhaps if you take a little time to study how I have set up Solver you would see that it can be used to great advantage. However I am not going to respond any further points you make - for the reason I have already given - it's ExpExchHelp's question.

Patrick
0
 
ExpExchHelpAuthor Commented:
patrickab, cdebel:

Wow... you got me lost in this conversation.    I'm quite certain that my Solver framework was set up correctly.

Although Solver requires "constraints" in order to execute, forget the "weight constraint" for just a moment here.  

The target cell is "looking" at maximizing the sum-product of quantity * item value.     Therefore, the higher an item's value, the greater the quantities should be.    Once a constraint (e.g, weight in this case) has been added, it should (and previously always did for me) determines that it would select, e.g., item # 3 first.... then, it there's weight capacity left, choose another item to maximize value based on 100 weight units being unfilled.

Currently, however, that's not how the Excel works.    
0
 
ExpExchHelpAuthor Commented:
cdebel:

Thanks for the XLS... howeer, you're missing my point.

MS-Excel has the Solver-capability built in.   There's no need for VBA whatsoever.

EEH

0
 
ExpExchHelpAuthor Commented:
Btw, pls find attached my version with two constraints (weight and volume).

This one makes more sense as it does what's it's supposed to be.    However, this solution includes a binary constraint (meeting the "0-1 Knapsack" concept).

For testing purposes (as my C++ code is not working correctly at this moment), I've removed two constraints:

1. I my original posting, I changed one of the constraints from "binary" to "integer" (meaning I can pack as many items into the knapsack)

2. I removed the volume constraint (as my C++ code currently only has that constraint).

So, my goal was to match the Excel to my C++ code... I would have bet "money" on it that it would... but it didn't.

Did I overlook something when having changed "binary" to "integer" and having removed the volume constraint?

EEH
With-2-Constraints.xls
0
 
patrickabConnect With a Mentor Commented:
ExpExchHelp,

You stated very clearly in your question:

The purpose is to maximize the number of items added to a "Knapsack".

Further on in your question you stated that "If my weight constraint = 900 weight.." as a constraint.

From that it appeared to me that you wanted the maximum number of items in the 'knapsack' with a maximum total weight of 900.

I don't see how this clear requirement is the same as you have just re-stated in your comment ID:34937818. Do please explain what you are wanting to achieve.

Patrick
0
 
patrickabCommented:
>MS-Excel has the Solver-capability built in.  There's no need for VBA whatsoever.

Indeed the VBA automation of Solver is tricky and not usually worth the trouble.

Patrick
0
 
ExpExchHelpAuthor Commented:
patrickab:

Yes, you're right... but I also added:

<< If my weight constraint = 900 weight units and I want to maximize "value", why does the Excel solution "select" the following? >>

Again, sorry for the confusion.    The goal is to maximize "value".

Final thoughts/recommendations?
0
 
Christian de BellefeuilleProgrammerCommented:
Sorry for the confusion too.  I was not aware that Excel had a solver built-in since i've never added any "Add-In" in it.

Maybe for some people VBA code might look difficult, but what i've sent you took me a big 5 minutes to write.  It would probably take me few hours to understand the "Solver Add-In".   So it wouldn't save me much time.

So i'll let Patrickab (or anyone else) go on and suggest things, since i don't plan to learn that thing.
0
 
ExpExchHelpAuthor Commented:
cdebel:

No problem... appreciate your help anyways.

Since you're well up to speed w/ programming (5 minutes is pretty fast as far as I'm concerned), maybe you have some suggestions for my C++ task.

So, if you also program in C++, I'd welcome your insights for a problem posted at:
http://www.experts-exchange.com/Programming/Languages/CPP/Q_26834581.html

0
 
patrickabCommented:
ExpExchHelp - Thanks for the points - Patrick
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.