[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] [Fwd: Re: Objective function defined with max, min.]
From: |
Andrew Makhorin |
Subject: |
[Help-glpk] [Fwd: Re: Objective function defined with max, min.] |
Date: |
Fri, 06 Jan 2017 21:30:56 +0300 |
-------- 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