Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Excel Solver

Posted on 2011-02-20
23
Medium Priority
?
1,473 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 9
  • 9
  • 5
23 Comments
 
LVL 10

Expert Comment

by:Christian de Bellefeuille
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:Christian de Bellefeuille
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
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
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:Christian de Bellefeuille
ID: 34937557
i'm mixed up Patrickab.  Where do you see items which weights 50 / item?
0
 
LVL 10

Expert Comment

by:Christian de Bellefeuille
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:Christian de Bellefeuille
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:Christian de Bellefeuille
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:Christian de Bellefeuille
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:
Christian de Bellefeuille earned 1000 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 1000 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:Christian de Bellefeuille
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

How to Use the Help Bell

Need to boost the visibility of your question for solutions? Use the Experts Exchange Help Bell to confirm priority levels and contact subject-matter experts for question attention.  Check out this how-to article for more information.

Question has a verified solution.

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

Access developers frequently have requirements to interact with Excel (import from or output to) in their applications.  You might be able to accomplish this with the TransferSpreadsheet and OutputTo methods, but in this series of articles I will di…
If you need to forecast numbers -- typically for finance -- the Windows and Mac versions of Excel 2016 have a basket of tools to get the job done.
This Micro Tutorial will demonstrate on a Mac how to change the sort order for chart legend values and decrpyt the intimidating chart menu.
This Micro Tutorial will demonstrate how to use a scrolling table in Microsoft Excel using the INDEX function.

609 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