A Two-Level SOLVER ??

[monir]

Hello;

I would very much appreciate your help in the following relatively simple
non-linear optimization problem.

1) By applying Solver:
.....Set target cell: E18 to max....(E18 represents dependent variable E)
.....By changing cells: J18 ..........(J18 represents independent variable J)
.............................: P18...........(P18 represents independent
variable P)
.....Subject to constraints: B18=1
.....................................: J range 0.05 to 1.40
.....................................: P range 0.50 to 1.50
it produces a feasible solution (J, P, E), which is not exactly the
"correct" one (differs by about 10% of what it should be)

2) The difficulty is directly associated with the above formulation of the
problem.
For any value of the changing variable P, say P1, in the range P=0.50 to
1.50, there is a max E1 at J1.
Solver in 1) above appears to seek the solution for max E based on the
changing combinations of J and P and settles for the combination that
produces max E in comparison with other combinations and subject to the
constraints.
This is clearly not what I had in mind!!

3) The correct formulation of the problem should be, I think, something like:
...Solver1: for each tried value of P, say, P1 in the range 0.50 to 1.50
...Set target cell: E18 to max.....(E18 represents dependent variable E)
...By changing cells: J18 ...........(J18 represents independent variable J)
...Subject to constraints: J range 0.05 to 1.40
..............(solution: J1, max E1 at each P1)
.....Solver2:
.....Set target cell: B18 = 1
.....By changing cells: J18 ..........(J18 now represents the new variable J1)
.....Subject to constraints: J1 range 0.05 to 1.40 (same range of J is fine)
..............(solution: J2, P2, max E2)

4) How would you intelligently combine Solver1 and Solver2 as a 2-level
Solver ?? either by running Solver manually or by a macro. And, is it
possible to do so relying entirely on the Solver internal trial solutions
without establishing the relation between P1s and E1s (which is not easy to
do) ??

Thank you kindly.

 

[SteveM]

Hello;

I would very much appreciate your help in the following relatively simple
non-linear optimization problem.

1) By applying Solver:
....Set target cell: E18 to max....(E18 represents dependent variable E)
....By changing cells: J18 ..........(J18 represents independent variable J)
............................: P18...........(P18 represents independent
variable P)
....Subject to constraints: B18=1
....................................: J range 0.05 to 1.40
....................................: P range 0.50 to 1.50
it produces a feasible solution (J, P, E), which is not exactly the
"correct" one (differs by about 10% of what it should be)

2) The difficulty is directly associated with the above formulation of the
problem.
For any value of the changing variable P, say P1, in the range P=0.50 to
1.50, there is a max E1 at J1.
Solver in 1) above appears to seek the solution for max E based on the
changing combinations of J and P and settles for the combination that
produces max E in comparison with other combinations and subject to the
constraints.
This is clearly not what I had in mind!!

3) The correct formulation of the problem should be, I think, something like:
..Solver1: for each tried value of P, say, P1 in the range 0.50 to 1.50
..Set target cell: E18 to max.....(E18 represents dependent variable E)
..By changing cells: J18 ...........(J18 represents independent variable J)
..Subject to constraints: J range 0.05 to 1.40
.............(solution: J1, max E1 at each P1)
....Solver2:
....Set target cell: B18 = 1
....By changing cells: J18 ..........(J18 now represents the new variable J1)
....Subject to constraints: J1 range 0.05 to 1.40 (same range of J is fine)
.............(solution: J2, P2, max E2)

4) How would you intelligently combine Solver1 and Solver2 as a 2-level
Solver ?? either by running Solver manually or by a macro. And, is it
possible to do so relying entirely on the Solver internal trial solutions
without establishing the relation between P1s and E1s (which is not easy to
do) ??

Thank you kindly.

monir,

Well first of all, what are you trying to maximize? If your 1 is
formulated properly then yes, it is doing what it is supposed to be
doing. So if not E then what?

It's better to describe your problem in equation (not Excel) form
because that is much clearer to another modeler. I.e., it would be
good to know what the functional relationship of P's and J's are to
E. BTW, if P and J are changing cells then they are decision
variables. It's not clear what they are either. Are they single
cells or a vector of cells. What are the non-linear constraint
functions that are functions of them? If you could post that it would
be helpful.

Your 2 implies E is only a function of J unless there is some sort of
plus/minus symmetry between J and P. But then you could make a P a
function of J and replace all the P's in your formulation. But
assuming there is not then P is not in the basis for any value of J.
Otherwise you'd a different Emax. So if P is not in the objective
function and always non basic. I don't see how including it can
contribute to the formulation.

You proposed parametric analysis in 3, reads to me like you'd get the
same Emax values when parameterizing P if I your previous statement
right:

For any value of the changing variable P, say P1, in the range P=0.50 to
1.50, there is a max E1 at J1.

So you lost me. You should not need two Phases to solve your problem,
because that implies that Phase II is a function of the Phase I
decision variables which implies that you can formulate all of the
decision variables in a single Phase because you know what their
functional relationships are. Splitting up the formulation, on its
face will provide no analytical value.

But if you want to optimize in two phases for whatever reason, yes
you'd write a VBA sub that calls solver and it's formulation twice,
saving Phase I outputs as inputs to Phase II. Frontline has a web
page with the VBA solver functions and return codes. You have to have
your maintenance paid up to access it though. The easiest way to
start your formulation is to use the macro recorder when completing
the solver dialog box. That will capture most of the code you need.
You may need to adjust the ranges in the formulation code to point to
both Phase I and Phase inputs/outputs based on what Phase is being
evaluated.

Good Luck,

SteveM

 

[monir]

Steve;

Thank you for your prompt reply.

a) Let me first clarify item 2) of my OP.
The 2nd sentence should read:
"For any value of the changing variable P, say P1, in the range P=0.50 to
1.50, there is a max E1 at J1, which DOES NOT necessarily satisfy the
constraint B18 = 1."

b) Please review my suggestion item 3) of my OP in light of the above
clarification.

c) I'm running Excel Solver from a macro.

d) FYI. Frontline Premium Solver is poorly developed and technically
unreliable! I've extensively tested it earlier on, and reported its numerous
and serious errors to Frontline.

Any thoughts ?? Thank you

 

[SteveM]

Steve;

Thank you for your prompt reply.

a) Let me first clarify item 2) of my OP.
The 2nd sentence should read:
"For any value of the changing variable P, say P1, in the range P=0.50 to
1.50, there is a max E1 at J1, which DOES NOT necessarily satisfy the
constraint B18 = 1."

b) Please review my suggestion item 3) of my OP in light of the above
clarification.

c) I'm running Excel Solver from a macro.

d) FYI. Frontline Premium Solver is poorly developed and technically
unreliable! I've extensively tested it earlier on, and reported its numerous
and serious errors to Frontline.

Any thoughts ?? Thank you

Not really. I still don't know what your problem is because I have
not seen the mathematical representation. You really can't be helped
without the "helper" knowing what that is.

There are some free NLP solvers out there. IPOPT is one. I have not
used it but you can find info here:

http://www.coin-or.org/Ipopt/ipopt-fortran.html

And yes Frontline is a dog. It stinks with MIP problems too. But
it's MIP capabilities are less stinky that it's NLP capabilities.
That being said, if the problem hangs up the NLP solver, you may be
able to formulate it as a piece-wise MIP and use the linear solver.
But again, without knowing what the problem is, I don't know if that
is feasible either.

SteveM

 

[monir]

Steve;

Thank you kindly for your thoughtful reply.

It's very clear that Excel / Solver (also developed by Frontline!) is the
problem!!! No surprise.

1) I've reformulated the optimization problem by deriving the analytical
expression for the 1st derivative d(E)/d(J) as a function of J and P. The
problem now reads:
Given the relations:
...T = fn1(J, P)
...Q = fn2(J, P)
...E = fn3(T, Q, J)
...B = fn4(J, Q)
find the values of:
...J (bet 0.05 and 1.40)
...P (bet 0.50 and 1.50)
such that:
...target: d(E)/d(J) = 0.0
...constraint: B = a known B0
(fn1, fn2, fn4 are complicated, lengthy, 6th deg polys, ~ 1 page long each.
That's why I didn't include them in my OP.)

2) Now the Solver solution (J, P, E) is perfect!!

3) I've never used or even heard of NLP IPOPT (Fortran)!! but will look at
it. Thanks for the link.

4) One of the difficulties would be to convert IPOPT to VBA. It is hard to
know without examining the code. My programming experience is about 60/40
Fortran/VBA. But again, the feasibility of the task would depend on the
complexity of IPOPT.
Based on your expertise in the field, do you know of or used a reliable VBA
optimizer macro ??

Thank you once again for your help.
Monir

 

[Dana DeLouis]

1) I've reformulated the optimization problem by deriving the analytical

expression for the 1st derivative d(E)/d(J) as a function of J and P.

