[Couenne] Input for COUENNE

[Pietro Belotti]

Tim,

> 1. Translating gms to nl files
> 
> In fact, I have access to neither GAMS nor AMPL currently.  I wrote a 
> .gms file generator to provide input to SparsePOP (using the SparsePOP 
> manual and GAMS tutorial), then found I could also use it to submit 
> optimization problems to BARON.  From the example .mod file you 
> provided, it seems that my generator could easily be modified to spit 
> out something in that format, so I guess I need to then look at access 
> to AMPL as a .nl converter?

Yes. An AMPL model file can be instructed to run Couenne without 
translating the model to a .nl file through the instruction

option solver couenne;

> 2. COUENNE and the 14-tree "toy" problem
> 
> The ex14.gms file I provided currently results identical (correct) 
> solutions when submitted to either BARON or SparsePOP.  The correct 
> solution is easy to find manually, but both solvers agree.  Not so with 
> COUENNE, warning (in the ex14.txt file) "no objective function found" 
> and stating "Integer solution of 0 found by Couenne Rounding NLP after 0 
> iterations".  I'm not sure about the significance of these messages, but 
> I note that the values offered by COUENNE for x1 through x14 are NOT 
> correct.  In the correct solution, x9, x11 and x12 should all equal 1, 
> and all others equal -1 (easily reproduced by submitting my ex14.gms to 
> BARON).  I'm not sure what is going on with COUENNE and why it does not 
> seem to solve correctly.  Obviously, I need to understand how to fix 
> this, if we are to continue with larger-scale problems.

I forgot that GAMS uses a variable for the objective function. The correct 
version gives me an objective function value of -3.934 and a solution very 
close to the one you mention (x9=.974679 and x13=-.974679 the only 
differences). I'll send you model files and result in a separate email.

> 3. What is a "reasonably good solution"
> 
> We have both operational and research applications for this model.  
> Operationally, time is not a huge factor, and we can afford to let the 
> solver run for long periods (hours, days), if that will achieve 
> something closer to a "true optimum" for a real situation.  For research 
> purposes, we are generally interested in incorporating the solver into 
> Monte Carlo simulations where execution times beome rather important.  
> In this case, finding the true optimum is not so important, provided 
> that the solution is a "good" one.  What is "reasonably good"?  Here 
> were are looking for a solution with exactly N variables equal to 1, and 
> the rest equal to -1. 

This can be enforced at the model level through a constraint on binary 
variables. After a more careful look at your model, it seems that you need 
to enforce integrality on the variables. What you do with the constraint

x1*x1 >= .95

seems to be that you need x1 to be either -1 and 1. This is a valid 
constraint, but a more direct way to say "x1 is either -1 or 1" is to 
declare another variable:

var y1 binary;

and then enforce the constraint

x1 = -1 + 2 * y1;

which simply encodes the two desired values of x1 in y1: if y1=0, then 
x1=-1; if y1=1, then x1=1. This will yield a solution where all x 
variables are either -1 or 1, and no x variable will be .97 as Couenne 
finds out.

> Anything short of this would require some sort of improvement through 
> heuristics or some other strategy.  I think this needs experience with 
> some of the approaches you’ve suggested to determine the best.

A good modeling sometimes makes the difference between solution times of 
days and minutes. I think the model can be further enhanced by getting rid 
of nonlinear expressions altogether.

> 4.  Problem size
> 
> Both SparsePOP and BARON easily solved our ex14.gms “toy” problem, 
> suggesting that our formulation works as intended and that our .gms file 
> is correct.  Both crash when asked to solve “real-scale” problems.  The 
> number of variables for these problems would generally be less than 500 
> (we can truncate our selection list by some "smart" preconditioning).  
> However, the number of terms in equation e2 will always be greater, 
> sometimes much greater (say, up to 10x).  Not really any way around 
> this, as this is defined by the nature of the pedigree -- the more 
> relatives, the greater the number of terms.  I understand that equation 
> e2 is a challenge for any solver but it is also the heart of the 
> solution.

This is the main reason why I suggest getting rid of nonlinear 
expressions. This requires a knowledge of modeling in integer linear 
optimization (ILP), but even non-commercial software for ILP can solve 
very large problems in a much shorter time.

