Re: [Help-glpk] [Fwd: Re: Objective function defined with max, min.]
On Fri, 6 Jan 2017, Andrew Makhorin wrote: Forwarded Message From: Alexey Karakulov To: Michael Hennebry Cc: Andrew Makhorin , help-glpk@gnu.org 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. How? Details matter. If you used a big-M method, how did you choose M? -- 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
[Help-glpk] [Fwd: Re: Objective function defined with max, min.]
Forwarded Message From: Alexey Karakulov To: Michael Hennebry Cc: Andrew Makhorin , help-glpk@gnu.org 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 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 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
[Help-glpk] [Fwd: Re: Objective function defined with max, min.]
Forwarded Message From: Alexey Karakulov To: Michael Hennebry Cc: Andrew Makhorin , help-glpk@gnu.org Subject: Re: [Help-glpk] Objective function defined with max, min. Date: Fri, 6 Jan 2017 00:09:00 +0200 Michael, thanks. This seems to work for me, but it's only for maximizing "crop(s)", not minimizing, right? I have "crop(s[i])" with both positive and negative signs for different "i", so I should do some fiddling to get it working. On Thu, Jan 5, 2017 at 8:39 PM, 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. 0<=crop(s)<=1 crop(s)<=p0 crop(s)>=1-n1 -- 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
[Help-glpk] [Fwd: Re: Objective function defined with max, min.]
Forwarded Message
From: Alexey Karakulov
To: Andrew Makhorin
Cc: help-glpk@gnu.org
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 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/msg5.html
> >
>
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk
