Reservoir-like constraint which empties at varying capacities

[Daniel Rogers]

====== PROBLEM BACKGROUND ========

I'm optimizing an event schedule. One event is a sensor-reading, which takes a fixed amount of time to perform. There is a certain window of opportunity to perform each reading (window_of_opportunity > time_to_perform). The overall porgram input is a list of all possible sensor-reading windows, which overlap preventing me from simply performing all the readings.

The readings are a fixed data size, but there is a memory limit. The other type of event to schedule is a memory-clear, which can be performed at any time, but also takes a fixed amount of time to complete (so while clearing the memory, I will miss the opportunity to perform sensor-readings available at that time).

Provided the input list of reading opportunities, the scheduler should find the best combination of sensor-read and memory-clear events which maximizes the number of sensor-reads.

I successfully modeled/optimized choosing the best sensor-reads to perform given an overlapping list of opportunity windows, but I'm stuck on incorporating the memory constraint.

====== CURRENT EFFORT/ATTEMPT ========

I am trying to use the ReservoirConstraint[WithActives], where the reservoir is analogous to the memory. But I see no way to arbitrarily empty the reservoir. It might be optimal to empty from 70% capacity at some particular time t_x, while later on at time t_y it will be optimal to empty from 90% capacity. So, I can't declare the emptying events in advance as required by the ReservoirConstraint's "demands" argument.

I thought to just empty the entire memory capacity for each emptying event, but of course if the capacity is 100, and it's filled to only 90, an emptying event would result in a final value of -10 (90 - 100), which would violate the ReservoirConstraint's min_level (0, in my case, representing empty memory).

====== QUESTION ========

Is the ReservoirConstraint the right approach for a problem like this? If so, how do I empty the reservoir arbitrarily? If not, what other constraints would encapsulate this type of functionality?

[blind.lin...@gmail.com]

Interesting question, and I'm afraid my response won't be that helpful, but in the routing solver, there is the concept of slack to address this sort of thing. Perhaps implement something similar...an intvar with a range from 0 to max-memory?? With a constraint that memory state + memory slack = max memory.

But scanning very quickly the reservoir constraint code, it seems it needs an int64, not an IntVar.

(Mostly I'm replying to bump this question and so that I pay attention to future responses to this question)

James

-- You received this message because you are subscribed to the Google Groups "or-tools-discuss" group. To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/030f2267-19cf-4976-9ba5-897610fc2c9dn%40googlegroups.com.

--
James E. Marca
Activimetrics LLC

[Laurent Perron]

The reservoir is fully expanded into

for all events i, sum( j_before_i * level_change(j)) in [min_level..max_level], with j_before_i <=> time(j) <= time_i

it would be possible to recreate this and add custom empty event, such that at a given time, sum(j_before_i* level_change(i)) +  empty_demand == 0

The only tricky parts would be (a) multiple events and (b) non fixed_time events.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/YpDxYBA6MsIV1UeF%40055559173be0.

--

--Laurent

[Daniel Rogers]

Hi Laurent, I have a simple example below using the reservoir constraint. Do you have the Python constraints/code that would replace the "AddReservoirConstraintWithActive" line? I'm trying to understand how to implement the reservoir constraints expansion. Once I have the constraints, I should then be able to work backwards and create the custom empty event like you mentioned.

```

from ortools.sat.python import cp_model

model = cp_model.CpModel()

start_bool = model.NewBoolVar("x0")
empty_bool1 = model.NewBoolVar("x1")
fill_bool1 = model.NewBoolVar("x2")
empty_bool2 = model.NewBoolVar("x3")

start = model.NewIntVar(0, 0, "start")
empty_time1 = model.NewIntVar(2, 2, "fill_time2")
fill_time1 = model.NewIntVar(8, 8, "fill_time1",)
empty_time2 = model.NewIntVar(12, 12, "empty_time2")

times = [start, empty_time1, fill_time1, empty_time2]
demands = [17, -1, 20, -2]
actives = [start_bool, empty_bool1, fill_bool1, empty_bool2]

model.AddReservoirConstraintWithActive(times, demands, actives, 0, 20) # <<< LINE TO REPLACE >>>>

model.Maximize(sum(d*a for d,a in zip(demands,actives))) # maximize the final resorvoir value

model.Add(empty_bool1 + empty_bool2 >= 1) # at least one empty must be chosen

solver = cp_model.CpSolver()
solver.Solve(model)
print(solver.ResponseStats())
print(solver.Value(start_bool), solver.Value(fill_2_bool), solver.Value(fill_8_bool), solver.Value(empty_12_bool))

```

[Laurent Perron]

No python code, C++ -> https://github.com/google/or-tools/blob/stable/ortools/sat/cp_model_expand.cc#L46

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/cced9d38-862b-4ef5-a68e-2f21fc446a00n%40googlegroups.com.

[Daniel Rogers]

For anyone following this problem, I came up with a solution. Since all of the sensor_reads would increase the reservoir by the same amount 'w', I know the clear_memory events will reduce the reservoir by some multiple of 'w'. For example, if sensor_reads increase reservoir by 10, I would only ever need to "empty" by 10,20,30,etc. I decided I don't want more than 5 sensor reads in a row (reservoir capacity of 50), so my biggest memory_clear event should be 50.

I don't know in advance which sensor_reads will have a memory_clear afterwards or, even what the current reservoir level will be when that memory_clear happens (THIS IS THE WHOLE ISSUE I WAS HAVING). So, for each possible sensor_read, I create 5 clear_memory IntervalVars with associated demands -10,-20,-30,-40, and -50. Each one will have its own boolean/active, so the solver will have the option of choosing the best one or none. With my objective function penalizing the # of clear_memory events, the solver seems to choose to reduce by the larger amounts (40 or 50), but it does not always choose a full memory clear. I believe I can further modify my objective function more to make the 50/full-clear more common.

This solution isn't great, because the complexity grows exponentially; the 5 clear_memory IntervalVars per sensor_read opportunity increases the variable count by at least 5*n, where 'n' is the total number of sensor_read opportunities. With relatively small inputs, I'm running into my solver time limits on finding optimal solutions now.

Would be interested to hear anyone else's approach to this problem.