Industrial Engineer

You can talk about anything here

Moderator: Global Moderator

User avatar
IndyBrit
N3O Officer
N3O Officer
Posts: 1318
Joined: Tue Feb 05, 2008 1:53 am
Location: Indianapolis

Re: Industrial Engineer

Post by IndyBrit »

I don't want to denigrate another poster who's trying to help you, especially in a 3rd party forum. However, I don't think he appreciates the problems with using Solver in this circumstance. This problem is a minefield of local minimums, and Solver only has all of those wonderful properties he describes in a well behaved solution space. Therefore, unless you know you're starting near a good minimum, Solver will not miss the best solution "not by much."

Example - I ran Solver from zero units initial condition and got 16 catapults and 44 paladins for 3892 wasted resources, or over 3000 better than his (showing the variability of the Solver solution, not the superiority of my random inputs). Then, I ran it again with an initial condition of five units of each type, and got (in order) 5-4-5-5-3-0-5-9-5 of each unit, with 5992 wasted resources, still about 1000 better than his number but 2000 worse than the first attempt. If you change the initial conditions, you will continue to get random answers which only represent the "optimum" that is nearest to the point you started.

As a side note - there is also an error in his solution, in that it does not seem to have a wasted population contribution (his wasted resources are listed at 5920, but are actually 7020 as I understand the problem).

Therefore, this requires either a transformation of the solution space to something more well behaved for Solver to crunch (which I described above by re-thinking the error term), or it requires a solution method that is robust to abundant local minimums (which will be programmatical).

I agree with his points "1" and "2" on each method, but his point "3" is incorrect, unless wasting at least 80% more resources than needed is considered not missing optimal by "much."
User avatar
GreenDude
Captain
Captain
Posts: 213
Joined: Sun Aug 10, 2008 6:17 am
Location: Concord, CA
Contact:

Re: Industrial Engineer

Post by GreenDude »

OK, i will let you guys know when I figure out what you are saying and when my brain stops overheating. My brain's PSU has exploded :-P
Image
Image
User avatar
Wetmelon
Honorary Member
Honorary Member
Posts: 190
Joined: Wed Sep 10, 2008 8:49 am
Location: London, ON

Re: Industrial Engineer

Post by Wetmelon »

[quote=""IndyBrit""]I don't want to denigrate another poster who's trying to help you, especially in a 3rd party forum. However, I don't think he appreciates the problems with using Solver in this circumstance. This problem is a minefield of local minimums, and Solver only has all of those wonderful properties he describes in a well behaved solution space. Therefore, unless you know you're starting near a good minimum, Solver will not miss the best solution "not by much."

Example - I ran Solver from zero units initial condition and got 16 catapults and 44 paladins for 3892 wasted resources, or over 3000 better than his (showing the variability of the Solver solution, not the superiority of my random inputs). Then, I ran it again with an initial condition of five units of each type, and got (in order) 5-4-5-5-3-0-5-9-5 of each unit, with 5992 wasted resources, still about 1000 better than his number but 2000 worse than the first attempt. If you change the initial conditions, you will continue to get random answers which only represent the "optimum" that is nearest to the point you started.

As a side note - there is also an error in his solution, in that it does not seem to have a wasted population contribution (his wasted resources are listed at 5920, but are actually 7020 as I understand the problem).

Therefore, this requires either a transformation of the solution space to something more well behaved for Solver to crunch (which I described above by re-thinking the error term), or it requires a solution method that is robust to abundant local minimums (which will be programmatical).

I agree with his points "1" and "2" on each method, but his point "3" is incorrect, unless wasting at least 80% more resources than needed is considered not missing optimal by "much."[/quote]

I wasn't trying to put you or your ideas down either, though, Indy. I was simply sending you to that forum as I had answered essentially all of the same questions that you were posing :P

