Using Solver to Assign Items to Buckets

Posted on May 11th, 2011 in Excel Howtos , Huis , Learn Excel , Posts by Hui - 50 comments

In April 2011, Mdsuhair asked a question at the Chandoo.org Forums

What formula can I use to divide a group of numbers into 2 groups so that the Sum of each of the 2 groups is as equal as possible?

This is a candidate for Solver.

This post will walk us through the solution to the problem using Solver. It uses Solver and screen shots from Excel 2007.

All versions of Excel have solver available. Users should note that the screen shots may not match your version although the functionality will, some of the functions appear in different locations in different versions of Solver.

What and Where Is Solver

What is Solver

Solver is an Excel add-in that can solve problems by enabling a Target cell to achieve some goal.

This goal may be to minimse, maximise, or achieve some target value.

It solves the problem by adjusting a number of input cells according to a set of criteria or constraints which are defined by the user.

Where is Solver

Solver is an Excel add-in supplied with Excel, but not enabled by default.

To enable solver

File, Excel Options, Add-ins, Manage Excel Add-ins, Select the Solver Add-in checkbox

Solver will now appear as a New Tab on the Data, Analysis Tab

Solver Example

This post is based around a worked example Solver Example File, the file is compatible with all versions of Excel.

Defining the Problem

Mdsuhair had a series of 8 Items each which had a value:

 

He wants to know which items should be combined so that the sum of the values of the items is nearly equal.

To do this we need to assign each item into a Bucket. Namely Bucket A and Bucket B.

We will put values of 1 into a Bucket for each Item to show that it is assigned to that Bucket and a value of 0 to show that the bucket is empty (In/Out) Value.

We can start by adding a Total Column, which counts items in Buckets A + Bucket B for each Item, It then totals the totals.

We also know that we need to work out the Value of each Item in each Bucket

We do this by multiplying the Items Value by the Buckets (In/Out) value

Finally we need to add up the values in each Bucket and work out the difference between them

Mdsuhair’s original problem was to minimise the difference between the sum of the values in the 2 buckets.

Now we can place values of 1 in the buckets manually and Excel will show us the value of each Bucket and the Difference between them in Cell G11.

I have applied some conditional formatting to show when a cell has a value > 0.

The problem is that there are 28 or 256 combinations of answers, and to test them all manually at 1 every 5 seconds would take 21.3 minutes, assuming we can keep up that pace and remember which was the best combination.

This is where solver comes to the fore.

Applying Solver

To apply solver we need to define a series of requirements, rules and constraints.

These requirements, rules and constraints guide solver and set limits which allow solver to quickly narrow in on the answer.

What are our rules

Our main requirement is to minimise the difference between the value of the 2 buckets.

The difference between the 2 buckets in our example is cell G11, the sum of Bucket 2 values minus the Sum of Bucket 1 values.

We want to have G11 as low as possible but greater than or equal to 0.

 

We also know that an item can only be in Bucket A or Bucket B, it can’t be in both and can’t be Broken apart.

That is 2 Constraints for each Item

Firstly The Total column must be equal to 1

Secondly the Buckets Values must be Integers

We also know that the Total Number of Items is 8, this is another constraint.

We will discuss how these constraints are used in the next section

The Solver Window

This section will explain the solver window and its use in defining the problem within solver.

A Blank Solver Window

A Filled Solver Window

Set Target Cell:

This is the Target cell which is the cell which you are trying to solve the problem for.

Our Target cell is G11, The difference between the 2 Buckets values

Equal To:

The Equal To: section defines what we want to do with our Target Cell.

We want to achieve the same value in each Bucket and so the difference between the Buckets will be 0.

It might sound strange but we don’t want to minimise that difference. A minimal value will be achieved when all the Items are placed in Bucket A, as our equation for G11 will then have 0 – Total which is –Total, which is more minimal than 0.

Another way to constrain this is to Change G11 to =Abs(G10-H10)

This allows us to use Min as an Equal To: Value

But for now we can just leave G11 as =G10-H10 and we will set the Equal To: section as 0.

By Changing Cells:

Changing Cells: refers to the cells which will be modified by Solver to try and solve the problem.

