Solved

Excel Solver

Posted on 2011-02-20
23
1,402 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
Comment Utility
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
Comment Utility
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
Comment Utility
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
 
LVL 45

Expert Comment

by:patrickab
Comment Utility
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
Comment Utility
i'm mixed up Patrickab.  Where do you see items which weights 50 / item?
0
 
LVL 10

Expert Comment

by:cdebel
Comment Utility
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
Comment Utility
>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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
(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
Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

 
LVL 45

Expert Comment

by:patrickab
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
>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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
ExpExchHelp - Thanks for the points - Patrick
0

Featured Post

Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

Join & Write a Comment

Approximate matching with VLOOKUP and MATCH seems to me to be a greatly under-used technique, and one which is vital for getting good performance out of large lookups. Until recently I would always have advised using an exact match for simplicity an…
Workbook link problems after copying tabs to a new workbook? David Miller (dlmille) Intro Have you either copied sheets to a new workbook, and after having saved and opened that workbook, you find that there are links back to the original sou…
The viewer will learn how to use a discrete random variable to simulate the return on an investment over a period of years, create a Monte Carlo simulation using the discrete random variable, and create a graph to represent the possible returns over…
This Micro Tutorial will demonstrate how to create pivot charts out of a data set. I also added a drop-down menu which allows to choose from different categories in the data set and the chart will automatically update.

772 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

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now