Putting dynamical constraints on variables

[grandmoon]

Hi all,

The problem is like this: we are given a network of water distribution network, and we have to work out a 24-hour schedule for it, so that the energy cost of pumps can be minimized. There are two pump stations, each one with 3 pumps; every pumping flow per hour for every pump is a constant when it's turned on. We came up with six binary vectors to describe their open-close status during 24 hours.

Now there are extensive requirements for the problem: if a pump is turned on, it has to stay pumping for at least two hours. How to formulate this requirement as constraints on the binary vectors? We want to keep the problem linear and binary, so that SAS can still solve the problem. 

The answer to this question will inspire us to model other parts of the project. For example, the water source inputs water to a water tank; it can't be turned off, and its flow rate can only change every 4 hours; the valves must keep open for at least 4 hours if it is turned on. I think these problems have similar answers, but I just don't know how to do it.

Thanks.

[lipury]

Using "solve with CLP" with the OPTMODEL procedure, for all times t in [2,24], and for each pump p:

4 * p_(t-2) + 2 * p_(t-1) + p_t NE 2;

[RobPratt]

The general approach to exclude a specific pattern of values to binary variables is to use a "no good" linear constraint of the form

sum {i in N0} (1 - x[i]) + sum {i in N1} x[i] <= |N0| + |N1| - 1,

where Nk is the set of variables that take value k in the forbidden pattern.  The idea is that setting x[i] = 0 for all i in N0 and x[i] = 1 for all i in N1 yields a left-hand side of |N0| + |N1|, which exceeds the right-hand side and hence violates the constraint.  Any other assignment of values satisfies the constraint, as desired.

For your first case, you want to exclude the pattern (0,1,0), where the binary variable is 1 if the pump is on and 0 if it is off.  The resulting constraint is (1 - x[t]) + x[t+1] + (1 - x[t+2]) <= 2, which simplifies to x[t+1] <= x[t] + x[t+2].  If you want to handle the beginning of the time horizon separately, you can exclude (1,0) at the beginning with x[1] + (1 - x[2]) <= 1, or more simply x[1] <= x[2].

The second case is similar.  You want to exclude the three patterns (0,1,0), (0,1,1,0), and (0,1,1,1,0), which you can do with three sets of constraints.  The (0,1,0) case is above, you can exclude (0,1,1,0) with (1 - x[t]) + x[t+1] + x[t+2] +(1 - x[t+3]) <= 3, and you can exclude (0,1,1,1,0) with (1 - x[t]) + x[t+1] + x[t+2] + x[t+3] +(1 - x[t+4]) <= 4.

[grandmoon]

Hi Rob,

Thank you so much! Following your hints we are now thinking about the question of water source flow change. Water source can't be shut down, and its flow rate can only change every 4 hours (at least). We tried to set a binary vector reflecting change in water flow from the previous hour: 1 means change, and 0 means no change (The first element is fixed to be 0). We will have to exclude the patterns (1,1), (1,0,1) and (1,0,0,1), which is doable. The tricky part is to transform this into linear constraints on water flow rate in every hour, which is one of the real decision variables in our optimization problem. How can we do that? Could you give us some hint?

Thanks.

[RobPratt]

To enforce at most one change per four consecutive hours, you can use a clique constraint:

sum {i in t..t+3} y[i] <= 1

That is simpler than excluding several sets of patterns.

To link the continuous variables to the binary variables, you can use big-M constraints.  Let w[t] be the water flow rate at time t.  You want to enforce the following logical implication: if w[t] ne w[t-1] then y[t] = 1.  Equivalently, the contrapositive is: if y[t] = 0 then w[t] = w[t-1].  You can accomplish this with two constraints, where M1 and M2 are constants:

• w[t] - w[t-1] <= M1*y[t]
• w[t-1] - w[t] <= M2*y[t]

If w[t] > w[t-1] then the first constraint forces y[t] = 1; if w[t-1] > w[t] then the second constraint forces y[t] = 1.  Equivalently, y[t] = 0 implies both w[t] <= w[t-1] and w[t-1] <= w[t], hence w[t] = w[t-1].

A best practice is to make big-M as small as you can without overconstraining the problem.  Here, you want the constraints to be redundant when y[t] = 1.  So take M1 = w[t].ub - w[t-1].lb and M2 = w[t-1].ub - w[t].lb.  Be sure to impose realistic bounds on w.  Arbitrarily large values will lead to numerical trouble.

[grandmoon]

Hi Rob,

Thanks for your wonderful explanation. I still have a puzzle about it though: so we now know that when y[t]=0, w[t]=w[t-1], but if w[t]=w[t-1] we can't get y[t]=0? Also, If the condition is y[t]=1, then -M2<=w[t]-w[t-1]<=M1, which means they are most of the time different but still can be equal? 

 Thanks,

[RobPratt]

The logical implication is only one direction. If you want to enforce the converse statement that y[t] = 1 implies w[t] ne w[t-1], you need to first decide how different is enough to be considered not equal. You also need to decide whether it is important for the model to enforce it during the solve or whether you can just post process to set y appropriately based on w after the solver call.