Join TSR now and get all your revision questions answeredSign up now

Trouble with linear programming in excel solver Watch

    • Thread Starter
    Offline

    0
    ReputationRep:
    Hi there,

    I am currently having problems with Excel solver, as the title suggests. My Linear programme consists of trying to minimise the deviation of certain percentages, some positive, some negative. To find the deviation of all these percentages I need the absolute values, but I can't use the absolute function with the Simplex LP method. Is there a way around this?

    Thank you in advance!
    • Study Helper
    Offline

    13
    (Original post by MBF)
    ...
    If the problem is in the object function, e.g. "minimise |a|", then
    you can change it to "minimise b".

    With the constraints
    a <= b
    -a<=b

    Adapt as necessary.
    Offline

    3
    ReputationRep:
    (Original post by MBF)
    Hi there,

    I am currently having problems with Excel solver, as the title suggests. My Linear programme consists of trying to minimise the deviation of certain percentages, some positive, some negative. To find the deviation of all these percentages I need the absolute values, but I can't use the absolute function with the Simplex LP method. Is there a way around this?

    Thank you in advance!
    Use the square of deviaton it is always nonnegtaive.
    • Thread Starter
    Offline

    0
    ReputationRep:
    Hi guys, thanks for your efforts.

    Unfortunately it's the sum of the deviations I am trying to minimise, so I was trying to find the absolute values of the deviations and sum those. This means ghostwalker's suggestion can't help. ztibor's suggestion of squaring the deviations won't work either as it is not satisfied by the linearity conditions.

    Any other suggestions would be greatly appreciated, I'm starting to stress out now!
    • Study Helper
    Offline

    13
    (Original post by MBF)
    Hi guys, thanks for your efforts.

    Unfortunately it's the sum of the deviations I am trying to minimise, so I was trying to find the absolute values of the deviations and sum those.
    The technique I was suggesting is the standard one for dealing with absolute values in the objective function. If there are 10 absolutes values you need to minimize the sum of, then you need to create an additional 10 variables and 20 constraints. I was just showing one as an example.

    Can you not use that method?
    • Thread Starter
    Offline

    0
    ReputationRep:
    I'm afraid I still don't understand, I've provided my excel sheet, any chance you could explain it in regards to my problem?
    Attached Files
  1. File Type: xlsx problem.xlsx (10.7 KB, 180 views)
    • Study Helper
    Offline

    13
    (Original post by MBF)
    I'm afraid I still don't understand, I've provided my excel sheet, any chance you could explain it in regards to my problem?
    Humm!

    Just loaded Solver into Excel and tried your spreadsheet and I get 0.07 as the parameter when I use Solver and 235.97% as the min value of sum of abs.

    It had no problems with the absolute values.

    Wasn't a linear programming problem.

    Puzzled.
    • Thread Starter
    Offline

    0
    ReputationRep:
    I know it works as a non-linear programme, but it has to be a linear programme, is there any way of doing this? I can't use absolute values or square values.
    • Study Helper
    Offline

    13
    (Original post by MBF)
    I know it works as a non-linear programme, but it has to be a linear programme, is there any way of doing this? I can't use absolute values or square values.
    I've only just loaded Solver, and I'm not familiar with the set up, and how one tells it to use linear programming even.

    But somehow it needs to use dummy variables, and I can't see how that works in Solver.

    I'll have a think/Google on it.
    • Thread Starter
    Offline

    0
    ReputationRep:
    Okay, thanks so much for your help so far. The algorithm I am supposed to be using is the simplex LP.
    • Study Helper
    Offline

    13
    (Original post by MBF)
    Okay, thanks so much for your help so far. The algorithm I am supposed to be using is the simplex LP.
    OK, I think we have a solution.

    Ditch the line with absolute values.
    Create a new row 10, with values the negative of row 9. E.g. Cell C10 has contents "=-C9", without the quotes of course.
    Create a new row 11 columns B to T and assign initial value 100% (not sure if initial values are entirely necessary).
    Let cell U11=SUM(B11:T11)

    Then in Solver.
    We wish to minimize U11, varying the contents of B7,B11:T11
    And subject to B9:T9:<=B11:T11
    and B10:T10<=B11:T11

    This is just implementing the method I originally outlined, as best I can guess, but it does work. Hopefully I got it right.
    • Thread Starter
    Offline

    0
    ReputationRep:
    It does seem to work, I assume you meant U11 and not U12, am I right?
    • Study Helper
    Offline

    13
    (Original post by MBF)
    It does seem to work, I assume you meant U11 and not U12, am I right?
    Yep. And there were a couple of mistakes with the constraints, that I've now corrected - hopefully. Getting my rows and columns mixed up - [email protected]#? Microsoft.
    • Thread Starter
    Offline

    0
    ReputationRep:
    Okay brilliant, it works perfectly, thank you! Unfortunately it is a long process using it as a solving method since excel cannot handle changing all the variables for one full answer. I'd have to use solver over a thousand times for this work, but at least the answers produced are the same for the GRG nonlinear method.

    Again, thank you, you're a lifesaver =]
    • Study Helper
    Offline

    13
    (Original post by MBF)
    Again, thank you, you're a lifesaver =]
    You're welcome - it was an interesting question.

    I notice that Solver is quite restrictive in the number of changing variables it will allow - looks to be about 200.

    If you have masses of data that needs processing in one go, then Solver isn't going to be able to do it - as far as I can see. But there may be some freeware out there that can handle medium+ size linear programmes.

    If you have many batches of smaller size in a table say, then it would be possible to write a macro to process each batch in turn, and you could leave it to run.

    Good luck with it. G.
    Offline

    0
    ReputationRep:
    HI,I read your post and I am facing the same problem. I am minimising relative deviations from the mean and the objective function is an absolute value. I tried following the suggested procedure and I fail to get any results. could you please help?Achi
    Attached Files
  2. File Type: xlsx optimisation problem.xlsx (54.1 KB, 79 views)
    • Study Helper
    Offline

    13
    (Original post by Achiaku)
    HI,I read your post and I am facing the same problem. I am minimising relative deviations from the mean and the objective function is an absolute value. I tried following the suggested procedure and I fail to get any results. could you please help?Achi
    I'm only running version 12, and your spreadsheet is beyond the capabilities of that version.

    I do note you seem to be trying to minimize E70 (at least according to my version) which has me puzzled.

    A bit of explanation of the constraints may help, but I can't guarantee it.
    Offline

    0
    ReputationRep:
    Hi,Thanks for your response. Yes I am optimising E70 which is the sum of relative deviations from the mean ... m-X/m. The objective function itself should be in absolute value i.e. minimise the sum of the absolute values of relative deviations from the mean ∑|m-X|/m since the simple relative deviation might be positive or negative.

    As to the constraints:
    (1) C41:C69<=F5:F33 i.e. optimal energy intake value should not exceed maximum energy limit
    (2) C41:C69>=E533 i.e. optimal energy intake value should not be less than minimum energy limit
    (3) C70>=C73 i.e. the minimum recommended energy allowance
    (4) C77:C79<=E7779 i.e. total energy value from items in this food group not to exceed maximum energy required from this group
    (5) C77:C79>=E7779 i.e. total energy value from items in this food group not to be less than minimum energy required from this group
    (6) H70<=1200 i.e. total expenditure on food not to exceed 1200 Tanzanian shillings (equivalent to half a euro)
    (7) I41:I69<=D533 i.e. the total food portion not to exceed the maximum daily limit

    these below are for the solution you had suggested on linearising the absolute value of the objective function

    (8) E4169>=F41:F69 this is the negative version of the objective
    (9) E4169>=G41:G69 this is the negative version of the objective

    I am running excel solver for MAC 2011.

    Regards
    Attached Images
     
    • Study Helper
    Offline

    13
    (Original post by mamaH)

    (8) E4169>=F41:F69 this is the negative version of the objective
    (9) E4169>=G41:G69 this is the negative version of the objective

    I am running excel solver for MAC 2011.

    Regards
    I don't think those are what I was suggesting in my second post.

    E70 is the sum of the relative deviations from the mean, BUT you want to minimize the sum of the absolute values of the relative deviations from the mean, so E70 doesn't cut it.

    G70 is what you want to minimize and this the sum of the "b"s I refer to in post #2.

    Also the two constraints I highlighted want to be:

    E41: E69<=G41:G69 and

    F41: F69<=G41:G69

    Then solving you want to allow G41:G69 to vary and also C41:C69 I think. I am partly guessing this bit as it's a good couple of years since I looked at this, and I can't try it out myself to check.
    Offline

    0
    ReputationRep:
    Thanks Ghostwalker
    I only find the solution when I remove the minimum recommended energy constraint (3). I guess I have over-constrained my model.

    I have changed my variable cells to C41 : C69. Please see the attached. However i do not understand your comment on allowing G41:G69 to vary and also C41:C69. I there a way of allowing both these cells to vary?

    Thanks again
    Attached Images
     
 
 
 
Poll
Which web browser do you use?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Quick reply
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.