> 5.  Alternative solvers
> 
> From what you tell me, it sounds like Bonmin warrants some investigation 
> to see if it will provide our power and flexibility needs.  Sounds also 
> like I still have to master the business of generating .nl files if I'm 
> to use it.
> 
> 6.  Next steps
> 
> After reading your suggestions, it seems to me that my next steps, 
> roughly in order of priority, are:
> 
> ·         Understand what went wrong with COUENNE's execution of Ex14.nl 
> and how to fix it

See forthcoming email.

> ·         Learn to access AMPL and generate .nl files with it from .gms 
> or .mod files  (I think I can easily modify my .gms file generator to 
> produce .mod files instead)
> 
> ·         Explore behaviour and control of alternative solvers, such as 
> Windows COUENNE and Bonmin
> 
>  
> 
> Thank you again for your help with this.  Indeed, our application is far 
> outside the usual realm of operations research and some of my questions 
> will reflect my total lack of experience in the field.  The learning 
> curve is very steep.  We feel that we’ve come a long way in describing 
> our problem(s) in terms of mathematical programming models – it would be 
> really good if we could find solvers that can be applied to these models 
> in practice.  This will be of huge benefit, not just for tree breeders, 
> but for ALL types of breeding activities, regardless of organism.

This is indeed an interesting application.

Regards,
Pietro

--
Pietro Belotti
Dept. of Mathematical Sciences
Clemson University
email: pbelott at clemson.edu
phone: 864-656-6765
web:   http://myweb.clemson.edu/~pbelott

On Wed, 7 Mar 2012, Tim Mullin wrote:

