Issue with Solver Binary Constraints

[NougatBike]

Hello!

I have a portion of a homework problem I don't know how to resolve. In the problem, I have a set of five parts to be produced where A+B+C add up to one product with a demand of 7000, and A+D+E add up to another with a demand of 5000. They can be produced in my home factory at a lower cost per item but with a one-time set-up fee per type of item produced, or outsourced for a higher per item cost but with no set-up fee. The lesson demands that this be done with a linear programming model.

Setting up everything but the one-time fee is no problem and Simplex LP will solve it with no issues. Once I try to factor in the one time fee, however, nothing works - I've tried setting up if/then statements reliant on >0 production in a particular item category, and I've set up binary constraints to do the same thing. As soon as that conditional "will I use the factory for that item and incur the fee or not" element is put into the spreadsheet in any way I know, Simplex LP won't play ball anymore.

Parts A,B,C combine into a product, which I need 7000 of. Parts A,D,E also combine into a product I need 5000 of, so I need exactly 12000 of part A, 7000 of B and C, and 5000 of D and E. The 30000 is a time constraint in the same units(minutes) as the time-per-part is expressed in; this is the most time my home factory has to spare. The overall objective is to determine what amount of which parts should be made in the home factory or outsourced, minimizing the cost.

I'm pretty sure I just don't understand the material very well, or I'm missing an entire concept somewhere. I've attached a screenshot of the spreadsheet as it's set up currently below. I definitely don't need anybody to do my homework for me or anything like that, but a nudge in the right direction would be amazing.

Capture.PNG

[Alf]

I think you better upload your sample file.

There are a least one constrain you have not specified in your post i.e. F15 <= 30000, then I'm not sure about I3 = 7000 and I4 = 7000 and I5 = 5000 and I6 = 5000

Is not the problem that you should produce 7000 and 5000 either at your home factory or it being being outsourced and solver should decide what should be produced where based on the lowest total cost for the total production of A+B+C and A+D+E.

Alf

[NougatBike]

Sorry, my mistake - I didn't realize I had left that out. Parts A,B,C combine into a product, which I need 7000 of. Parts A,D,E also combine into a product I need 5000 of. The 30000 is a time constraint in the same units(minutes) as the time-per-part is expressed in. The overall objective is to determine what amount of which parts should be made in the home factory or outsourced, minimizing the cost.

[Alf]

Sorry, my mistake - I didn't realize I had left that out

Well really you had not, my bad really as I didn't read you posting properly.

So I set up a model, had to guesstimate a bit as not all was obvious. Not happy with the result because Solver complained about problem not being a proper linear one so I
had to run it using the GRG-Nonlinear engine. Can't see why this problem in not linear.

The second problem was setting up the constraint to make solver find the optimal solution. Analyzing the cost difference it was obvious that the lowest cost would be found
by not buying sub component A, B and D but saw that the in-house time was a limiting factor so in the end I added the constraint that range F2:F4 = 1 to get the best lowest
cost solution.

Well there you are, I'll upload the modified file as it's not a 100 % solver found solution but when you get the right solution to this problem I would appreciate it if you
could post that file in this thread.

Alf

[NougatBike]

That's about what I was running into as well - it won't treat it as a linear problem no matter what I do. I think that's fine, though - if other people who are better at excel than me are running into the same issue, I'm now wondering if the problem itself is just poorly constructed/worded.

Thank you very much for your help!

[Alf]

Having another go at the problem and made a slightly different setup it now runs as a linear problem.

Don't know why this made a difference but it does. Still setting values of 1 in the range F2:F4 bothers me, had a similar problem some time ago and got a solution
using the "Evolutionary" engine in the solver set up. But this solution was not as optimal as the one I got when I used fixed values i.e. 1 in several cells.

Oh well this solution gives same result i.e. 50575 as the min value in cell L2 even if the production / buy pattern is different.

Alf

[NougatBike]

So I'm basically getting the same thing - between your work and me messing with it I've isolated that what solver particularly doesn't like is the "open" cells being considered variable cells if anything else in the problem is dependent on them, even without the binary constraint. Once you include them as variable cells, solver refuses to touch it. If they aren't variables and you just treat them as a manual on-off switch, it's fine then and it will do the problem. So I'm basically concluding that the problem isn't doable in the way they want me to do it, and I'm going to say as much in the assignment and see where that gets me. Thanks again!

[Alf]

what solver particularly doesn't like is the "open" cells being considered variable cells

Yes that seems to be the root of the problem. I've also tested the setup with the "OpenSolver" a much more powerful linear solver than the excel one. But also this solver can't cope with this problem.

Still it does not tell problem is not linear but it ignores the range I2:I6 so all sub components gets bought nothing is produced in the home factory.

Link for dowloding OpenSolver in case you are interested:

https://opensolver.org/

So using solver I do think that the "Evolutionary" solver engine may give you a solution to this problem but how good I don't know.

The problem I solver by using the "Evolutionary" engine see file in post #4 and the much better solution when applying a bit of logic to the problem in post 6 where the problem can be solved as a Simplex linear problem.

https://www.excelforum.com/excel-gen...ml#post4756303

So normal solvers like excel's Simplex LP and the GRG is not up to tackle problems of this kind nor will the "OpenSolver" manage this. The "Evolutionary" engine may manage
to do this but it's not sure that one gets the best possible solution.

Alf

[shg]

( deleted )

I couldn't improve on Alf's solution.

[Alf]

Thanks for rep shg

Alf

[Hydraulics]

I hope it's not too late for your homework assignment. Since you are asking for hints I will not (yet) give you the final solution.

First, the simplex algorithm can deal only with linear constraints. But in your formula expressing the built price you have the product of two variables: the binary one indicating the presence of fixed costs and the quantity to be produced. Your constraint should be in the form

T = Fy + vx

where y is binary, x continuous (integer, actually), and F and v are fixed and variable costs, respectively.

However y and x are not independent from each other. y can be 1 only when x>0, otherwise it must be zero. This means we must add a constraint, that is usually expressed as

x -My <= 0

where M is a constant "large enough" not to interfere with already given constraints. In the last equation, if y is zero, x is forced to zero as well. And when y is 1, x remains bounded from the other conditions.

As for remaining constraints on total quantities, I suggest you to express them as given (A+B+C = 7000 and A+B+E = 5000). Your assumptions on single amounts is incorrect.

If you still need it, I will post the solution.

(As a check, and if I'm not mistaken, the solution has a minimal cost of 4000)

[Alf]

Hi Hydraulics

I would like to see algorithmic solution so could you please post it.

By the way did you realize that the deciding factor for solving this problem is the max time that the home factory can use in the production? Max time is set to 30000 minutes and the table in the uploaded file shows setup time for a part + a production time for that particular part

a_home_work.jpg

So F (fixed ) should be equal to setup time and v (variable) should be production time/unit

Alf

[Hydraulics]

Hi Alf,

here is the solution. The solver is already set.

[...]
By the way did you realize that the deciding factor for solving this problem is the max time that the home factory can use in the production?
[...]

Well, not really. Time is a limiting factor (constraint) exactly as the demand that A+B+C = 7000.

Set up is a one-time fee (a typical situation in these kind of problems).

[...]
In the problem, I have a set of five parts to be produced where A+B+C add up to one product with a demand of 7000, and A+D+E add up to another with a demand of 5000. They can be produced in my home factory at a lower cost per item but with a one-time set-up fee per type of item produced, or outsourced for a higher per item cost but with no set-up fee.
[...]

Outsourcing a piece means paying a variable cost, and nothing else.

Producing it internally incurs in a set up fee, a variable cost and a time spent.

[Alf]

Not sure you read properly what OP wrote in post #1. Well I didn't the first time But eventually I saw my error

Parts A,B,C combine into a product, which I need 7000 of. Parts A,D,E also combine into a product I need 5000 of, so I need exactly 12000 of part A, 7000 of B and C, and 5000 of D and E.

So the OP needs 12000 of A, 7000 of B and C and finally 5000 of D and E. For my solution I assumed the OP meant 7000 of B, 7000 of C, 5000 of D and also 5000 of E in order to make 7000 and 5000 combined units. If you can see his solver setup (try open it on a separate tab by right clicking on the image) on the posted image you will see that I3 = 7000, I4 = 7000, I5 = 5000 and I6 = 5000 so I thinks that confirms my assumption.

Alf

[Hydraulics]

Not sure you read properly what OP wrote in post #1. Well I didn't the first time But eventually I saw my error

Alf, actually I did read. And I already pointed out in my first message that subsequent assumptions about single product quantities are incorrect.

This is the original problem statement (and again, this is a rather common setup for these basic linear programming problems)

In the problem, I have a set of five parts to be produced where A+B+C add up to one product with a demand of 7000, and A+D+E add up to another with a demand of 5000.

A+B+C=7000
and
A+D+E =5000

does not imply that

So the OP needs 12000 of A, 7000 of B and C and finally 5000 of D and E.

Do we agree?

[Alf]

Do we agree?

Don't think it matters if we agree or not, the issue here is what did the OP mean when he wrote

Parts A,B,C combine into a product, which I need 7000 of. Parts A,D,E also combine into a product I need 5000 of, so I need exactly 12000 of part A, 7000 of B and C, and 5000 of D and E.

and until he enters this discussion and settle this issue I see no point in discussing it.

Alf

[shg]

A+B+C=7000
and
A+D+E =5000

does not imply that the OP needs 12000 of A, 7000 of B and C and 5000 of D and E.

I took it to mean exactly that, and would be surprised it it were otherwise.