Re: [Help-glpk] Objective function defined with max, min.
> 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, Did you try using cutting planes? --mir and --gomory may help (a bit). > and I don't know how long for real problem with hundreds of points. ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Objective function defined with max, min.
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
Re: [Help-glpk] Objective function defined with max, min.
> 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. Yes, it doesn't work in case of maximization. You may try using the "standard big M" approach, for example, as follows. Let z1 = 1, z2 = 0, z3 = 0: -M1 <= x1 <= 0, 0 <= x2 <= 0, 0 <= x3 <= 0 z1 = 0, z2 = 1, z3 = 0: 0 <= x1 <= 0, 0 <= x2 <= 1, 0 <= x3 <= 0 z1 = 0, z2 = 0, z3 = 1: 0 <= x1 <= 0, 0 <= x2 <= 0, 1 <= x3 <= +M3 Then f(x) = min(0, max(1, x)) can be described by the following linear constraints: f = x2 + z3 x = x1 + x2 + x3 -M1 * z1 <= x1 <= 0 0 <= x2 <= z2 z3 <= x3 <= +M3 * z3 z1 + z2 + z3 = 1 where x1, x2, x3 are auxiliary continuous vars, z1, z2, z3 are auxiliary binary vars, M1, M3 are "big M" constants. Note that some auxiliary variables can be eliminated due to equality constraints. ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Objective function defined with max, min.
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
Re: [Help-glpk] Objective function defined with max, min.
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
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