We want to let Solver change the number of items in each bucket, this is the range: $C$2:$D$9

Hint: You can try the Guess button next to the Range Reference and Solver will take a Guess at what cells the problem is dependent on.

Always check this if you use it, especially in complex models.

Subject to the Constraints:

Constraints are the rules which define the limits of the possible solutions to the problem

We will add several constraints for our rules:

1. The Total column must be equal to 1 for each Item

2. The Bucket Value must be an Integer

3. The total contents of the 2 buckets must be 8 items

4. You could add a further constraint that each Bucket should hold the same number of items

Hint: As a general Rule, Under Constrain rather than over constrain! You can always add more constraints later.

To do this we will use the Add Constraint Button

1. We need to add a constraint for each cell in the Range E2:E9 that it is only allowed to be = 1

This constraint must be applied for each cell in the range E2:E9

2. We need to add a constraint for each cell in the Range C2:D9 that it is only allowed to be an integer

This constraint must be applied for each cell in the range C2:D9

3. We need to add a constraint for the Total of the 2 Buckets, E10=8

You can Change or Delete Constraints if you make a mistake by selecting the appropriate constraint and using the Change or Delete Buttons

Save and Load Solves Parameters

Selecting the Options Button there is the Option to Save Model and Load Models.

Hint: The Save/Load Models has been shifted onto the main Solver dialog in Excel 2010.

Using the Save Model and Load Model options you can Save and the Load the Solver Parameters for your model. The Save Model saves the parameters in a Range of cells as shown below.

This allows an easy way to actually setup and/or change the solver parameters.

Hint: Setup one constraint using solver then Save the model. Edit the model on the worksheet and re-load the model as required.

Note: That the parameters although when saved show as True/False or Numbers are all Excel Equations, see above.

This means you can edit them to change the Constraints and Parameters as required and re-load them into solver.

I have included 3 sets of Parameters for our model.

These are:

  • Base Case – Forces bucket values to be equal, Allows uneven bucket counts
  • Equal Sized Buckets – Forces each bucket to contain the same number of items
  • Force an error – Which forces an error in the solver model

Load each model and try them at your leisure.

Running the Solver Model

Warning: Solver is a computationally complex add-in, so once your model is setup, Save your Workbook.

Prior to running the model there are a few parameters we should look at to ensure the model solves correctly.

On the main Solver window select the Options button. (Some of these parameters are on the Main Solver window in Solver 2010)

Generally you can accept the defaults but in this case we will change the following

Assume Linear Model – Select

Assume Non-Negative – Select

Note: Solver in Excel 2010 will return a better answer without these 2 parameters enabled by default

The other 2 parameters which you may need to change from time to time is

Precision: Precision is a number from 0 to 1 and higher means more precise

Tolerance: Tolerance shows how far away from a Number, an Integer constraint is allowed to be

The use of the Estimates, Derivatives and Search parameters are beyond the scope of this post. I direct you to the Excel Help on these subjects, by selecting the Help button.

Run the Model

To Run the Model, select the Solve Button from the main Solver menu.

The main status bar in Excel will flash up a number of statistics about the internal workings of the Solver add-in. Generally these flash by and are too fast to read. If a model is too complex it may stall and you won’t see any movement for a while. Solver generally recovers from these problems itself.

 

Once the Solver model finishes it will display a dialog of the results and allow you to do several things

First thing to note is that “Solver Found a Solution.

If it has found a solution, the worksheet cells will be changed to show the solution

You now have 4 options:

  • Run a Report
  • Save a Scenario
  • Return to the model
  • Check Your Results

Run a Report

Run a report by clicking the report you want.

A new sheet will be added to your workbook depending on the report but will be called:

  • Answer Report 1,
  • Sensitivity Report 1
  • Limits Reports 1

etc.

Note, that not all reports are relevant at all times, depending on the Constraints you have applied.

Save a Scenario

Selecting the Save a Scenario button takes you to the Save Scenario dialog.

 

Type in a Name and the Scenario of your model is saved as a Scenario.

Scenarios as available for use in the Scenario Manager, which is accessed from the Data, What-If-Analysis Tab

