Trouble finding solutions using GAMS and PathNLP

[Archiver]

Hi

I have a quadratic obj linear constraint NLP we are solving using
PATHNLP.

I have 3 questions here (bear with me ). The first two are strange
outcomes I don't really understand, and the 3rd is a more generalised
advice question on techniques for getting our problem to solve (as I
have never tried solving NLPs or used PATH before).

We solve each year individually in a big loop, ie something like
loop (y) do

solve my_model using NLP maximising z;

endloop

Question 1:
----------------
For year 2007 the model solved. I worked out that some constraints
are not required in all cases, and so eliminated this constraint for
some items (ie the problem is now less constrained). However where
the model used to solve with the full constraint set, it now reports
back as infeasible.(?!) Solving the full constraint set takes a few
mins, solving the optimised constraint set concludes it is infeasible
much quicker.

I have posted the output from the full and restricted constraint set
below in case it helps.

Can someone suggest why this is? Is it hitting some limit somewhere
perhaps which it reaches in the less constrained version but doesnt
hit in the fully constrained version?


#### FULL CONSTRAINT SET ####

L O O P S scen Scen1
y 2007
s FullYr

S O L V E S U M M A R Y

MODEL TCONE OBJECTIVE Z
TYPE NLP DIRECTION MAXIMIZE
SOLVER PATHNLP FROM LINE 2206

**** SOLVER STATUS 1 NORMAL COMPLETION
**** MODEL STATUS 2 LOCALLY OPTIMAL
**** OBJECTIVE VALUE 11034141.0678

RESOURCE USAGE, LIMIT 80.314 100000000.000
ITERATION COUNT, LIMIT 34433 10000000
EVALUATION ERRORS 0 0

PATH-NLP Nov 27, 2006 WIN.PT.PT 22.3 016.035.041.VIS Path 4.6.07

NLP size: 16195 rows, 20241 cols, 60155 non-zeros, 0.02% dense.
MCP size: 36434 rows/cols, 100028 non-zeros, 0.01% dense.



**** REPORT SUMMARY : 0 NONOPT
0 INFEASIBLE
0 UNBOUNDED
0 ERRORS

### OPTIMISED (ie fewer) CONSTRAINTS ###

S O L V E S U M M A R Y

MODEL TCONE OBJECTIVE Z
TYPE NLP DIRECTION MAXIMIZE
SOLVER PATHNLP FROM LINE 2207

**** SOLVER STATUS 2 ITERATION INTERRUPT
**** MODEL STATUS 6 INTERMEDIATE INFEASIBLE
**** OBJECTIVE VALUE 11033991.5615

RESOURCE USAGE, LIMIT 32.141 100000000.000
ITERATION COUNT, LIMIT 13367 10000000
EVALUATION ERRORS 0 0

PATH-NLP Nov 27, 2006 WIN.PT.PT 22.3 016.035.041.VIS Path 4.6.07

NLP size: 16181 rows, 20241 cols, 59595 non-zeros, 0.02% dense.
MCP size: 36420 rows/cols, 98908 non-zeros, 0.01% dense.



**** REPORT SUMMARY : 123 NONOPT ( NOPT)
4 INFEASIBLE (INFES)
SUM 8.4338869E-5
MAX 3.4079636E-5
MEAN 2.1084717E-5
0 UNBOUNDED
0 ERRORS


Question 2:
-------------------
For some solve years we are not getting a feasible solution back, even
though I would imagine that one exists - and I have explicit slack
variables (at a very high cost) added to the constraints I thought
might cause trouble to try and reduce this issue.

Strangely however if I solve *just that year on its own*, i get a
feasible solution.

ie if for example year 2009 does not solve during the full loop, and I
change my loop to be as follows I get a feasible solution for 2009.

loop (y)$(SameAs(y,"2009")) do

endloop;

Its possible we are hitting some limit, or do not have well tweaked
PATHNLP settings and so PATH is struggling for some reason.
Perhaps we have some previous solution's residue floating around which
PATHNLP is picking up and its causing it issues? However I didnt see
a PATH option to turn this off..?

To add to the confusion, I can get a solution for 2009 if I have:
loop (y)$(SameAs(y,"2009")) do [ie solve 2009 only]
or
loop (y)$(SameAs(y,"2008") OR SameAs(y,"2009")) do [ie solve 2008
and 2009]

but not if I have
loop (y)$(SameAs(y,"2007") OR SameAs(y,"2008") OR SameAs(y,"2009"))
do [ie solve 2007 and 2008 and 2009]
or
loop (y)$(SameAs(y,"2007") OR SameAs(y,"2009")) do [ie solve 2007 and
2009]

