Year 12s: what will be the first way you research your future options? >>

Trouble with linear programming in excel solver

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!

Scroll to see replies

Reply 1

ghostwalker

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.

Reply 2

ztibor

Original post by MBF

Use the square of deviaton it is always nonnegtaive.

Reply 3

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. 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!

Reply 4

ghostwalker

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?

Reply 5

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?

problem.xlsx11.0KB

Reply 6

ghostwalker

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.

Reply 7

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.

(edited 11 years ago)

Reply 8

ghostwalker

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.

Reply 9

MBF

Okay, thanks so much for your help so far. The algorithm I am supposed to be using is the simplex LP.

Reply 10

ghostwalker

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.

(edited 11 years ago)

Reply 11

MBF

It does seem to work, I assume you meant U11 and not U12, am I right?

(edited 11 years ago)

Reply 12

ghostwalker

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 - ~@#? Microsoft.

Reply 13

MBF

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 =]

Reply 14

ghostwalker

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.

Reply 15

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

optimisation problem.xlsx55.4KB

Reply 16

ghostwalker

Original post by Achiaku

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.

Reply 17

mamaH

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>=E5 :colone:

33 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<=E77 :colone:

79 i.e. total energy value from items in this food group not to exceed maximum energy required from this group
(5) C77:C79>=E77 :colone:

79 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<=D5 :biggrin:

33 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) E41 :colone:

69>=F41:F69 this is the negative version of the objective
(9) E41 :colone:

69>=G41:G69 this is the negative version of the objective

I am running excel solver for MAC 2011.

Regards

Screen Shot 2015-06-12 at 21.20.50.png42.6KB

Reply 18

ghostwalker

Original post by mamaH

(8) E41

69>=F41:F69 this is the negative version of the objective
(9) E41 :colone:

69>=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.

(edited 8 years ago)

Reply 19

mamaH

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

Screen Shot 2015-06-12 at 23.21.33.png43.8KB