Solved

Excel Solver

Posted on 2011-02-20
23
1,416 Views
Last Modified: 2012-05-11
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
0
Comment
Question by:ExpExchHelp
  • 9
  • 9
  • 5
23 Comments
 
LVL 10

Expert Comment

by:cdebel
ID: 34937414
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
 
LVL 10

Expert Comment

by:cdebel
ID: 34937422
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
 
LVL 45

Expert Comment

by:patrickab
ID: 34937504
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
Free Tool: Postgres Monitoring System

A PHP and Perl based system to collect and display usage statistics from PostgreSQL databases.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 45

Expert Comment

by:patrickab
ID: 34937552
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
 
LVL 10

Expert Comment

by:cdebel
ID: 34937557
i'm mixed up Patrickab.  Where do you see items which weights 50 / item?
0
 
LVL 10

Expert Comment

by:cdebel
ID: 34937566
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
 
LVL 45

Expert Comment

by:patrickab
ID: 34937571
>Where do you see items which weights 50 / item?

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

Patrick
0
 
LVL 45

Expert Comment

by:patrickab
ID: 34937581
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
 
LVL 10

Expert Comment

by:cdebel
ID: 34937614
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
 
LVL 10

Expert Comment

by:cdebel
ID: 34937617
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
 
LVL 10

Expert Comment

by:cdebel
ID: 34937643
(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
 
LVL 45

Expert Comment

by:patrickab
ID: 34937645
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
 
LVL 45

Expert Comment

by:patrickab
ID: 34937655
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
 
LVL 10

Accepted Solution

by:
cdebel earned 250 total points
ID: 34937711
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
 

Author Comment

by:ExpExchHelp
ID: 34937818
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
 

Author Comment

by:ExpExchHelp
ID: 34937826
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
 

Author Comment

by:ExpExchHelp
ID: 34937872
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
 
LVL 45

Assisted Solution

by:patrickab
patrickab earned 250 total points
ID: 34937940
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
 
LVL 45

Expert Comment

by:patrickab
ID: 34937965
>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
 

Author Comment

by:ExpExchHelp
ID: 34938132
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
 
LVL 10

Expert Comment

by:cdebel
ID: 34938295
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
 

Author Comment

by:ExpExchHelp
ID: 34938336
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
 
LVL 45

Expert Comment

by:patrickab
ID: 34939199
ExpExchHelp - Thanks for the points - Patrick
0

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction While answering a recent question (http:/Q_27311462.html), I created an alternative function to the Excel Concatenate() function that you might find useful.  I tested several solutions and share the results in this article as well as t…
Convert between Excel file formats (.XLS, .XLSX, .XLSM) with/without macro option David Miller (dlmille) Intro Over this past Fall, I've had the opportunity to see several similar requests and have developed a couple related solutions associate…
This Micro Tutorial will demonstrate on a Mac how to change the sort order for chart legend values and decrpyt the intimidating chart menu.
Many functions in Excel can make decisions. The most simple of these is the IF function: it returns a value depending on whether a condition you describe is true or false. Once you get the hang of using the IF function, you will find it easier to us…

856 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question