Re: [Help-glpk] Non linear constraint

[Michael Hennebry]

On Sun, 8 Nov 2015, esma mehiaoui wrote:

> I just need to be sure that the no linear following constraint cannot be 
> expressed in a MIP program or linearised.
>
> Prod{i in 1..4} sum {j in 1..5} V[i,j] * C[i] * R[i]
>
> Ps: V is a boolean variable
>      C is a boolean parameter
>      R is a real parameter

I'm taking this to mean can
P = Prod{i in 1..4} sum {j in 1..5} V[i,j] * C[i] * R[i]
be linearized.

Expanding the product one gets a sum of up to 5**4=625
products of boolean variables times real parameters.
An auxillary boolean for each product will give you a linearization.

The continuous relaxations of linearizations tend to be rather loose.
I expect that the one above will be more loose than most.
Getting the convex hull might involve 2**20 constraints or variables,
so I expect that that is out of the question.

A common technique is to start with a set of constraints
that is mathematically sufficient and add additional
constaints (cutting planes) during solution.
The separation problem between(P, V) and
conv{ (p, v) : p = Prod ... } is solvable,
but might involve solving a sequence of rather large LPs.
What one might do instead is to take the gradient of P with respect to V.
Test whether g . V - P is in range.
Starting from scratch, that could require around 4*5*2**20 operations.

--
Michael   address@hidden
"Sorry but your password must contain an uppercase letter, a number,
a haiku, a gang sign, a heiroglyph, and the blood of a virgin."
                                                             --  someeecards