(fn1, fn2, fn4 are complicated, lengthy, 6th deg polys, ~ 1 page long each

Just a thought. Without knowing what you have, solving 6th Deg Polyn. can
be hard, and have multiple solutions.(Derivative =0's)
Solver was probably seeing multiple local Min & Max points on your curve.
As one curve was increasing, probably the other curves were decreasing,
etc... Once Solver gets confused, it easily gives up. Once Solver locks
onto an incorrect local minimum, Solver doesn't have enought logic to get
out of it, and give proper warnings.
Make sure you model was not using functions like IF(), as these cause
problems for Solver.

Mentioning 6th Deg Polys with Solver should send a red flag! It may be
possible to write a vba routine using the Newton Method. That can sometimes
help.
You may have a valid solution, but my experience would suggest caution with
the answer given.

 

[monir]

Dana;

Thank you for taking the time.

1) Your thoughts are valid. Yes, a combination of a 6th deg poly and Solver
is generally a problem! However, as I indicated in my OP, for any value of
the changing variable P, say P1, E has a single extremum (max) within the
range of interest of J and P.
Thus, Solver should not really get confused by seeing multiple min and max!
There's only one local max point.

2) It seems to me that Excel / Solver performs better when the target is set
to a value rather than to a max or min! And that's precisely why I had to
reformulate the problem such that d(E)/d(J) is set to zero instead of
(originally) setting E to max. It works!

3) It's evident from your reply that you're familiar with the subject
matter, and possibly have tried other optimizers. If so, would you be kind
enough to share some of your experience and thoughts on such other optimizers
regarding: reliability, limitations, options, availability of VBA code, etc.

Thank you.
Monir

 

[Dana DeLouis]

Hi. I'd be very interested if you could send me your workbook.
I'd be glad to take a look at it. I'm curious about your polynomial
equation.
Thanks. :>)

 

[Mike Middleton]

monir -

Yes, a combination of a 6th deg poly and Solver is generally a problem! <

Please educate me. When is a 6th degree polynomial appropriate?

I can understand using a 2nd degree polynomial to model a single-bulge
relationship, and occasionally there may be an S-shaped relationship that
needs a 3rd degree polynomial.

But what kind of real-world situation needs a model with a 6th degree
polynomial?

(In most data analysis applications, I would be very concerned with
over-fitting and the numerical precision difficulties associated with
raising values to the 6th power.)

I really am curious.

- Mike Middleton
http://www.DecisionToolworks.com
Decision Analysis Add-ins for Excel

 

[SteveM]

monir -


Please educate me. When is a 6th degree polynomial appropriate?

I can understand using a 2nd degree polynomial to model a single-bulge
relationship, and occasionally there may be an S-shaped relationship that
needs a 3rd degree polynomial.

But what kind of real-world situation needs a model with a 6th degree
polynomial?

(In most data analysis applications, I would be very concerned with
over-fitting and the numerical precision difficulties associated with
raising values to the 6th power.)

I really am curious.

- Mike Middletonhttp://www.DecisionToolworks.com
Decision Analysis Add-ins for Excel










...

read more >>

I gotta step in here. Regardless of what the function is (excepting
that it's smooth and continuous in the feasible region, the max/min
value of the objective function may be meaningless by itself. I.e.
setting first derivatives to 0. Because the feasible region is
defined by the bounded poly-tope comprised of both the objective
function and the constraint set.

Say you have a simple parabola, y = x2 that you want to minimize.
Setting the first derivative = 0, gives an inflection point. Simple
enough. But now add the constraint y >= 3 which is represented by a
line that passes right through the parabola. So now the feasible
region has been reduced taking the 0 point of the objective function
out of play. So the derivative by itself provides you with no value.

The convexity of higher order systems of non-linear inequalities is
generally impossible to establish by inspection. It can be determined
by examining if the Hessian of the Lagrangian equation meets KKT
conditions. I.e. is positive/negative definite. I'm not an NLP guy
per se. (But was taught by the best, Fiacco and McCormick who
formulated the SUMT technique which is the basis for barrier solvers),
but KKT evaluation requires that the Lagrangian be twice
differentiable. But sometimes it's not, e.g. the case above, but
there are ways around that. I don't know how complex the solvers are
these days because I'm mostly a MIP guy, but part of their power is
being able to look at the formulation and deduce what kind of animal
it's dealing with. It all gets kind of complicated.

One other thing, Newton's Method can be used as search strategy for
NLP, but it's generally not used because it is a "steepest descent"
algorithm I think. That's a greedy method that often has the solver
stuck iterating around a flat spot of the poly-tope if the wrong
feasible starting point was selected and the iteration step size is
not properly scaled. There are superior quasi-Newton methods as well
as others. Much of the time, the efficiency of an optimization is
based on search parameters set by the modeler. The more sophisticated
the solver package that more switches can be set. I know for MIP
problems though, there are tons of search parameter combinations and
often the right combination is discovered serendipitously. BTW, a
solution time can sometimes be knocked back from hours to seconds if
you get it right.

OK, so back to the original poster's original question. I still don't
know what his/her functional form is, so really have know idea what's
what with his/her problem. But related to NLP and solvers, you all
can check these references if you wish:

http://www-new.mcs.anl.gov/otc/Guide/

is a wonderful site with a link to a list of solvers.

Another great site is run my Hans Mittelmann at Arizona State:

http://plato.asu.edu/sub/websub.html

Note that LINGO and What's Best directly interface with Excel. What's
Best models are formulated like Frontline. LINGO is an algebraic
modeling language. Both are put out by LINDO Systems so you can be
sure that the NLP solvers are not very robust. But you can probably
download a trial version of What's Best and see if it works. (I'm
sure LINGO uses the same NLP engine.)