I follow what you're saying though, and I realize that brute force is really the more accurate solution, but you're also right on another front: You have to have some sort of beginning "Guess". For example, I ran through this math by hand and got close, though I was still off by quite a bit, it was close for doing it by hand. This required simply a brute force approach, but with an initial guess. Without that initial guess, (Possibly user-inputed if it has to be :() then every method will have issues...
TheRam
N3O Member
N3O Member
Posts: 530
Joined: Fri Mar 29, 2013 9:31 pm

Re: Industrial Engineer

Post by TheRam »

[quote=""GreenDude""]My brain's PSU has exploded :-P[/quote]
You son of a gun...
User avatar
IndyBrit
N3O Officer
N3O Officer
Posts: 1318
Joined: Tue Feb 05, 2008 1:53 am
Location: Indianapolis

Re: Industrial Engineer

Post by IndyBrit »

No worries, I didn't feel attacked at all.

The method I suggested provides an initial guess, so that's not needed if you solve programmatically. In fact, if you were wanting to get the "best" solution, you would probably combine brute force to develop an initial guess, and then use Solver (or an equivalent optimization routine) to ensure you had the best possible solution within the area of the solution space that your brute force method put you into. Solver could be called by the program at the end, or you could just let the program find it's best attempt and then run Solver manually to tweak the final result.

Think of this problem as a field with a bunch of wells. The "best" solution is the very bottom of the deepest well. The brute force method yells into all the wells to see about how deep they are, and will be unlikely to miss a well (depending on how much brute force you are willing to use), but is not particularly good at putting you into the bottom of that deepest well. Solver (rather, the underlying optimization routine) is really good at running to the nearest well and getting all the way to the bottom. Where there is only one well, or where all the wells are about the same depth, that's perfectly fine.

Your problem is a "knapsack" problem, which optimization routines are notoriously bad at solving. Using an optimization routine on a knapsack problem (without more, at least), is the third classic blunder. The first two are well known of course, never start a land war in Asia and never go against a Sicilian when death is on the line. So now you know #3.
User avatar
IndyBrit
N3O Officer
N3O Officer
Posts: 1318
Joined: Tue Feb 05, 2008 1:53 am
Location: Indianapolis

Re: Industrial Engineer

Post by IndyBrit »

[quote=""Kaiser_von_Nuben""]liberal arts brain... mush![/quote]

But you repeat yourself. :-P

Have a feeling some of my vils are going to pay for that one... :D
User avatar
Soccerman771
N3O Officer
N3O Officer
Posts: 2874
Joined: Fri Jan 18, 2008 7:25 am
Location: Sachse, Texas (near Dallas)
Contact:

Re: Industrial Engineer

Post by Soccerman771 »

[quote=""IndyBrit""]Your problem is a "knapsack" problem, which optimization routines are notoriously bad at solving. Using an optimization routine on a knapsack problem (without more, at least), is the third classic blunder. The first two are well known of course, never start a land war in Asia and never go against a Sicilian when death is on the line. So now you know #3.[/quote]

Knapsack problems are solved best by linear programming. I just haven't had the time to go through the motions.

This is a good example of an overview of LP:
http://www.math.ucla.edu/~tom/LP.pdf
jtackel@hotmail.com

"Do you know how difficult it is to micro Napalm?" - Lazy_Tuga

"This isn't going to work. I've picked a water deck and there isn't even a pond on this map." - Blackadderthe4th
User avatar
Kaiser_von_Nuben
Honorary Member
Honorary Member
Posts: 2186
Joined: Fri Jul 04, 2008 11:40 pm
Location: New York, NY USA

Re: Industrial Engineer

Post by Kaiser_von_Nuben »

[quote=""IndyBrit""][quote=""Kaiser_von_Nuben""]liberal arts brain... mush![/quote]

But you repeat yourself. :-P

Have a feeling some of my vils are going to pay for that one... :D[/quote]

Taunt 157 :-P
"The German Army will not stand for it!"

-Colonel Bockner, King Solomon's Mines (1985)
User avatar
Wetmelon
Honorary Member
Honorary Member
Posts: 190
Joined: Wed Sep 10, 2008 8:49 am
Location: London, ON

Re: Industrial Engineer

Post by Wetmelon »

Think of this problem as a field with a bunch of wells. The "best" solution is the very bottom of the deepest well. The brute force method yells into all the wells to see about how deep they are, and will be unlikely to miss a well (depending on how much brute force you are willing to use), but is not particularly good at putting you into the bottom of that deepest well. Solver (rather, the underlying optimization routine) is really good at running to the nearest well and getting all the way to the bottom. Where there is only one well, or where all the wells are about the same depth, that's perfectly fine.
Good idea, then, combining the brute force for "depth-check" and the Solver for "well-diving" once the appropriate well has been chosen. I understand what it's doing. If I could use the same formula as Solver on my calculator, it would tell me a value for every one of them though :/ (Ti-89 for the win).
Knapsack problems are solved best by linear programming. I just haven't had the time to go through the motions.

This is a good example of an overview of LP:
http://www.math.ucla.edu/~tom/LP.pdf
Yea I'm fairly busy tonight, so I'll have to wade through the programming over the weekend, but I think that's how I'm going to end up doing it.. we'll see.

EDIT: Ok, glanced through the .pdf. The math makes sense and doesn't make sense hehe. I'll dive into it in depth tomorrow. Thanks for the link :)
User avatar
GreenDude
Captain
Captain
Posts: 213
Joined: Sun Aug 10, 2008 6:17 am
Location: Concord, CA
Contact:

Re: Industrial Engineer

Post by GreenDude »

[quote=""Cammel""][quote=""GreenDude""]My brain's PSU has exploded :-P[/quote]
You son of a gun...[/quote]
sry, could resist :D
Image
Image
Post Reply