No subject
Wed Mar 7 20:39:40 EST 2012
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.
=20
6. Next steps
After reading your suggestions, it seems to me that my next steps, =
roughly in order of priority, are:
=C2=B7 Understand what went wrong with COUENNE's execution of =
Ex14.nl and how to fix it
=C2=B7 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)
=C2=B7 Explore behaviour and control of alternative solvers, =
such as Windows COUENNE and Bonmin
=20
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=E2=80=99ve come a long way in =
describing our problem(s) in terms of mathematical programming models =
=E2=80=93 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.
=20
Very best regards,
=20
Tim
=20
-----Original Message-----
From: Pietro Belotti [mailto:pbelott at clemson.edu]=20
Sent: Tuesday, 6 March 2012 5:38 p.m.
To: Tim Mullin
Subject: Re: Input for COUENNE
=20
Dear Dr. Mullin,
=20
> At this point, we have succeed in developing the NLP formulation of=20
> the optimisation problem, and have managed to solve small, toy=20
> problems with a couple of solvers, SparsePOP and BARON. Both of these =
> accept a .gms file as input.
=20
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.
=20
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
=20
time_limit 1234
=20
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.
=20
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:
=20
feas_pump_heuristic yes
=20
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).
=20
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).
=20
> Our requirement is to find a Windows-based standalone solver that has=20
> the horsepower to solve real-life selection problems, and the ability=20
> 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=20
> resources before producing good solutions for real-scale problems.
> SparsePOP can conveniently be called from other programs in a Windows=20
> environment, but crashes when we attempt larger problems.
=20
Couenne could be a solution to that, as binaries are available for =
Windows at
=20
<http://www.coin-or.org/download/binary/Couenne> =
http://www.coin-or.org/download/binary/Couenne
=20
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).
=20
> I wanted to try COUENNE as an alternative solver, but realise that it=20
> expects input as an .nl file. I have tried to follow David =
Gay=E2=80=99s=20
> paper on =E2=80=9CWriting .nl files=E2=80=9D, but confess I get =
hopelessly lost by=20
> page 4. I should stress that, while I am a quantitative forest=20
> geneticist and tree breeder, I am NOT a mathematician and certainly=20
> not an OR expert. I=E2=80=99m feeling well out of my depth. Getting =
this far=20
> with our project and producing working gms input files has already=20
> been a huge effort, but I definitely need help if I=E2=80=99m to =
translate our problem to an .nl file.
>=20
> Is there such a thing as a conversion tool that can translate our gms=20
> files to .nl?
=20
Yes. Details below.
=20
> I=E2=80=99ve found mention of a tool called COCONUT on Google =
searches, but=20
> the links are dead.
=20
I managed to use COCONUT some time ago, but I do not have the code with =
me.
=20
> If there is no such thing as a converter, is there perhaps other=20
> instructional material that would help me through the maze of=20
> generating .nl files =E2=80=9Cfrom scratch=E2=80=9D?
=20
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.
=20
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.
=20
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:
=20
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.
=20
With the example you sent me, Couenne gives the output as in the file =
ex14.txt attached.
=20
> All this, of course, so that we can test if COUENNE will really=20
> provide an adequate solver for our selection problems. As an=20
> illustration, I=E2=80=99m attaching a gms file that optimises =
selection of 3=20
> individuals from a pedigree of 14. It is a =E2=80=9Ctoy=E2=80=9D =
example that is=20
> easily solved by hand, but all of our real-life problems would use=20
> very similar gms files, only much larger.
=20
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.
=20
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.
=20
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 <mailto:couenne at list.coin-or.org> =
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).
=20
Regards,
Pietro
=20
--
Pietro Belotti
Dept. of Mathematical Sciences
Clemson University
email: <mailto:pbelott at clemson.edu> pbelott at clemson.edu
phone: 864-656-6765
web: <http://myweb.clemson.edu/~pbelott> =
http://myweb.clemson.edu/~pbelott
=20
On Tue, 6 Mar 2012, Tim Mullin wrote:
=20
>=20
> Dear Dr. Belotti:
>=20
> =20
>=20
> I=E2=80=99ve recently come across COUENNE, on the recommendation of a =
Japanese=20
> optimisation expert (Professor Makoto Yamashita) who thought it could=20
> provide the solver power for a rather common problem in plant =
breeding.
> Briefly, the objective is to maximise genetic performance when=20
> selecting N individuals from a group of Z candidates, while=20
> constraining on the relatedness by descent within the selected group.
>=20
> =20
>=20
> At this point, we have succeed in developing the NLP formulation of=20
> the optimisation problem, and have managed to solve small, toy=20
> problems with a couple of solvers, SparsePOP and BARON. Both of these =
> accept a .gms file as input.
>=20
> =20
>=20
> Our requirement is to find a Windows-based standalone solver that has=20
> the horsepower to solve real-life selection problems, and the ability=20
> 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=20
> resources before producing good solutions for real-scale problems.
> SparsePOP can conveniently be called from other programs in a Windows=20
> environment, but crashes when we attempt larger problems.
>=20
> =20
>=20
> I wanted to try COUENNE as an alternative solver, but realise that it=20
> expects input as an .nl file. I have tried to follow David =
Gay=E2=80=99s=20
> paper on =E2=80=9CWriting .nl files=E2=80=9D, but confess I get =
hopelessly lost by=20
> page 4. I should stress that, while I am a quantitative forest=20
> geneticist and tree breeder, I am NOT a mathematician and certainly=20
> not an OR expert. I=E2=80=99m feeling well out of my depth. Getting =
this far=20
> with our project and producing working gms input files has already=20
> been a huge effort, but I definitely need help if I=E2=80=99m to =
translate our problem to an .nl file.
>=20
> =20
>=20
> Is there such a thing as a conversion tool that can translate our gms=20
> files to .nl? I=E2=80=99ve found mention of a tool called COCONUT on =
Google=20
> searches, but the links are dead. If there is no such thing as a=20
> converter, is there perhaps other instructional material that would=20
> help me through the maze of generating .nl files =E2=80=9Cfrom =
scratch=E2=80=9D?
>=20
> =20
>=20
> All this, of course, so that we can test if COUENNE will really=20
> provide an adequate solver for our selection problems. As an=20
> illustration, I=E2=80=99m attaching a gms file that optimises =
selection of 3=20
> individuals from a pedigree of 14. It is a =E2=80=9Ctoy=E2=80=9D =
example that is=20
> easily solved by hand, but all of our real-life problems would use=20
> very similar gms files, only much larger.
>=20
> =20
>=20
> Thanking you in advance for your help on this.
>=20
> =20
>=20
> Best regards,
>=20
> =20
>=20
> Tim
>=20
> =20
>=20
> BioSylve Forest Science NZ Limited
>=20
> and
>=20
> Skogforsk (Swedish Forestry Research Institute)
>=20
> =20
>=20
> Dr. T.J. "Tim" Mullin, PhD, RPF
>=20
> 45 Korokoro Road
>=20
> Lower Hutt 5012
>=20
> NEW ZEALAND
>=20
> Phone: +64-(0)4-589 7676
>=20
> Mobile: 021-02 25 57 91
>=20
> Email: <mailto:tim.mullin at BioSylve.com> tim.mullin at BioSylve.com =
<mailto:tim.mullin at skogforsk.se> tim.mullin at skogforsk.se
>=20
> =20
>=20
> CAUTION: This e-mail message and accompanying data may contain=20
> information that is confidential. If you are not the intended=20
> recipient you are notified that any use, dissemination, distribution=20
> 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=20
> 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=20
> received this e-mail message in error please delete it and notify me. =
Thank you.
------=_NextPart_000_003F_01CCFC56.F65DA120
Content-Type: text/html;
charset="utf-8"
Content-Transfer-Encoding: quoted-printable
<html xmlns:v=3D"urn:schemas-microsoft-com:vml" =
xmlns:o=3D"urn:schemas-microsoft-com:office:office" =
xmlns:w=3D"urn:schemas-microsoft-com:office:word" =
xmlns:m=3D"http://schemas.microsoft.com/office/2004/12/omml" =
xmlns=3D"http://www.w3.org/TR/REC-html40"><head><meta =
http-equiv=3DContent-Type content=3D"text/html; charset=3Dutf-8"><meta =
name=3DGenerator content=3D"Microsoft Word 14 (filtered =
medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";
mso-fareast-language:EN-US;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.MsoPlainText, li.MsoPlainText, div.MsoPlainText
{mso-style-priority:99;
mso-style-link:"Plain Text Char";
margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";
mso-fareast-language:EN-US;}
span.PlainTextChar
{mso-style-name:"Plain Text Char";
mso-style-priority:99;
mso-style-link:"Plain Text";
font-family:"Calibri","sans-serif";}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:1069763546;
mso-list-type:hybrid;
mso-list-template-ids:1344689732 336134145 336134147 336134149 =
336134145 336134147 336134149 336134145 336134147 336134149;}
@list l0:level1
{mso-level-number-format:bullet;
mso-level-text:=EF=82=B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:=EF=82=A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:=EF=82=B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:=EF=82=A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:=EF=82=B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:=EF=82=A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext=3D"edit" spidmax=3D"1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext=3D"edit">
<o:idmap v:ext=3D"edit" data=3D"1" />
</o:shapelayout></xml><![endif]--></head><body lang=3DEN-NZ link=3Dblue =
vlink=3Dpurple><div class=3DWordSection1><p =
class=3DMsoPlainText>Pietro:<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>Thank =
you for your very prompt and detailed response to my questions on the =
care and feeding of COUENNE.=C2=A0 You've covered a lot of ground in =
your response, so I'll try to condense my supplementary questions under =
discrete headings:<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText><b>1. =
Translating gms to nl files<o:p></o:p></b></p><p class=3DMsoPlainText>In =
fact, I have access to neither GAMS nor AMPL currently.=C2=A0 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.=C2=A0 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?<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText><b>2. =
COUENNE and the 14-tree "toy" problem<o:p></o:p></b></p><p =
class=3DMsoPlainText>The ex14.gms file I provided currently results =
identical (correct) solutions when submitted to either BARON or =
SparsePOP.=C2=A0 The correct solution is easy to find manually, but both =
solvers agree.=C2=A0 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".=C2=A0 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.=C2=A0 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).=C2=A0 I'm not sure what is going on =
with COUENNE and why it does not seem to solve correctly.=C2=A0 =
Obviously, I need to understand how to fix this, if we are to continue =
with larger-scale problems.<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText><b>3. =
What is a "reasonably good solution"<o:p></o:p></b></p><p =
class=3DMsoPlainText>We have both operational and research applications =
for this model.=C2=A0 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.=C2=A0 For research purposes, we are generally interested in =
incorporating the solver into Monte Carlo simulations where execution =
times beome rather important.=C2=A0 In this case, finding the true =
optimum is not so important, provided that the solution is a =
"good" one.=C2=A0 What is "reasonably good"?=C2=A0 =
Here were are looking for a solution with exactly N variables equal to =
1, and the rest equal to -1.=C2=A0 Anything short of this would require =
some sort of improvement through heuristics or some other =
strategy.=C2=A0 I think this needs experience with some of the =
approaches you=E2=80=99ve suggested to determine the =
best.<o:p></o:p></p><p class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText><b>4.=C2=A0 Problem size<o:p></o:p></b></p><p =
class=3DMsoPlainText>Both SparsePOP and BARON easily solved our ex14.gms =
=E2=80=9Ctoy=E2=80=9D problem, suggesting that our formulation works as =
intended and that our .gms file is correct.=C2=A0 Both crash when asked =
to solve =E2=80=9Creal-scale=E2=80=9D problems.=C2=A0 The number of =
variables for these problems would generally be less than 500 (we can =
truncate our selection list by some "smart" =
preconditioning).=C2=A0 However, the number of terms in equation e2 will =
always be greater, sometimes much greater (say, up to 10x).=C2=A0 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.=C2=A0 I =
understand that equation e2 is a challenge for any solver but it is also =
the heart of the solution.<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText><b>5.=C2=A0 Alternative =
solvers<o:p></o:p></b></p><p class=3DMsoPlainText>From what you tell me, =
it sounds like Bonmin warrants some investigation to see if it will =
provide our power and flexibility needs.=C2=A0 Sounds also like I still =
have to master the business of generating .nl files if I'm to use =
it.<o:p></o:p></p><p class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText><b>6.=C2=A0 Next steps<o:p></o:p></b></p><p =
class=3DMsoPlainText>After reading your suggestions, it seems to me that =
my next steps, roughly in order of priority, are:<o:p></o:p></p><p =
class=3DMsoPlainText =
style=3D'margin-left:36.0pt;text-indent:-18.0pt;mso-list:l0 level1 =
lfo1'><![if !supportLists]><span style=3D'font-family:Symbol'><span =
style=3D'mso-list:Ignore'>=C2=B7<span style=3D'font:7.0pt "Times New =
Roman"'> =
</span></span></span><![endif]>Understand what went wrong with COUENNE's =
execution of Ex14.nl and how to fix it<o:p></o:p></p><p =
class=3DMsoPlainText =
style=3D'margin-left:36.0pt;text-indent:-18.0pt;mso-list:l0 level1 =
lfo1'><![if !supportLists]><span style=3D'font-family:Symbol'><span =
style=3D'mso-list:Ignore'>=C2=B7<span style=3D'font:7.0pt "Times New =
Roman"'> =
</span></span></span><![endif]>Learn to access AMPL and generate .nl =
files with it from .gms or .mod files=C2=A0 (I think I can easily modify =
my .gms file generator to produce .mod files instead)<o:p></o:p></p><p =
class=3DMsoPlainText =
style=3D'margin-left:36.0pt;text-indent:-18.0pt;mso-list:l0 level1 =
lfo1'><![if !supportLists]><span style=3D'font-family:Symbol'><span =
style=3D'mso-list:Ignore'>=C2=B7<span style=3D'font:7.0pt "Times New =
Roman"'> =
</span></span></span><![endif]>Explore behaviour and control of =
alternative solvers, such as Windows COUENNE and Bonmin<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>Thank =
you again for your help with this.=C2=A0 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.=C2=A0 The =
learning curve is very steep.=C2=A0 We feel that we=E2=80=99ve come a =
long way in describing our problem(s) in terms of mathematical =
programming models =E2=80=93 it would be really good if we could find =
solvers that can be applied to these models in practice.=C2=A0 This will =
be of huge benefit, not just for tree breeders, but for ALL types of =
breeding activities, regardless of organism.<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>Very =
best regards,<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText>Tim<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText><span =
lang=3DEN-US style=3D'mso-fareast-language:EN-NZ'>-----Original =
Message-----<br>From: Pietro Belotti [mailto:pbelott at clemson.edu] =
<br>Sent: Tuesday, 6 March 2012 5:38 p.m.<br>To: Tim Mullin<br>Subject: =
Re: Input for COUENNE</span></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>Dear =
Dr. Mullin,<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>> =
At this point, we have succeed in developing the NLP formulation of =
<o:p></o:p></p><p class=3DMsoPlainText>> the optimisation problem, =
and have managed to solve small, toy <o:p></o:p></p><p =
class=3DMsoPlainText>> problems with a couple of solvers, SparsePOP =
and BARON. Both of these <o:p></o:p></p><p =
class=3DMsoPlainText>> accept a .gms file as input.<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>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<o:p></o:p></p><p class=3DMsoPlainText>2000 constraints (although it =
very much depends on the type of<o:p></o:p></p><p =
class=3DMsoPlainText>constraints) are usually quite hard to =
solve.<o:p></o:p></p><p class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText>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<o:p></o:p></p><p class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText>time_limit 1234<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>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.<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText>Second, use the "feasibility pump", a =
more thorough (but more time<o:p></o:p></p><p =
class=3DMsoPlainText>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:<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText>feas_pump_heuristic yes<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText>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).<o:p></o:p></p><p class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText>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).<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>> =
Our requirement is to find a Windows-based standalone solver that has =
<o:p></o:p></p><p class=3DMsoPlainText>> the horsepower to solve =
real-life selection problems, and the ability <o:p></o:p></p><p =
class=3DMsoPlainText>> to be called from the command line by other =
tools (such as Monte Carlo <o:p></o:p></p><p class=3DMsoPlainText>> =
simulators). BARON, of course, is an online solver, and runs out =
of <o:p></o:p></p><p class=3DMsoPlainText>> resources before =
producing good solutions for real-scale problems.<o:p></o:p></p><p =
class=3DMsoPlainText>> SparsePOP can conveniently be called from =
other programs in a Windows <o:p></o:p></p><p class=3DMsoPlainText>> =
environment, but crashes when we attempt larger =
problems.<o:p></o:p></p><p class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText>Couenne could be a solution to that, as binaries =
are available for Windows at<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText><a =
href=3D"http://www.coin-or.org/download/binary/Couenne"><span =
style=3D'color:windowtext;text-decoration:none'>http://www.coin-or.org/do=
wnload/binary/Couenne</span></a><o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText>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).<o:p></o:p></p><p class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText>> I wanted to try COUENNE as an alternative =
solver, but realise that it <o:p></o:p></p><p class=3DMsoPlainText>> =
expects input as an .nl file. I have tried to follow David =
Gay=E2=80=99s <o:p></o:p></p><p class=3DMsoPlainText>> paper on =
=E2=80=9CWriting .nl files=E2=80=9D, but confess I get hopelessly lost =
by <o:p></o:p></p><p class=3DMsoPlainText>> page 4. I should =
stress that, while I am a quantitative forest <o:p></o:p></p><p =
class=3DMsoPlainText>> geneticist and tree breeder, I am NOT a =
mathematician and certainly <o:p></o:p></p><p class=3DMsoPlainText>> =
not an OR expert. I=E2=80=99m feeling well out of my depth. =
Getting this far <o:p></o:p></p><p class=3DMsoPlainText>> with our =
project and producing working gms input files has already =
<o:p></o:p></p><p class=3DMsoPlainText>> been a huge effort, but I =
definitely need help if I=E2=80=99m to translate our problem to an .nl =
file.<o:p></o:p></p><p class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> Is there such a thing as a conversion tool =
that can translate our gms <o:p></o:p></p><p class=3DMsoPlainText>> =
files to .nl?<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>Yes. =
Details below.<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>> =
I=E2=80=99ve found mention of a tool called COCONUT on Google searches, =
but <o:p></o:p></p><p class=3DMsoPlainText>> the links are =
dead.<o:p></o:p></p><p class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText>I managed to use COCONUT some time ago, but I do =
not have the code with me.<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>> =
If there is no such thing as a converter, is there perhaps other =
<o:p></o:p></p><p class=3DMsoPlainText>> instructional material that =
would help me through the maze of <o:p></o:p></p><p =
class=3DMsoPlainText>> generating .nl files =E2=80=9Cfrom =
scratch=E2=80=9D?<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText>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.<o:p></o:p></p><p class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText>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.<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>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:<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>1) set =
Couenne as the solver;<o:p></o:p></p><p class=3DMsoPlainText>2) start =
optimization;<o:p></o:p></p><p class=3DMsoPlainText>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.<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>With =
the example you sent me, Couenne gives the output as in the file =
ex14.txt attached.<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>> =
All this, of course, so that we can test if COUENNE will really =
<o:p></o:p></p><p class=3DMsoPlainText>> provide an adequate solver =
for our selection problems. As an <o:p></o:p></p><p =
class=3DMsoPlainText>> illustration, I=E2=80=99m attaching a gms file =
that optimises selection of 3 <o:p></o:p></p><p =
class=3DMsoPlainText>> individuals from a pedigree of 14. It is =
a =E2=80=9Ctoy=E2=80=9D example that is <o:p></o:p></p><p =
class=3DMsoPlainText>> easily solved by hand, but all of our =
real-life problems would use <o:p></o:p></p><p class=3DMsoPlainText>> =
very similar gms files, only much larger.<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText>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<o:p></o:p></p><p class=3DMsoPlainText>repository) =
a shot.<o:p></o:p></p><p class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText>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.<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>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 <a href=3D"mailto:couenne at list.coin-or.org"><span =
style=3D'color:windowtext;text-decoration:none'>couenne at list.coin-or.org<=
/span></a> (granted, I'd probably answer those emails first, but those =
seeking an answer to a similar problem would be able to google =
that).<o:p></o:p></p><p class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText>Regards,<o:p></o:p></p><p =
class=3DMsoPlainText>Pietro<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p =
class=3DMsoPlainText>--<o:p></o:p></p><p class=3DMsoPlainText>Pietro =
Belotti<o:p></o:p></p><p class=3DMsoPlainText>Dept. of Mathematical =
Sciences<o:p></o:p></p><p class=3DMsoPlainText>Clemson =
University<o:p></o:p></p><p class=3DMsoPlainText>email: <a =
href=3D"mailto:pbelott at clemson.edu"><span =
style=3D'color:windowtext;text-decoration:none'>pbelott at clemson.edu</span=
></a><o:p></o:p></p><p class=3DMsoPlainText>phone: =
864-656-6765<o:p></o:p></p><p class=3DMsoPlainText>web:=C2=A0=C2=A0 <a =
href=3D"http://myweb.clemson.edu/~pbelott"><span =
style=3D'color:windowtext;text-decoration:none'>http://myweb.clemson.edu/=
~pbelott</span></a><o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>On =
Tue, 6 Mar 2012, Tim Mullin wrote:<o:p></o:p></p><p =
class=3DMsoPlainText><o:p> </o:p></p><p class=3DMsoPlainText>> =
<o:p></o:p></p><p class=3DMsoPlainText>> Dear Dr. =
Belotti:<o:p></o:p></p><p class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p class=3DMsoPlainText>> =
I=E2=80=99ve recently come across COUENNE, on the recommendation of a =
Japanese <o:p></o:p></p><p class=3DMsoPlainText>> optimisation expert =
(Professor Makoto Yamashita) who thought it could <o:p></o:p></p><p =
class=3DMsoPlainText>> provide the solver power for a rather common =
problem in plant breeding.<o:p></o:p></p><p class=3DMsoPlainText>> =
Briefly, the objective is to maximise genetic performance when =
<o:p></o:p></p><p class=3DMsoPlainText>> selecting N individuals from =
a group of Z candidates, while <o:p></o:p></p><p =
class=3DMsoPlainText>> constraining on the relatedness by descent =
within the selected group.<o:p></o:p></p><p class=3DMsoPlainText>> =
<o:p></o:p></p><p class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p class=3DMsoPlainText>> At =
this point, we have succeed in developing the NLP formulation of =
<o:p></o:p></p><p class=3DMsoPlainText>> the optimisation problem, =
and have managed to solve small, toy <o:p></o:p></p><p =
class=3DMsoPlainText>> problems with a couple of solvers, SparsePOP =
and BARON. Both of these <o:p></o:p></p><p =
class=3DMsoPlainText>> accept a .gms file as input.<o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p class=3DMsoPlainText>> =
<o:p></o:p></p><p class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> Our requirement is to find a Windows-based =
standalone solver that has <o:p></o:p></p><p class=3DMsoPlainText>> =
the horsepower to solve real-life selection problems, and the ability =
<o:p></o:p></p><p class=3DMsoPlainText>> to be called from the =
command line by other tools (such as Monte Carlo <o:p></o:p></p><p =
class=3DMsoPlainText>> simulators). BARON, of course, is an =
online solver, and runs out of <o:p></o:p></p><p =
class=3DMsoPlainText>> resources before producing good solutions for =
real-scale problems.<o:p></o:p></p><p class=3DMsoPlainText>> =
SparsePOP can conveniently be called from other programs in a Windows =
<o:p></o:p></p><p class=3DMsoPlainText>> environment, but crashes =
when we attempt larger problems.<o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p class=3DMsoPlainText>> =
<o:p></o:p></p><p class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> I wanted to try COUENNE as an alternative =
solver, but realise that it <o:p></o:p></p><p class=3DMsoPlainText>> =
expects input as an .nl file. I have tried to follow David =
Gay=E2=80=99s <o:p></o:p></p><p class=3DMsoPlainText>> paper on =
=E2=80=9CWriting .nl files=E2=80=9D, but confess I get hopelessly lost =
by <o:p></o:p></p><p class=3DMsoPlainText>> page 4. I should =
stress that, while I am a quantitative forest <o:p></o:p></p><p =
class=3DMsoPlainText>> geneticist and tree breeder, I am NOT a =
mathematician and certainly <o:p></o:p></p><p class=3DMsoPlainText>> =
not an OR expert. I=E2=80=99m feeling well out of my depth. =
Getting this far <o:p></o:p></p><p class=3DMsoPlainText>> with our =
project and producing working gms input files has already =
<o:p></o:p></p><p class=3DMsoPlainText>> been a huge effort, but I =
definitely need help if I=E2=80=99m to translate our problem to an .nl =
file.<o:p></o:p></p><p class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p class=3DMsoPlainText>> Is =
there such a thing as a conversion tool that can translate our gms =
<o:p></o:p></p><p class=3DMsoPlainText>> files to .nl? =
I=E2=80=99ve found mention of a tool called COCONUT on Google =
<o:p></o:p></p><p class=3DMsoPlainText>> searches, but the links are =
dead. If there is no such thing as a <o:p></o:p></p><p =
class=3DMsoPlainText>> converter, is there perhaps other =
instructional material that would <o:p></o:p></p><p =
class=3DMsoPlainText>> help me through the maze of generating .nl =
files =E2=80=9Cfrom scratch=E2=80=9D?<o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p class=3DMsoPlainText>> =
<o:p></o:p></p><p class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> All this, of course, so that we can test if =
COUENNE will really <o:p></o:p></p><p class=3DMsoPlainText>> provide =
an adequate solver for our selection problems. As an =
<o:p></o:p></p><p class=3DMsoPlainText>> illustration, I=E2=80=99m =
attaching a gms file that optimises selection of 3 <o:p></o:p></p><p =
class=3DMsoPlainText>> individuals from a pedigree of 14. It is =
a =E2=80=9Ctoy=E2=80=9D example that is <o:p></o:p></p><p =
class=3DMsoPlainText>> easily solved by hand, but all of our =
real-life problems would use <o:p></o:p></p><p class=3DMsoPlainText>> =
very similar gms files, only much larger.<o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p class=3DMsoPlainText>> =
<o:p></o:p></p><p class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> Thanking you in advance for your help on =
this.<o:p></o:p></p><p class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p class=3DMsoPlainText>> =
Best regards,<o:p></o:p></p><p class=3DMsoPlainText>> =
<o:p></o:p></p><p class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p class=3DMsoPlainText>> =
Tim<o:p></o:p></p><p class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p class=3DMsoPlainText>> =
BioSylve Forest Science NZ Limited<o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p class=3DMsoPlainText>> =
and<o:p></o:p></p><p class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> Skogforsk (Swedish Forestry Research =
Institute)<o:p></o:p></p><p class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p class=3DMsoPlainText>> =
Dr. T.J. "Tim" Mullin, PhD, RPF<o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p class=3DMsoPlainText>> 45 =
Korokoro Road<o:p></o:p></p><p class=3DMsoPlainText>> =
<o:p></o:p></p><p class=3DMsoPlainText>> Lower Hutt =
5012<o:p></o:p></p><p class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> NEW ZEALAND<o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p class=3DMsoPlainText>> =
Phone: +64-(0)4-589 7676<o:p></o:p></p><p class=3DMsoPlainText>> =
<o:p></o:p></p><p class=3DMsoPlainText>> Mobile: 021-02 25 57 =
91<o:p></o:p></p><p class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> Email: <a =
href=3D"mailto:tim.mullin at BioSylve.com"><span =
style=3D'color:windowtext;text-decoration:none'>tim.mullin at BioSylve.com</=
span></a> <a href=3D"mailto:tim.mullin at skogforsk.se"><span =
style=3D'color:windowtext;text-decoration:none'>tim.mullin at skogforsk.se</=
span></a><o:p></o:p></p><p class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p =
class=3DMsoPlainText>> <o:p></o:p></p><p class=3DMsoPlainText>> =
CAUTION: This e-mail message and accompanying data may contain =
<o:p></o:p></p><p class=3DMsoPlainText>> information that is =
confidential. If you are not the intended <o:p></o:p></p><p =
class=3DMsoPlainText>> recipient you are notified that any use, =
dissemination, distribution <o:p></o:p></p><p class=3DMsoPlainText>> =
or copying of this message or data is prohibited. All content is to be =
<o:p></o:p></p><p class=3DMsoPlainText>> treated as confidential =
unless otherwise specified, and is not to be <o:p></o:p></p><p =
class=3DMsoPlainText>> forwarded to third parties without the prior =
permission of the author. <o:p></o:p></p><p class=3DMsoPlainText>> To =
do so may breach the New Zealand Privacy Act 1993. If you have =
<o:p></o:p></p><p class=3DMsoPlainText>> received this e-mail message =
in error please delete it and notify me. Thank =
you.<o:p></o:p></p></div></body></html>
------=_NextPart_000_003F_01CCFC56.F65DA120--
More information about the Couenne
mailing list