SAS Optimization, and SAS Simulation Studio

turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

Find a Community

Topic Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-16-2017 12:35 AM

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.

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to grandmoon

10-16-2017 11:10 AM

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;

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to grandmoon

10-16-2017 02:05 PM

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.

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to RobPratt

10-17-2017 02:12 AM

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.

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to grandmoon

10-17-2017 10:56 AM - edited 10-19-2017 11:47 AM

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.

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to RobPratt

10-21-2017 07:53 AM

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,

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to grandmoon

10-21-2017 09:39 AM

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.