I have looked hard at the constraints via the .lst file and cannot see
any differences between the 2009 constraint listing for one which
works and one which doesn't - so I don't believe I am screwing up some
data value within the model during the data processing stage within
the loop.


Question 3:
-------------------
Can someone advise as to a good set of PATHNLP or GAMS settings to try
first when trying to get PATHNLP to solve, and or what limits I should
be looking at. I am new to NLPs and PATH. Basically - are there any
good settings which increase the changes of PATHNLP solving even it it
slows things down, and we can wind them back as we get comfortable
that the model is finding solutions and the solutions are sensible.

Thanks in advance
Andy C
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to gamsworld@googlegroups.com
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en
-~----------~----~----~----~------~----~------~--~---

[Archiver]

Andrew,

Please find my responses below.

On Tue, Jan 13, 2009 at 7:42 PM, AC wrote:
> >
> > Hi
> >
> > I have a quadratic obj linear constraint NLP we are solving using
> > PATHNLP.
> >
> > I have 3 questions here (bear with me ). The first two are strange
> > outcomes I don't really understand, and the 3rd is a more generalised
> > advice question on techniques for getting our problem to solve (as I
> > have never tried solving NLPs or used PATH before).
> >
> > We solve each year individually in a big loop, ie something like
> > loop (y) do
> >
> > solve my_model using NLP maximising z;
> >
> > endloop
> >
> > Question 1:
> > ----------------
> > For year 2007 the model solved. I worked out that some constraints
> > are not required in all cases, and so eliminated this constraint for
> > some items (ie the problem is now less constrained). However where
> > the model used to solve with the full constraint set, it now reports
> > back as infeasible.(?!) Solving the full constraint set takes a few
> > mins, solving the optimised constraint set concludes it is infeasible
> > much quicker.
> >
> > I have posted the output from the full and restricted constraint set
> > below in case it helps.
> >
> > Can someone suggest why this is? Is it hitting some limit somewhere
> > perhaps which it reaches in the less constrained version but doesnt
> > hit in the fully constrained version?
> >
> >
> > #### FULL CONSTRAINT SET ####
> >
> > L O O P S scen Scen1
> > y 2007
> > s FullYr
> >
> > S O L V E S U M M A R Y
> >
> > MODEL TCONE OBJECTIVE Z
> > TYPE NLP DIRECTION MAXIMIZE
> > SOLVER PATHNLP FROM LINE 2206
> >
> > **** SOLVER STATUS 1 NORMAL COMPLETION
> > **** MODEL STATUS 2 LOCALLY OPTIMAL
> > **** OBJECTIVE VALUE 11034141.0678
> >
> > RESOURCE USAGE, LIMIT 80.314 100000000.000
> > ITERATION COUNT, LIMIT 34433 10000000
> > EVALUATION ERRORS 0 0
> >
> > PATH-NLP Nov 27, 2006 WIN.PT.PT 22.3 016.035.041.VIS Path 4.6.07
> >
> > NLP size: 16195 rows, 20241 cols, 60155 non-zeros, 0.02% dense.
> > MCP size: 36434 rows/cols, 100028 non-zeros, 0.01% dense.
> >
> >
> >
> > **** REPORT SUMMARY : 0 NONOPT
> > 0 INFEASIBLE
> > 0 UNBOUNDED
> > 0 ERRORS
> >
> > ### OPTIMISED (ie fewer) CONSTRAINTS ###
> >
> > S O L V E S U M M A R Y
> >
> > MODEL TCONE OBJECTIVE Z
> > TYPE NLP DIRECTION MAXIMIZE
> > SOLVER PATHNLP FROM LINE 2207
> >
> > **** SOLVER STATUS 2 ITERATION INTERRUPT
> > **** MODEL STATUS 6 INTERMEDIATE INFEASIBLE
> > **** OBJECTIVE VALUE 11033991.5615
> >
> > RESOURCE USAGE, LIMIT 32.141 100000000.000
> > ITERATION COUNT, LIMIT 13367 10000000
> > EVALUATION ERRORS 0 0
> >
> > PATH-NLP Nov 27, 2006 WIN.PT.PT 22.3 016.035.041.VIS Path 4.6.07
> >
> > NLP size: 16181 rows, 20241 cols, 59595 non-zeros, 0.02% dense.
> > MCP size: 36420 rows/cols, 98908 non-zeros, 0.01% dense.
> >
> >
> >
> > **** REPORT SUMMARY : 123 NONOPT ( NOPT)
> > 4 INFEASIBLE (INFES)
> > SUM 8.4338869E-5
> > MAX 3.4079636E-5
> > MEAN 2.1084717E-5
> > 0 UNBOUNDED
> > 0 ERRORS
> >
> >