Return to the model

You can return to your model and either:

  • Keep Solver Solution
  • Restore Original Values

Check the Results

Solver is probably the most Black Box’ish of systems within Excel. As such any results it puts out must be manually checked for suitableness before further use.

These checks for realness, should as a start confirm that the results meet all the criteria supplied.

Are the results roughly what were expected?

Are any Minimums or Maximums violated?

 

What If Solver Doesn’t Find a Solution?

From time to time Solver will return with an error that a “Solver could not find a feasible solution.

When this happens it is indicating one of several possibilities:

  • Your model is over or under constrained
  • Your model constraints are impossible to meet
  • Your model constraints have an error

Start by checking the current constraints for errors and ambiguities

Eg: in our case we have 8 items so requiring the Count of the two buckets to be 20 is impossible to meet

 

My Solver Answer has Strange Numbers?

In solver up to and including Excel 2007, solver would commonly return numbers like 3.5E-18.

This is 0.0000000000000000035, which is effectively 0

If your model returns these, feel free to go through the model and change them to 0, in our model we should also check as the corresponding 1, may in fact be 0.9999999999999999965.

It should be noted that this problem in Solver in Excel 2010 does not occur as often but will still occur.

 

What and How have you used solver in the past?

What and How have you used solver in the past?

Let us know in the comments below:

Your email address is safe with us. Our policies

Written by Hui...
Tags: , , ,
Home: Chandoo.org Main Page
? Doubt: Ask an Excel Question

50 Responses to “Using Solver to Assign Items to Buckets”

  1. Curtis Frye says:

    There is one more setting users should check if they’re getting non-integer answers. In Excel 2010, click the Options button in the Solver window and then, on the All Methods tab, ensure that the Ignore Integer Constraints check box is cleared. If that box is checked, as I think it is by default in Excel 2007 and 2010, you might not get the answer you expect.

  2. Anurag Gupta says:

    Hi Chandoo

    Very interesting post !! I used solver earlier for calculating rate of interest for a required EMI amount for a given loan amount etc..

    In your example , is it possible to get “0″ difference with 9 count of data sets (from 1 to 9) ? Perhaps not…

    Bty,
    Thanks

  3. Matt Healy says:

    Another good use for Solver is doing nonlinear curve fitting. The simpler varieties of nonlinear curve fitting can be done as linear regression on transformed variables (logs, square roots, etc.), but if your nonlinear model is too complex for that approach you can use Solver to minimize your error metric.

    • MANJUNATH says:

      Hi Matt,

      I am working in a construction company. I am trying fit Cum. Actual cost (of the project) Vs Time this with S Curve.
      In y = L/(1+a*exp(-b*t))
      1) Estimated value of L
      2) Applied Linear regression on transformed Variables ( Ln (L/y)-1) Vs t
      But the difference between the actual values (Known values) and predicted values is high.
      My doubt is
      1) How minimize the error using solver?
      2) Is there any other method to forecast/fitting the curve.

  4. annmarie says:

    I used to remember doing this to split mp3s so that there would be roughly equal total song times over 2 CDs, almost like A and B side of an LP. I think I did it by sorting and finding the median point and swap the items around. Another way, instead of trying finding the smallest difference, you would in the same way, try to find a combination which sum has the smallest difference from half the value of the list total.

  5. sam says:

    Has any one tried using solver to do a shopping basket analysis ?

  6. Hui... says:

    @Sam
    Can you elaborate on “Shopping basket analysis”

  7. Jon says:

    Hi,

    Long term visitor of the site – first time posting.

    I don’t understand the need for constraint 3 in the example above (Total items [cell E10] must equal 8). Doesn’t this constraint come ‘for free’ from constraint 1, which states that each cell in the range E2:E9 must equal one? If the 8 cells in the range E2:E9 all have value one, than E10 must have a value of 8?
    It’s obviously still OK to include constraint 3 – I only query it in the vain of “better to under constrain then to over constrain”, or in case I’ve missed something in the example.

    Great website – keep up the good work!

  8. Fred says:

    Thanks Hui! Very interesting. I have got a different, but same answer, result.

    My bucket A has 1, 2, 4, 5, 6 = 18 while bucket B has 3, 7, 8 = 18.

    @Jon I guess you are right too. My approach was
    Each value in column E = 1
    C2:D9 =0
    C2:D9 = integer

  9. JJ says:

    Another thing I have used solver for is calculating the IRR (internal rate of return for a capital expenditure application). The standard Excel formula for IRR is based on the NPV function and (as I remember, but Excel help couldnt tell me!) assumes that the cashflows occur at the end of the period. For an operating asset this is incorrect as the asset would normally be making money all year, so the correct approach is to do your NPV and IRR based on mid point cashflows.
    Thus I set up my model to calculate NPV the long way using mid point cash flows, then used solver to work out the rate-of-return when NPV=0 which is the IRR.

  10. Gary says:

    Hi,
    This is a very useful aiticle for me. But I have a serious question here:

    When I try to add the Solver add-in I get the following
    error message:

    “Macro error at cell:
    [SOLVER.XLA]Excel4Functions!A31″

    Can you pls help me how to make Solver load?

    Ps: My Excel version is 2003.

    Many Thanks

  11. sam says:

    @Hui

    “The term market basket analysis in the retail business refers to research that provides the retailer with information to understand the purchase behaviour of a buyer. This information will enable the retailer to understand the buyer’s needs and rewrite the store’s layout accordingly, develop cross-promotional programs, or even capture new buyers (much like the cross-selling concept). An apocryphal early illustrative example for this was when one super market chain discovered in its analysis that customers that bought Chips often bought beer as well, have put the Chips close to beer coolers, and their sales increased dramatically.”

    Assume you sell 5 products to hundreds of clients.
    You want to know which two products are there in everyones shopping basket

    Typically your data would look like this

    Order_No Client Product Qty Amt
    1 ABB A 10 124
    1 ABB B 5 545
    1 ABB C 4 54
    2 AREVA B 3 434
    2 AREVA D 3 4
    …….

    We need to find out which combination of two products where there is everyones shopping basket.

    So was it A&B, or B&D or C&A et

  12. Hui... says:

    @All
    There are a number of solutions to this problem which all satisfy the various criteria
    This problem is not uncommon using solver, but rarely seen in complex problems, in this case it is easily demonstrated.
    .
    Normally you would add more criteria to try and constrain the options solver has
    .
    I think Solver uses the current cells values as starting points for its internal workings and so if you put different values in different cells you will often get a correct but differing solution.
    There also appears to be small differences between different versions of Excel Solver, they must have made some tweaks interavlly along the way.

  13. Gary says:

    Hi Hui
    Sorry to bother you.
    I dont understand and can you pls send me a download linkage of Solver.xla?

    Thanks.

  14. Hui... says:

    @Gary
    I was referring to the section on the Tools Menu, which is further down the page, by Dana DeLouis.
    .
    Do you have the Tools Menu displayed ?
    It looks like it has to be displayed before Solver will be loaded

  15. Scott Green says:

    I solved this with formulas only – no add-in tools, no VBA, nothing but formulas:

    http://i51.tinypic.com/29bziic.png

  16. sam says:

    @Hui, Cant be done with a Pivot, This is a very calculation intensive task.
    If you can share your e-mail, I can send you a sample problem to help you understand the problem

  17. General Ledger says:

    Excellent posting!! During my career I never had a problem so complex that I needed to use Solver. I have used Solver’s little brother, Goal Seek, a few times. This is great when you need to determine one value to achieve a certain result for a calculation.

    I liken using Goal Seek to the process of completing an income tax return. You start by entering known values you can not alter such as how much you were paid and how much tax was withheld. Go to the end of the return and fill in the amount of tax you want to owe or receive as a refund. Then use solver to work through the calculation of deductions, credits and tax tables to determine how much you would have to adjust a value to achieve the desired tax result.

  18. [...] greater than one with a negative value as the first cash flow. For a guide to using solver, go to http://chandoo.org/wp/2011/05/11/using-solver-to-assign-item/. Chadoo is a great source for all things [...]

  19. Steve Sexton says:

    Nice article but I do not know if you are aware that Microsoft products have built-in spelling checkers. You may want to familiarize yourself with its operation. :)

  20. Sohail Khan says:

    ‘=IF(a35=””,””,(DATE(2012,8,14)=A35,”Independence Day”,IF(DATE(2012,12,25)=A35,”Crismas Day”,IF(DATE(2012,2,5)=A35,”Kashmir Day”,IF(DATE(2012,3,23)=A35,”Pakistan Day”,IF(DATE(2012,5,1)=A35,”Labour Day”,IF(DATE(2012,11,9)=A35,”Iqbal Day”,CHOOSE(WEEKDAY(A35),”Sunday”,” “,” “,” “,” “,” “,”Saturday”)))))))
    But Excel give error. A35 is equal to date

    • Hui... says:

      It should be:
      =IF(A35=””,””,(IF(DATE(2012,8,14)=A35,”Independence Day”, IF(DATE(2012,12,25)=A35,”Crismas Day”, IF(DATE(2012,2,5)=A35,”Kashmir Day”, IF(DATE(2012,3,23)=A35,”Pakistan Day”, IF(DATE(2012,5,1)=A35,”Labour Day”, IF(DATE(2012,11,9)=A35,”Iqbal Day”, CHOOSE(WEEKDAY(A35),”Sunday”,” “,” “,” “,” “,” “,”Saturday”)))))))))

      Please note that if you copy/paste this you will need to retype all the ” characters as they may look like ” characters but they aren’t

  21. mukesh kumawat says:

    sir,

    me excel me 1 sheet me  raw  ko jaise

    1  05.06.12   paint    50 nos   colour use    received

    2  06.06.12  bulb      10 nos   lighting        non recd

    3  07.06.12  pen      05 nos    stationery     received

     sheet me non recd  items ko ydi 2sri sheet  me only unhi raw ko list type me  hi chahta hu to wo kaise hoga jise mujhe pata chal jaye ki ye list non recd item ki hi h only qki ye list adhik      
      

  22. Tomer says:

    Hi,

    Great article!

    Any ideas on how to extend your example to 3 buckets (or more)?

    I can’t seem to find a formula for the “target cell” that will still be linear for the simplex to work.

    Thanks 

  23. [...] Solver add-in: Chandoo’s blog is an excellent place to know more about this add-in. Xlsx file used in this quiz can be [...]

  24. DJV says:

    Thanks for the various articles of various ages. I am pretty good at excel but have until recently not used solver. I have the following use which works well for me.
    I work at a mine, we have a target end of year production with constraints…
    We do not want to go slower than X or faster than Y
    X and Y are usually fixed, but some months we accept lower throughput due to wet season causing transport issues etc. As a result I have a set of constraints that vary each month. Usually we just eyeball the spreadsheet, make up numbers, readjust then publish, THEN realise we made an error because something is a bit odd (yes we should put in conditional formatting).
    We have a stockpile of feed material, we do not want it to go below a certain value, again there is an ideal but sometimes we have to accept a lower stockpile. This reduces our buffer and blending so not ideal.
    Each month we have previous stockpile, incoming ore or variable quality (which is never the same two months in a row as mining is dynamic), processed material and output concentrate.
    So I use solver as follows (more or less).
    Each value (ie throughput, deliveries) or constraint (max tonnes per hour, minimum stockpile) has its own data row, each month has it’s own column (its a data table duh!)
    Monthly output is rolled up to an end of year figure. Solver is set to maximise output (or resolve to the budget value) for that figure.
    with the saved solver something like [my comments in brackets]
    =MAX($O$51) [maximise result]
    =COUNT($I$16:$N$16) [Change these cells]
    =$I$16:$N$16>=’Processing Physicals (MAX)’!$I$79:$N$79 [throughput faster than this value which is different for some months]
    =$I$16:$N$16<=’Processing Physicals (MAX)’!$I$80:$N$80 [throughput lower than this value which is plant max throughput capability and sometimes deliberately lower]
    =$I$56:$N$56>=’Processing Physicals (MAX)’!$I$81:$N$81 [ensure the stockpile is never lower than what is specified for each month]
    I input the new anticipated mined tonnes and grades then run solver to optimise production plan. So this takes about 0.5 seconds to run, gives a robust solution and we can still easily change constraints for each month if we feel it is reasonable.
    i think this is a great use of solver and has saved a lot of mucking about as we change forecasts several times during the monthly planning phase so used to spend AGES re jigging to try to make the end figures match budget, or maximise, or whatever the mine manager thinks of while walking down the hallway (very dilbert)
    Hope that helps and inspires. can I provide an example? really? maybe one day. apologies if that all sounds complex, its really pretty simple.
     

  25. Sami says:

    Try the book Step-By-Step Optimization With Excel Solver – the Excel Statistical Master (Excel Master Series) by Mark Harmon. You gonna love it and i am sure you will start preparing a video on it :-)

  26. derick says:

     thanks for your post, I tried to use solver on a modelling question but it keeps saying “set target cell must be a formula” I have tried all I can but still couldn’t get it. Please how do I solve this?  . ha

  27. [...] Hi, One option is to use the Solver add-in that comes with Excel. Your objective would be to set B4 to the known value for your result, by changing cells B1:E1. You could also add any constraints / other options as necessary. If you Google the topic, there are lots of examples on how to use it, here's one to get you started: Using Excel and Solver for problem solving, a practical tutorial. | Chandoo.org – Learn Microsoft Ex… [...]

  28. Nancy Day says:

    I have a problem I project management and I have excel OM 2010 o my computer. I need to know how to enter an AON problem into the computer to get it into the excel program can someone help me?

  29. Alok Joshi says:

    Very informative article. Keep up the good work.

  30. Cosmic Singh says:

    Hi!
    I am using Excel Solver in Excel 2007. It is working fine. But the problem I am facing is whenever I am changing the values of the constraints, Excel Solver isn’t automatically updating the solution. Because of this every time I have to click the ‘Solve’ button in Excel Solver.
    Please Help me on how to get the solution automated with changed values of constraints.

  31. myra says:

    I will be training others on Excel Advanced concepts. I’m looking for a simple layman’s explanation of the three choices in the Excel 2013 version of Solver: Simplex LP, GRG Nonlinear & Evolutionary. Can anyone help me with this?

    When I go to Excel help I am redirected to http://www.solver.com

    There I find very long winded, technical explanations. I contacted them also and still could not come up with an explanation.

  32. Saman says:

    Dear Friends,
    i am working with excel but i am new for excel. i have face for the following issue. please help me if someone know the soultion….
    i am feeding data to sheet A machine breakdown details as follow.
    Machine breakdown time
    Start Date End Date Machine
    1/1/2014 6:00 1/3/2014 13:00 X
    1/1/2014 12:00 1/2/2014 1:20 Y
    1/1/2014 22:00 1/2/2014 2:00 Z
    and i need to get fill automaticall following breakdown hours respect to each dates

    Machine breakdown Hours
    X Y Z
    1/1/2014
    1/2/2014
    1/3/2014
    1/4/2014

    please help me

    • Hui... says:

      @Saman

      I would add another column as Breakdown Time
      =End date-Start date

      Then make a pivot table of the Machine and Breakdown Time

      If you can upload a sample file that may be more help

  33. Aditya says:

    Hello sir i want irr exel sheet down loding so plz hlp me
    i have good irr exel sheet but not option advance emi ontions so i want a advance emi option irr exel sheet so plz help me and plz send my mail me

  34. adnan saif says:

    Sir i have a problem…
    If we have two values X & Y .
    X is kept constant. Only i can change y and and the answer is also kept constant that is Z.
    X*Y=Z how to solve this question in excel please can anyone help me..its urgent.

    • Hui... says:

      @Adnan
      You can use a couple of techniques
      1. Use Algebra ie: Z=X*Y then Y=Z/X
      2. Use Goal Seek

      However if X and Z are fixed then there will only be one value of Y = Z/X

  35. sanjoy adhikary says:

    dip wid bal
    10
    0 20 30
    12 0 18
    =IF(A3>=0,C2+B3,IF(B3>=0,C2-A3,0))
    please solve this problem

Leave a Reply