[Couenne] Multilinear model formulations

[Pietro Belotti]

Akshay,

> For a product written as x1*(\sum_i y_i), I guess there is only one 
> auxiliary created. or is the sum disaggregated ?

There are two auxiliaries:

w = \sum_i y_i
z = x1*w

The sum would be disaggregated only if expressed as \sum_i (x1 * y_i) 
(i.e., Couenne does not factor x1 if expressed this way).

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

> 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