[Couenne] Possible bug in adding branching objects

[Pietro Belotti]

Hi Pete,

that part didn't change over the years, and I think this is a correct  
behavior. You may find a more detailed explanation in the paper  
"Branching and bounds tightening techniques for non-convex MINLP"  
linked below:

http://www.optimization-online.org/DB_HTML/2008/08/2059.html
http://www.informaworld.com/smpp/content~db=all~content=a913750293~frm=titlelink?words=belotti&hash=633929582

As you know, Couenne uses a linear relaxation to find a lower bound to  
a nonlinear problem. Given a nonlinear constraint y=f(x), where f is  
nonlinear, a branching rule uses a disjunction (x <= a OR x >= a),  
where x is a variable and a is a constant, in order to partition the  
problem in two subproblems and obtain a tighter relaxation and better  
lower bounds. The branching rule is only necessary when the solution  
(x0,y0) to the linear relaxation is such that y0 != f(x0).

Branching rules, therefore, are only necessary with nonlinear  
constraints (and with integer variables). When f is linear, the  
constraint y=f(x) is directly added to the linear relaxation and is  
hence never violated, therefore there is no need to add x as a  
branching variable if it only appears as an argument of f and f is  
linear.

Considering your example, w_4 should not trigger a branching rule on  
w_3 as the linear equation linking them is always satisfied by the  
relaxation. In that case, only x_1 needs to be branched on, because  
the linear relaxation might have a solution (x_1,w_2,w_3,w_4) where  
w_2 != x_1 ^ 2.

I hope this answer your question.

Best,
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 06/08/2010, Pete Janes <ppjanes at gmail.com> wrote:

> Hi Pietro,
>
> I notice that there might be a bug in the way Couenne adds new branching
> objects in main/BonCouenneSetup.cpp. Here, an object associated with an
> exprVar is added:
>
> continuousSolver_ -> addObjects (nobj, objects)
>
> if 1) it is an integer variable, or 2) it has at least another variable
> which is dependent on it. I think the problem lies with the way the
> dependency determined in problem/fillDependence.cpp as it does not consider
> a linear variable as a dependent. For example:
>
> w_3 = x_1 ^ 2
> w_4 = w_3 + w_2
>
> w_4 is clearly dependent on w_3, but the dependency graph does not include
> this relationship as w_4 is linear. This is seen in the code
> in problem/fillDependence.cpp:
>
> for (std::vector <exprVar *>::iterator i = variables_.begin ();
>        i != variables_.end (); ++i) {
>
>     if (((*i) -> Type () == AUX)                           // consider aux's
> only
> && ((*i) -> Image () -> Linearity () > LINEAR)) {  // and nonlinear
>     }
>
> This affects how the number of infeasibilities are counted, as
> checkInfeasibilities() is only called on branching variables. This means
> that some solution calculated by CLP may be accepted as a solution to the
> primal problem, when they are actually infeasible. I am using an old
> modified version of Couenne, but I have checked the latest source code. I am
> not sure why I didn't notice this problem before.
>
> Regards,
>
> Pete
>



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