[Fwd: Re: Objective function defined with max, min.]

-------- Forwarded Message --------
From: Alexey Karakulov <[email protected]>
To: Andrew Makhorin <[email protected]>
Cc: [email protected]
Subject: Re: Objective function defined with max, min.
Date: Thu, 5 Jan 2017 20:46:43 +0200

        f(x) = 0, if x <  0
             = x, if x >= 0
         
        
        The latter equality can be modeled thru the following
        linear constraints:
        x = x1 - x2
        f = x1
        x1, x2 >= 0


Simplified:


> f = x + z
> f, z >= 0



It should work for minimization, but I want to maximize expression with
f(x) as a summand. So adding Z should make the solution unbounded.


Note that in my problem X is dependent variable. If it was independent,
I could just write "x" instead of "f(x)".


Basically, I want to maximize convex piece-wise linear function f(x).
Probably I'll have to use binary variables as described in the second
case
here: http://orinanobworld.blogspot.com.cy/2010/10/piecewise-linear-functions-in-math.html


On Thu, Jan 5, 2017 at 12:52 AM, Andrew Makhorin <[email protected]> wrote:
        On Thu, 2017-01-05 at 01:50 +0300, Andrew Makhorin wrote:
        > On Wed, 2017-01-04 at 23:43 +0200, Alexey Karakulov wrote:
        > > Hi, I have this kind of function in the objective:
        > >
        > > > crop(s) = max(0, min(1, s))
        > >
        > >
        > > I wonder if it's possible (and how) to reformulate the task
        to be LP
        > > problem. I have read this posting [1], but I'm not sure how
        to apply
        > > it.
        >
        >
        > Note that
        >
        > crop(x) = f(x) - f(x-1)
        >
        > where
        >
        > f(x) = 0, if x <  0
        >      = x, if x >= 0
        >
        > The latter equality can be modeled thru the following linear
        > constraints:
        >
        > x = x1 + x2
        
        Must read
        
        x = x1 - x2
        
        
        > f = x1
        > x1, x2 >= 0
        >
        > where x1, x2 are auxiliary variables.
        >
        > f(x-1) can be modeled in the same way by taking y = x-1.
        >
        > (Check all this carefully for errors.)
        >
        > >
        > >
        > > > param maxN default 1000;
        > > > param maxJ default 10;
        > > > set N := 1 .. maxN;
        > > > set J := 1 .. maxJ;
        > > > param a{N};
        > > > param w{N};
        > > > var X0;
        > > > var X{J};
        > > > var S{maxJ .. maxN};
        > >
        > >
        > > > maximize Obj: sum {n in N} w[n] * crop(S[n])
        > >
        > > > subject to DefineS {n in maxJ .. maxN}: S[n] = X0 + sum {j
        in J}
        > > a[n-j+1] * X[j]
        > >
        > >
        > > [1]:
        http://lists.gnu.org/archive/html/help-glpk/2007-06/msg00005.html
        > >
        >