Re: [Help-glpk] Linear expressions in the integrands of iteratedexpressions

[Andrew Makhorin]

> On Sunday 22 October 2006 20:54, you wrote:
>> Can you replace
>> 
>>   s.t. blrMax:max{i in I, j in J} x[i,j] = 1;
>> 
>> with just putting an upper bound "x[i,j] <= 1" where you define the
>> variable?
> 
> That's a very good suggestion, but it doesn't quite handle 
> what I'm trying to do.  I'm trying to code up
> exclusivity without having to use "binary", e.g. 
> 
>     s.t. foo:sum{i in I} x[i] = 42;
>     s.t. bar:max{i in I} x[i] = 42;
> 
> should ensure that there is one and only one "42" in x[i],
> with everything else being zero (assuming all x[i]>=0, of
> course).  
> 
> This can certainly be done more elegantly in an ILP than 
> an LP, and I don't know if an LP still scales better when 
> given these kind of constraints.  So I'll be coding up 
> one of each flavor and testing.
> 
>> "max" isn't a linear operator.
> 
> Here's what I've been doing using the C interface to glpk:
> 
>    given variables x>=0, y>=0, and z, z=max(x,y) looks like
> 
>    -x + z >= 0
>    -y + z >= 0
>    (indirectly) minimize z
> 
> I thought that "max" would have similar functionality.  If
> that's not the case because it isn't a linear operator, then
> I'll need back up a bit and try a different approach.
> 
> So, is "max" not intended for what I'm trying to do?  Did I
> get a little too giddy at the thought of abandoning my large
> pieces of graph paper for a high-level language?

The builtin max operator being non-linear can be applied to
expressions containing only parameters, not variables. Otherwise
your model would be non-linear (even essentially non-linear, i.e.
non-smooth) and therefore not suitable for solving with glpk.

However, that does not mean that you cannot model non-linearities.
In principle, using piecewise linear functions (which max is) you
can model constraints practically of any kind. And if the feasible
region as well as the objective function are known to be convex,
you can solve the problem as a pure lp. Otherwise you can use binary
variables that leads to mip.

There are no "standard" ways in which the original non-linear problem
could be automatically "translated" to lp or mip, so the user himself
has to do that in any particular case.