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

[Andrew Makhorin]

-------- Forwarded Message --------
From: Alexey Karakulov <address@hidden>
To: Michael Hennebry <address@hidden>
Cc: Andrew Makhorin <address@hidden>, address@hidden
Subject: Re: [Help-glpk] Objective function defined with max, min.
Date: Fri, 6 Jan 2017 19:46:31 +0200

Andrew & Michael,


Thanks a lot for the advice. I implemented binary variables, for f(x) =
max(x, 0). It seems to give a correct result, but works extremely slower
than LP problem. It takes like 10s for have a few dozen points with
binary variables, and I don't know how long for real problem with
hundreds of points.

On Fri, Jan 6, 2017 at 6:59 AM, Michael Hennebry
<address@hidden> wrote:
        On Thu, 5 Jan 2017, Michael Hennebry wrote:
        
                The objective function includes  crop(s) = median(0, s,
                1)
                where the range of s includes both negative values and
                values > 1 .
                
                The set defined is not convex and so cannot be defined
                purely with
                linear constraints.
                One can get around the need for a binary by using
                optimality.
                
                Add nonnegative auxillary variables p0, n0, p1 and n1.
                s = p0-n0
                s = p1-n1+1
                Adjust the objective to ensure that p0 or n0 is zero
                at optimality and that p1 or n1 is zero at optimality.
        
        Oops.  That does not work.
        There are situations in which the optimality condition is
        useful,
        but your function is neither convex nor concave.
        
        You will need at least one binary.
        
        The convex hull of (s, crop(s) has vertices
        (smin, 0) (0, 0) (smax, 1) (1, 1)
        in that order.
        
        
                0<=crop(s)<=1
                crop(s)<=p0
                crop(s)>=1-n1
        
        -- 
        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