R help - Dec 2011 - Lagged values problem requiring short solution time

Hello,

I am hoping someone can help tackle the problem below, for which I require a
fast solution. It feels like there should be an elegant approach, but I am
drawing blanks.

Take a vector 'x' with random values > 0:

x = runif(10,1,5)

Assume some reasonably small positive value 'delta':

delta = 0.75

The task is to find a solution vector 'y' of same length as 'x'
such that:

The absolute difference between y[i] and y[i-1] is >= 'delta'

and y[i] >= x[i]

and that the sum of y[i] - x[i] be as small as possible -- i.e. minimize
sum(y-x).

The real-world application that (loosely) inspires this problem is the case of
thermal power plants that face limits ('delta') in the speed with which
they can "ramp" output up (or down) in response to changing demand.
The period-to-period difference in output cannot exceed the absolute value of
'delta'. The other constraints I've imposed are specific to my
application, but also provide a more neatly defined problem. A real-world
problem would not have random starting values for 'x', but I figure the
random values will present a particular difficulty in terms of solution time.

SPEED IS CRITICAL here, as this example must handle 'x' with
length=10,000 in practice and is located within an optimization routine that
requires it be iterated over different 'x' vectors many times. My
Neanderthal-ish solution (below) may or may not give the theoretically optimal
solution, but, regardless, is too slow when 'x' becomes lengthy due to
its reliance on loops.

Hope you can help!

x = runif(10,1,5)
delta = 0.75

chg = diff(c(x,x[1]))
y = x
	
while (any(abs(chg)>delta)) {
	
	temp = sign(chg)*chg - delta
	
	temp1=temp
	temp1[chg>=(-delta)] = 0
	temp1 = c(temp1[length(temp1)],temp1[-length(temp1)])
	
	temp2 = temp
	temp2[chg<=delta] = 0
	
	y = y+temp1+temp2

	chg = diff(c(y,y[1]))
		
	}

#Solution vector:
y

Thank you,
Kevin

Kevin Ummel
CARMA Project Manager
Center for Global Development



	[[alternative HTML version deleted]]

Kevin,

Your problem seems to have three restrictions: (1) abs(x[i] - x[i-1]) >delta
(2) y[i] >= x[i]
and (3) minimize sum(y-x). If this is the case I believe I have a better
solution, with a smaller sum
and in much less time.
The problem is restriction (2). If the diffs are negative you can't subtract
negative,
 the new y[i] would be less than x[i]. So, add. Here is the code:

fun1 <- your code

fun2 <- function(x, delta){
	n <- length(x)                                             # don't need
to
create a work y
	if(abs(x[1] - x[n]) < delta) x[1] <- x[n] + delta # special case, wraps
around.
	ix <- which(abs(x[2:n] - x[2:n - 1]) < delta)     # make up an index
vector
	x[ix] <- x[ix - 1] + delta                                # and use it. 
	x
}

# First test both

x = runif(10,1,5)
y1 <- fun1(x, delta=0.75); s1 <- sum(y1 - x)
y2 <- fun2(x, delta=0.75); s2 <- sum(y2 - x)
# and display results
rbind(fun1=c(y=y1, s=s1), c(diff(c(y1,y1[1])), NA),
	fun2=c(y=y2, s=s2), c(diff(c(y2,y2[1])), NA),
	x=c(x, NA), c(diff(c(x,x[1])), NA))

# now time them!
x <- runif(10^5, 1, 5)
t1 <- system.time(for(i in 1:10^2) y1 <- fun1(x, delta=0.75))[c(1, 3)]
t2 <- system.time(for(i in 1:10^2) y2 <- fun2(x, delta=0.75))[c(1, 3)]
rbind(fun1=t1, fun2=t2, ratio=t1/t2)
#
# Sample run
#
      user.self  elapsed
fun1   26.99000 29.60000
fun2    0.92000  1.09000
ratio  29.33696 27.15596

29 times faster!

I hope it's usefull

Rui Barradas


--
View this message in context:
http://r.789695.n4.nabble.com/Lagged-values-problem-requiring-short-solution-time-tp4184566p4186786.html
Sent from the R help mailing list archive at Nabble.com.