> 
> Pietro:
> 
>  
> 
> Thank you for your very prompt and detailed response to my questions on 
> the care and feeding of COUENNE.  You've covered a lot of ground in your 
> response, so I'll try to condense my supplementary questions under 
> discrete headings:
> 
>  
> 
> 1. Translating gms to nl files
> 
> In fact, I have access to neither GAMS nor AMPL currently.  I wrote a 
> .gms file generator to provide input to SparsePOP (using the SparsePOP 
> manual and GAMS tutorial), then found I could also use it to submit 
> optimization problems to BARON.  From the example .mod file you 
> provided, it seems that my generator could easily be modified to spit 
> out something in that format, so I guess I need to then look at access 
> to AMPL as a .nl converter?
> 
>  
> 
> 2. COUENNE and the 14-tree "toy" problem
> 
> The ex14.gms file I provided currently results identical (correct) 
> solutions when submitted to either BARON or SparsePOP.  The correct 
> solution is easy to find manually, but both solvers agree.  Not so with 
> COUENNE, warning (in the ex14.txt file) "no objective function found" 
> and stating "Integer solution of 0 found by Couenne Rounding NLP after 0 
> iterations".  I'm not sure about the significance of these messages, but 
> I note that the values offered by COUENNE for x1 through x14 are NOT 
> correct.  In the correct solution, x9, x11 and x12 should all equal 1, 
> and all others equal -1 (easily reproduced by submitting my ex14.gms to 
> BARON).  I'm not sure what is going on with COUENNE and why it does not 
> seem to solve correctly.  Obviously, I need to understand how to fix 
> this, if we are to continue with larger-scale problems.
> 
>  
> 
> 3. What is a "reasonably good solution"
> 
> We have both operational and research applications for this model.  
> Operationally, time is not a huge factor, and we can afford to let the 
> solver run for long periods (hours, days), if that will achieve 
> something closer to a "true optimum" for a real situation.  For research 
> purposes, we are generally interested in incorporating the solver into 
> Monte Carlo simulations where execution times beome rather important.  
> In this case, finding the true optimum is not so important, provided 
> that the solution is a "good" one.  What is "reasonably good"?  Here 
> were are looking for a solution with exactly N variables equal to 1, and 
> the rest equal to -1.  Anything short of this would require some sort of 
> improvement through heuristics or some other strategy.  I think this 
> needs experience with some of the approaches you’ve suggested to 
> determine the best.
> 
>  
> 
> 4.  Problem size
> 
> Both SparsePOP and BARON easily solved our ex14.gms “toy” problem, 
> suggesting that our formulation works as intended and that our .gms file 
> is correct.  Both crash when asked to solve “real-scale” problems.  The 
> number of variables for these problems would generally be less than 500 
> (we can truncate our selection list by some "smart" preconditioning).  
> However, the number of terms in equation e2 will always be greater, 
> sometimes much greater (say, up to 10x).  Not really any way around 
> this, as this is defined by the nature of the pedigree -- the more 
> relatives, the greater the number of terms.  I understand that equation 
> e2 is a challenge for any solver but it is also the heart of the 
> solution.
> 
>  
> 
> 5.  Alternative solvers
> 
> From what you tell me, it sounds like Bonmin warrants some investigation 
> to see if it will provide our power and flexibility needs.  Sounds also 
> like I still have to master the business of generating .nl files if I'm 
> to use it.
> 
>  
> 
> 6.  Next steps
> 
> After reading your suggestions, it seems to me that my next steps, 
> roughly in order of priority, are:
> 
> ·         Understand what went wrong with COUENNE's execution of Ex14.nl 
> and how to fix it
> 
> ·         Learn to access AMPL and generate .nl files with it from .gms 
> or .mod files  (I think I can easily modify my .gms file generator to 
> produce .mod files instead)
> 
> ·         Explore behaviour and control of alternative solvers, such as 
> Windows COUENNE and Bonmin
> 
>  
> 
> Thank you again for your help with this.  Indeed, our application is far 
> outside the usual realm of operations research and some of my questions 
> will reflect my total lack of experience in the field.  The learning 
> curve is very steep.  We feel that we’ve come a long way in describing 
> our problem(s) in terms of mathematical programming models – it would be 
> really good if we could find solvers that can be applied to these models 
> in practice.  This will be of huge benefit, not just for tree breeders, 
> but for ALL types of breeding activities, regardless of organism.
> 
>  
> 
> Very best regards,
> 
>  
> 
> Tim
> 
>  
> 
> -----Original Message-----
> From: Pietro Belotti [mailto:pbelott at clemson.edu]
> Sent: Tuesday, 6 March 2012 5:38 p.m.
> To: Tim Mullin
> Subject: Re: Input for COUENNE
> 
>  
> 
> Dear Dr. Mullin,
> 
>  
> 
> > At this point, we have succeed in developing the NLP formulation of 
> > the optimisation problem, and have managed to solve small, toy 
> > problems with a couple of solvers, SparsePOP and BARON.  Both of these 
> > accept a .gms file as input.
> 
>  
> 
> First, I'm afraid I have to break some bad news: in general, Couenne is 
> not much better than Baron. Problems with more than 2000 variables and 
> 2000 constraints (although it very much depends on the type of 
> constraints) are usually quite hard to solve.
> 
>  
> 
> There are a few ways to overcome this: first, if you are happy with a 
> (relatively good) feasible solution rather than a truly optimal one, set 
> a time limit by adding, for instance, the line
> 
>  
> 
> time_limit 1234
> 
>  
> 
> to a file named couenne.opt, which has to reside in the same directory 
> where you run the executable. The number following "time_limit" is the 
> number of seconds after which execution stops. It might happen that by 
> then Couenne has found a feasible solution, which, however, might not be 
> an optimal solution.
> 
>  
> 
> Second, use the "feasibility pump", a more thorough (but more time 
> consuming) heuristic introduced with the more recent stable/0.4 version 
> of Couenne. To enable this, add the following line to the file 
> couenne.opt:
> 
>  
> 
> feas_pump_heuristic yes
> 
>  
> 
> Depending on the size of the problem, this could actually take more time 
> and hence might be counterproductive. Again, this does not guarantee to 
> find the global optimum, but only a (relatively good) upper bound on the 
> global optimum. Couenne guarantees global optimality only upon 
> termination (i.e., without time limits).
> 
>  
> 
> Third (yet another heuristic method): use a method that guarantees to 
> solve to global optimality the subclass of convex MINLPs, i.e., MINLPs 
> whose continuous relaxation is a convex optimization problem (a class of 
> much easier problems). Bonmin is one such method, and has a very similar 
> interface as Couenne (i.e., it reads .nl files and is accessible from 
> GAMS).
> 
>  
> 
> > Our requirement is to find a Windows-based standalone solver that has 
> > the horsepower to solve real-life selection problems, and the ability 
> > to be called from the command line by other tools (such as Monte Carlo 
> > simulators).  BARON, of course, is an online solver, and runs out of 
> > resources before producing good solutions for real-scale problems. 
> > SparsePOP can conveniently be called from other programs in a Windows 
> > environment, but crashes when we attempt larger problems.
> 
>  
> 
> Couenne could be a solution to that, as binaries are available for Windows at
> 
>  
> 
> http://www.coin-or.org/download/binary/Couenne
> 
>  
> 
> although only up to release 0.3.2 (release 0.4.2 is available as open 
> source code). Also, there is a version of GAMS that contains Couenne 
> (though I believe this integration is still in a preliminary phase), 
> hence you might be able to use Couenne with the version of GAMS you have 
> (I assume you do since you sent me a .gms file).
> 
>  
> 
> > I wanted to try COUENNE as an alternative solver, but realise that it 
> > expects input as an .nl file.  I have tried to follow David Gay’s 
> > paper on “Writing .nl files”, but confess I get hopelessly lost by 
> > page 4.  I should stress that, while I am a quantitative forest 
> > geneticist and tree breeder, I am NOT a mathematician and certainly 
> > not an OR expert.  I’m feeling well out of my depth.  Getting this far 
> > with our project and producing working gms input files has already 
> > been a huge effort, but I definitely need help if I’m to translate our 
> > problem to an .nl file.
> 
> 
> > Is there such a thing as a conversion tool that can translate our gms 
> > files to .nl?
> 
>  
> 
> Yes. Details below.
> 
>  
> 
> > I’ve found mention of a tool called COCONUT on Google searches, but 
> > the links are dead.
> 
>  
> 
> I managed to use COCONUT some time ago, but I do not have the code with 
> me.
> 
>  
> 
> > If there is no such thing as a converter, is there perhaps other 
> > instructional material that would help me through the maze of 
> > generating .nl files “from scratch”?
> 
>  
> 
> Actually, .nl files are an intermediate format that can be read by most 
> solvers, but are hardly understandable (and writable) by humans. These 
> files are created by AMPL, which reads a .mod file (and possibly a .dat 
> file with data, e.g. parameter values) and produces a .nl file stored 
> either in a temporary disk directory or in the RAM. Then, the .nl file 
> is sent to the solver, which solves the problem and saves a .sol file 
> with data about the solution, which is read again by AMPL, which in turn 
> can display the variables' values.
> 
>  
> 
> If you have GAMS, there is an option to set the "solver" to a converter 
> (I believe the minlp.opt file has to contain the word "convert", but I 
> am not a GAMS expert) which writes a file ampl.mod, which is in AMPL 
> format. The ampl.mod file can then be read by AMPL and transformed (via 
> the command "write gfilename;") to a .nl file.
> 
>  
> 
> I have attached a file in AMPL format (ex14.mod) that is equivalent to 
> the .gms file you have sent me. The last three lines, respectively:
> 
>  
> 
> 1) set Couenne as the solver;
> 
> 2) start optimization;
> 
> 3) save a file ex14.nl (note the "g" prefix given to the file name). I 
> have attached the resulting .nl file to this email as well.
> 
>  
> 
> With the example you sent me, Couenne gives the output as in the file 
> ex14.txt attached.
> 
>  
> 
> > All this, of course, so that we can test if COUENNE will really 
> > provide an adequate solver for our selection problems.  As an 
> > illustration, I’m attaching a gms file that optimises selection of 3 
> > individuals from a pedigree of 14.  It is a “toy” example that is 
> > easily solved by hand, but all of our real-life problems would use 
> > very similar gms files, only much larger.
> 
>  
> 
> Equation e2 might be a real pain, while the rest appears to be convex. 
> You might consider giving Bonmin (older brother of Couenne in the 
> COIN-OR repository) a shot.
> 
>  
> 
> Hope this helps. Couenne is more or less a one-man project, with a few 
> contributors but only one maintainer (myself), and it takes some time to 
> implement and test new features. One very important one that I have in 
> mind is to be able to create a problem from within the program rather 
> than reading .nl files.
> 
>  
> 
> Thanks for your interest in Couenne. These emails are very welcome as 
> they tell me that there are users far outside the OR community. I would 
> be even happier if you could send messages like this to the Couenne 
> mailing list at couenne at list.coin-or.org (granted, I'd probably answer 
> those emails first, but those seeking an answer to a similar problem 
> would be able to google that).
> 
>  
> 
> Regards,
> 
> Pietro
> 
>  
> 
> --
> 
> Pietro Belotti
> Dept. of Mathematical Sciences
> Clemson University
> email: pbelott at clemson.edu
> phone: 864-656-6765
> web:   http://myweb.clemson.edu/~pbelott
> 
>  
> 
> On Tue, 6 Mar 2012, Tim Mullin wrote:
> 
>  
> 
> >
> > Dear Dr. Belotti:
> >
> >  
> >
> > I’ve recently come across COUENNE, on the recommendation of a Japanese
> > optimisation expert (Professor Makoto Yamashita) who thought it could
> > provide the solver power for a rather common problem in plant breeding.
> > Briefly, the objective is to maximise genetic performance when
> > selecting N individuals from a group of Z candidates, while
> > constraining on the relatedness by descent within the selected group.
> >
> >  
> >
> > At this point, we have succeed in developing the NLP formulation of
> > the optimisation problem, and have managed to solve small, toy
> > problems with a couple of solvers, SparsePOP and BARON.  Both of these
> > accept a .gms file as input.
> >
> >  
> >
> > Our requirement is to find a Windows-based standalone solver that has
> > the horsepower to solve real-life selection problems, and the ability
> > to be called from the command line by other tools (such as Monte Carlo
> > simulators).  BARON, of course, is an online solver, and runs out of
> > resources before producing good solutions for real-scale problems.
> > SparsePOP can conveniently be called from other programs in a Windows
> > environment, but crashes when we attempt larger problems.
> >
> >  
> >
> > I wanted to try COUENNE as an alternative solver, but realise that it
> > expects input as an .nl file.  I have tried to follow David Gay’s
> > paper on “Writing .nl files”, but confess I get hopelessly lost by
> > page 4.  I should stress that, while I am a quantitative forest
> > geneticist and tree breeder, I am NOT a mathematician and certainly
> > not an OR expert.  I’m feeling well out of my depth.  Getting this far
> > with our project and producing working gms input files has already
> > been a huge effort, but I definitely need help if I’m to translate our problem to an .nl file.
> >
> >  
> >
> > Is there such a thing as a conversion tool that can translate our gms
> > files to .nl?  I’ve found mention of a tool called COCONUT on Google
> > searches, but the links are dead.  If there is no such thing as a
> > converter, is there perhaps other instructional material that would
> > help me through the maze of generating .nl files “from scratch”?
> >
> >  
> >
> > All this, of course, so that we can test if COUENNE will really
> > provide an adequate solver for our selection problems.  As an
> > illustration, I’m attaching a gms file that optimises selection of 3
> > individuals from a pedigree of 14.  It is a “toy” example that is
> > easily solved by hand, but all of our real-life problems would use
> > very similar gms files, only much larger.
> >
> >  
> >
> > Thanking you in advance for your help on this.
> >
> >  
> >
> > Best regards,
> >
> >  
> >
> > Tim
> >
> >  
> >
> > BioSylve Forest Science NZ Limited
> >
> > and
> >
> > Skogforsk (Swedish Forestry Research Institute)
> >
> >  
> >
> > Dr. T.J. "Tim" Mullin, PhD, RPF
> >
> > 45 Korokoro Road
> >
> > Lower Hutt   5012
> >
> > NEW ZEALAND
> >
> > Phone: +64-(0)4-589 7676
> >
> > Mobile: 021-02 25 57 91
> >
> > Email: tim.mullin at BioSylve.com  tim.mullin at skogforsk.se
> >
> >  
> >
> > CAUTION: This e-mail message and accompanying data may contain
> > information that is confidential. If you are not the intended
> > recipient you are notified that any use, dissemination, distribution
> > or copying of this message or data is prohibited. All content is to be
> > treated as confidential unless otherwise specified, and is not to be
> > forwarded to third parties without the prior permission of the author.
> > To do so may breach the New Zealand Privacy Act 1993. If you have
> > received this e-mail message in error please delete it and notify me. Thank you.