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]]

