|
|
 | | From: | Tom | | Subject: | CP on mathematical optimization problems | | Date: | Tue, 18 Jan 2005 22:53:11 +1000 |
|
|
 | Dear all,
I was wondering if there is any tool or research
related to solving nonlinear programming (NLP) or
linear programming (LP) problems by using
constraint programming.
For example:
minimize: f(x)
subject to: g(x) <= 0
h(x) =0
Thanks a lot,
I-Lun
|
|
| | From: | Andrew John Sadler | | Subject: | Re: CP on mathematical optimization problems | | Date: | 18 Jan 2005 16:40:35 +0000 |
|
|
| "Tom" writes:
> Dear all,
>
> I was wondering if there is any tool or research
> related to solving nonlinear programming (NLP) or
> linear programming (LP) problems by using
> constraint programming.
>
> For example:
> minimize: f(x)
> subject to: g(x) <= 0
> h(x) =0
>
>
> Thanks a lot,
> I-Lun
Hi Tom,
Indeed there are many such tools. I would recommend the ECLiPSe
system available here.... http://www.icparc.ic.ac.uk/eclipse/
It has many features that allow such problems (NLP and LP) to be
solved via constraint programming, linear programming, mixed integer
programming and even combinations of techniques (called hybrid
methods). I am slightly biased as I currently work as part of the
ECLiPSe team, but nevertheless ECLiPSe can certainly address your
needs.
Hope that helps..
Andrew
|
|
| | From: | Tom | | Subject: | Re: CP on mathematical optimization problems | | Date: | Wed, 19 Jan 2005 12:12:00 +1000 |
|
|
| Dear Andrew,
Thanks for the information.
I was also wondering if your tool can be used to solve NLP
problems, such as the problem in:
http://en.wikipedia.org/wiki/Nonlinear_programming
For the 2-dimensional example, I re-write the problem below:
minimize: f(x) = X1 + X2
subject to: X1 >= 0,
X2 >= 0,
(X1)^2 + (X2)^2 >= 1,
(X1)^2 + (X2)^2 <= 2
Thanks a lot,
Tom
"Andrew John Sadler" wrote in message
news:wzbrbmd724.fsf@cow.icparc.ic.ac.uk...
> "Tom" writes:
>
>> Dear all,
>>
>> I was wondering if there is any tool or research
>> related to solving nonlinear programming (NLP) or
>> linear programming (LP) problems by using
>> constraint programming.
>>
>> For example:
>> minimize: f(x)
>> subject to: g(x) <= 0
>> h(x) =0
>>
>>
>> Thanks a lot,
>> I-Lun
>
> Hi Tom,
>
> Indeed there are many such tools. I would recommend the ECLiPSe
> system available here.... http://www.icparc.ic.ac.uk/eclipse/
>
> It has many features that allow such problems (NLP and LP) to be
> solved via constraint programming, linear programming, mixed integer
> programming and even combinations of techniques (called hybrid
> methods). I am slightly biased as I currently work as part of the
> ECLiPSe team, but nevertheless ECLiPSe can certainly address your
> needs.
>
> Hope that helps..
>
> Andrew
|
|
| | From: | Andrew John Sadler | | Subject: | Re: CP on mathematical optimization problems | | Date: | 19 Jan 2005 09:41:31 +0000 |
|
|
| "Tom" writes:
> Dear Andrew,
>
> Thanks for the information.
> I was also wondering if your tool can be used to solve NLP
> problems, such as the problem in:
> http://en.wikipedia.org/wiki/Nonlinear_programming
> For the 2-dimensional example, I re-write the problem below:
>
> minimize: f(x) = X1 + X2
> subject to: X1 >= 0,
> X2 >= 0,
> (X1)^2 + (X2)^2 >= 1,
> (X1)^2 + (X2)^2 <= 2
>
>
> Thanks a lot,
> Tom
>
>
Hi Tom,
Here would be one way to solve your problem in ECLiPSe...
:-lib(ic).
:-lib(branch_and_bound).
my_problem(X1,X2,Fx):-
X1 $>= 0,
X2 $>= 0,
X1*X1 + X2*X2 $>=1,
X1*X1+ X2*X2 $=<2,
Fx $= X1 + X2,
minimize((locate([X1,X2,Fx],0.00000000001),get_max(Fx,Fx)),Fx).
The line ":-lib(ic)." loads the "Interval Constraints" library which
allows arbitrary constraint solving over real or integer variables.
The line ":-lib(branch_and_bound)." loads the "Branch and Bound"
library for optimising objective functions.
The line "my_problem(X1,X2,Fx)" defines a predicate that when called
will setup the constraints including a constraint to define the value
of the objective variable "Fx $= X1 + X2".
Then the final line
minimize((locate([X1,X2,Fx],0.00000000001),get_max(Fx,Fx)), Fx) works
by iteratively narrowing the bounds on the three variables X1, X2 and
Fx until a minimum precision is reached "0.00000000001", using the
"locate" predicate, then instantiating the cost variable to its
upperbound "get_max(Fx,Fx)". The enclosing "minimize" predicate
states that this process should be repeated until the cost variable
has been prooved minimum (subject to some numeric tolerance which is
not expilicitly stated).
This is a very simple example of how such problems can be modelled and
solved in ECLiPSe, though there are many more advanced features too.
Incidentaly, calling the above predicate returns the following answers
?- top(X1, X2, Fx).
X1 = X1{0.0 .. 6.7761352084971804e-12}
X2 = X2{0.99999999999999978 .. 1.0000000000067759}
Fx = 1.0000000000067759
Andrew
|
|
| | From: | A.L. | | Subject: | Re: CP on mathematical optimization problems | | Date: | Wed, 19 Jan 2005 06:24:21 -0600 |
|
|
| On 19 Jan 2005 09:41:31 +0000, Andrew John Sadler
wrote:
>"
>
>Hi Tom,
>
>Here would be one way to solve your problem in ECLiPSe...
>
However, not necessary the most efficient one...
A.L.
|
|
|
