[Couenne] Nonlinear relaxations of problem

[Pietro Belotti]

Hi Helder,

> my understanding is that given a problem, Couenne, by introducing new
> variables and
> constraints will build a reformulated problem, and then solve a linearized
> version of this reformulated problem.

This is correct. The linear relaxation of the reformulation gives a  
valid lower bound.

> What I would like to do is to have Couenne do this reformulation for most of
> the terms, but for some specific terms
> keep these terms in the model and then solve a nonlinear relaxation instead
> of a linear one.
> As an example if I have a term x*y Couenne would introduce a variable z and
> then maybe Mccormick relaxations, but
> if I have a quadratic convex constraint I would like to leave it in the
> problem.

Couenne, for now, uses an LP solver for obtaining a lower bound, and  
switching to a convex solver requires quite some coding, although it  
is certainly possible. First of all, the OsiSolverInterface used for  
the LP relaxation should change to some more general object containing  
the nonlinear information. This is in my todo list, but it is not  
there at the moment.

I'm not sure if this could be useful, but quadratic expressions can  
also be handled by Couenne. If the quadratic is convex, a procedure  
will generate an outer approximation of the quadratic instead of  
decomposing it. If it is nonconvex, an alpha-convexification (see the  
work by Nowak and Vigerske for a good explanation) generates a convex  
relaxation of it. In order to use it, you should have an option file  
couenne.opt with the line

use_quadratic yes

Hope this helps.

Cheers,
Pietro

_________________________________________
Pietro Belotti, Lehigh University
Dept. of Industrial and Systems Engineering
200 W Packer Ave, Bethlehem PA 18015.
phone: 610-758-3865   fax: 610-758-4886
email: belotti at lehigh.edu
web:   http://www.lehigh.edu/~pib208


On 04/26/2010, H Inacio <hjmypg at gmail.com> wrote:

> Hi all,
>
> my understanding is that given a problem, Couenne, by introducing new
> variables and
> constraints will build a reformulated problem, and then solve a linearized
> version of this reformulated problem.
>
> What I would like to do is to have Couenne do this reformulation for most of
> the terms, but for some specific terms
> keep these terms in the model and then solve a nonlinear relaxation instead
> of a linear one.
> As an example if I have a term x*y Couenne would introduce a variable z and
> then maybe Mccormick relaxations, but
> if I have a quadratic convex constraint I would like to leave it in the
> problem.
>
> Is this possible to do in Couenne?
> What would be the major modifications in the code I would have to do to
> acomplish this?
>
> Thank you very much.
>
> Helder Inacio
>



----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.