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 henne...@web.cs.ndsu.nodak.edu
"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
_______________________________________________
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk
