[Couenne] Multilinear model formulations

[Akshay Gupte]

Hi Pietro,

Thanks for your input. It surely helps a lot. I have one more question: For a product written as x1*(\sum_i y_i), I guess there is only one auxiliary created. or is the sum disaggregated ?

Akshay. 

Sent from my iPad

On Mar 28, 2012, at 3:42 PM, Pietro Belotti <pbelott at clemson.edu> wrote:

> 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
>