[Couenne] Multilinear model formulations

[Pietro Belotti]

Akshay,

some similar experiments I did (although that was long ago, with Couenne 
not even stable/0.1) suggest there is no difference in the performance 
w.r.t. the order in which one orders the bilinear terms.

The reformulation step would produce a new problem (with auxiliaries) that 
would be the same whether or not you define those auxiliaries explicitly 
beforehand. Some difference in performance may come from the order in 
which products are created, but that is not easy to measure and I could 
not determine whether certain groupings are better than others.

> For example, does this pre-empt any cut generation ? Is it able to 
> detect the original multilinear constraint from the new computational 
> graph and generate the same multi-term (if any) cuts as before ?

Interesting point. First answer: the default options decompose all 
multilinear terms (x1 * x2 * ... * xn) into products of two variables 
using the recursive procedure of Ryoo and Sahinidis. Hence it subsequently 
forgets the set of terms it came from.

Second: there are options in Couenne to add cuts for trilinear terms (see 
http://www.lix.polytechnique.fr/~liberti/quarticbook.pdf). Every product 
of four or more variables is decomposed as follows depending on the option 
"quadrilinear_decomp" in the option file:

"rAI" (default): as in Ryoo and Sahinidis.

"tri+bi": the multilinear terms is decomposed in as many trilinear terms 
as possible plus (possibly) one bilinear term.

"bi+tri": a first bilinear term and as many trilinear terms as possible.

"hier-bi": consecutive bilinear terms are grouped and reformulated with 
new auxiliaries, which are then grouped in turn (the structure is that of 
a balanced binary tree).

> Are the user defined auxiliary variables considered as original problem 
> variables and hence preprocessed, bound tightened, branched upon like 
> all other variables ?

Yes.

Hope this helps.

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, 28 Mar 2012, Akshay Gupte wrote:

> Hi,
>
> I was just wondering the following: Suppose I formulate a multilinear 
> problem with AMPL where I replace each multilinear term with its 
> auxiliary variable and write explicit constraints for defining these 
> auxiliary variables. Is this likely to affect the performance of Couenne 
> in a significant way - good or bad ?
>
> For example, does this pre-empt any cut generation ? Is it able to 
> detect the original multilinear constraint from the new computational 
> graph and generate the same multi-term (if any) cuts as before ? Are the 
> user defined auxiliary variables considered as original problem 
> variables and hence preprocessed, bound tightened, branched upon like 
> all other variables ?
>
> Thanks,
> Akshay.
>
> Sent from my iPad
> _______________________________________________
> Couenne mailing list
> Couenne at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/couenne