I use a model management system called MPL, www.maximal-usa.com and
the XA LP/MIP solver which is very good for medium to large problems
and is priced right. The developer, Sunset Technologies, www.sunsetsoft.com
also has NLP modules. Their shop is small but they know what they are
doing. And again if their stuff at their prices can solve your
problem, then why not?

MPL also has a component library called Optimax that allows you to
embed your model directly in Excel using VBA. I use MPL and Optimax
in tandem and it works out very well. MPL also has trial downloads of
the product itself, plus a reduced version of CPLEX, which is one of
the most powerful (and expensive) optimizers out there. If your
problem is small enough and non-recurrent, the trial download may work
for you. (Although the CPLEX parameter set is huge. But MPL allows
you set them via it's intuitive interface.)

If you want additional help, you can visit the Google OR newsgroup,
sci.op-research. Dr. Paul Rubin from Michigan State is an
optimization guy who is always lurking around looking to help.
Including "Dr. Rubin, Help!?" in your subject line is like putting a
worm in front of a fish.

Oh, if you actually need to purchase product and contact those guys,
Jim at Sunset and Bjarni at Maximal, tell them I sent you J.

OK, I'm tapped out.

SteveM

 

[monir]

$$ Dana;
1) >"Hi. I'd be very interested if you could send me your workbook."
I would be glad to do so. The difficulty, however, is multi-folds!! The
w/b is ~ 13. MB and trying to delete irrelevant stuff would likely disrupt
the data flow and renders the w/b unworkable!!
2) I may be able to send a truncated copy directly to you, if you don't mind!


$$ Mike;
3) >"Please educate me. When is a 6th degree polynomial appropriate?"
Polynomials are the most easy to use and the most difficult to predict!
In some cases, the deg of poly is a by-product of the analytical method,
while in other cases it is pre-selected depending on the application.
4) In my current application, I selected/ended up with a 6th degree
polynomials, and here's how.
I had numerous 5-parameter analytical data sets, and I needed an accurate
regression model to represent the data analytically for post processing.
5) I've successfully developed a Genetic Algorithm (GA) based on a reliable
Evolutionary Strategy (ES) technique and incorporating a non-linear
multi-variant regression model.
I've the option of specifying the variable's highest exponent in each
polynomial term. Based on my experience on handling similar regression
problems, I chose 6; the max integer exponent allowed in my current version
of the algorithm.
6) So if the regression equation is given by:
....E = fn(X, Y, Z, W, V)
and
....E = SUM(n=1, N) An.(X)^an .(Y)^bn. (Z)^cn. (W)^dn. (V)^en
then one can determine the exponents and the set of regression coefficients
such that the best-fit to the data is realized, i.e.; the Squared Error Sum
(SES) is less than a specified accuracy, say, < 1.E-6, which is a reasonable
engineering accuracy for my current application.


$$ Steve;
7) >"Say you have a simple parabola, y = x2 that you want to minimize.
Setting the first derivative = 0, gives an inflection point."
As you know, a zero 2nd derivative alone DOES NOT necessarily identify an
inflection point! The 1st derivative must pass smoothly through a "true"
inflection point. Another situation, if the change-of-sign of the 2nd
derivative is accompanied by a change-of-sign of the 1st derivative, then the
point is NOT an inflection point!
8) >"So the derivative by itself provides you with no value."
I respectfully disagree! One can learn a lot by
examining/studying/observing the behaviour of derivatives of complex
functions!!
9) Back to my OP and my subsequent reformulation of the optimization problem
by setting d(E)/d(J) = 0 instead of E = max.
I've tested the reformulated optimization 100s of times with different sets
of data and with different starting values. The results, so far, are
consistent and correct for every and each case tested.
10) I'll access the links to NLP and Arizona State (and others you kindly
provided) to see if I can realistically find a reasonable replacement to
Excel/Solver without major changes to my program.
I'll seriously consider any non-Frontline VBA Solver algorithm.

Thank you, Dana, Steve and Mike for your thoughtful contributions.
Monir