The 2nd run (with the "optimized" model) is not reporting back as
infeasible. The solver status is telling you that PATHNLP quit before
it found a solution, and the model status indicates the solution is an
intermediate value (i.e. whatever the solver had on had when it quit)
that is not feasible. If you look more closely at the parts of the
PATH log that you didn't send you will likely find clues as to why
PATH quit and what you could do to make it keep going. But before you
look at the log you might consider putting back in the constraints you
removed. I doubt a few extra constraints will do any harm, and they
seem to help in this case.


> > Question 2:
> > -------------------
> > For some solve years we are not getting a feasible solution back, even
> > though I would imagine that one exists - and I have explicit slack
> > variables (at a very high cost) added to the constraints I thought
> > might cause trouble to try and reduce this issue.
> >
> > Strangely however if I solve *just that year on its own*, i get a
> > feasible solution.
> >
> > ie if for example year 2009 does not solve during the full loop, and I
> > change my loop to be as follows I get a feasible solution for 2009.
> >
> > loop (y)$(SameAs(y,"2009")) do
> >
> > endloop;
> >
> > Its possible we are hitting some limit, or do not have well tweaked
> > PATHNLP settings and so PATH is struggling for some reason.
> > Perhaps we have some previous solution's residue floating around which
> > PATHNLP is picking up and its causing it issues? However I didnt see
> > a PATH option to turn this off..?
> >
> > To add to the confusion, I can get a solution for 2009 if I have:
> > loop (y)$(SameAs(y,"2009")) do [ie solve 2009 only]
> > or
> > loop (y)$(SameAs(y,"2008") OR SameAs(y,"2009")) do [ie solve 2008
> > and 2009]
> >
> > but not if I have
> > loop (y)$(SameAs(y,"2007") OR SameAs(y,"2008") OR SameAs(y,"2009"))
> > do [ie solve 2007 and 2008 and 2009]
> > or
> > loop (y)$(SameAs(y,"2007") OR SameAs(y,"2009")) do [ie solve 2007 and
> > 2009]
> >
> > I have looked hard at the constraints via the .lst file and cannot see
> > any differences between the 2009 constraint listing for one which
> > works and one which doesn't - so I don't believe I am screwing up some
> > data value within the model during the data processing stage within
> > the loop.


In addition to the model itself, GAMS always provides the solver with
an initial point. This is important and often crucial information for
a nonlinear model. Lots has been written about this over the years -
I suggest looking first at the CONOPT solver manual
http://www.gams.com/dd/docs/solvers/conopt.pdf, then searching the
GAMS-L archives http://www.gams.com/maillist/gams_l.htm for more on
this topic.

Most likely, the two runs are getting different initial points: this
can change the outcome. I would verify this by doing the 2009 solves
with the CONVERT solver instead of PATHNLP. CONVERT will not solve
the model but will dump out a scalar version in the file gams.gms.
You can compare the two files to see if the model and/or initial point
are the same for the two solves, and if not, what the differences are.


> >
> >
> > Question 3:
> > -------------------
> > Can someone advise as to a good set of PATHNLP or GAMS settings to try
> > first when trying to get PATHNLP to solve, and or what limits I should
> > be looking at. I am new to NLPs and PATH. Basically - are there any
> > good settings which increase the changes of PATHNLP solving even it it
> > slows things down, and we can wind them back as we get comfortable
> > that the model is finding solutions and the solutions are sensible.
> >

If I was having problems getting a feasible point I would try another
GAMS NLP solver instead of PATHNLP. For example, CONOPT has good
diagnostics in case of unbounded or poorly scaled models that help you
improve the formulation, and MINOS is particularly well suited to
models that have linear constraints. COINIPOPT is free and highly
regarded, in case you've not got a license for any of the others. You
should be aware that PATHNLP is a very simplistic implementation of an
SQP method for solving NLP: it will be as robust as the other NLP
solvers in general but it was created since the method is very, very
fast in several cases of particular interest (e.g. maximum entropy and
min-cross-entropy models).

Another idea is to first solve a linear version of the model to get a
feasible initial point, but I would first try the other NLP solvers.

-- Steven Dirkse, Ph.D. GAMS Development Corp., Washington DC Voice: (202)342-0180 Fax: (202)342-0181 sdirkse@gams.com http://www.gams.com