Algorithm for Power Plant CSP

Question

Design a solution for the given constraint satisfaction problem.  Solution should explain the variables, the domain values, the constraints, the heuristics, and how the constraint propagation would work.

In a country, there are 15 power plants.  They produce different amount of power, that is given by the array P[i].   The total power produced must equal at least X (for example 1000), but should not exceed 1500 to maintain a decent price.  For adequate workforce planning and employment reasons, at least one of the power plant near each city must operate each day.

Partial example..

Power Plant, i	P[i]	Associated Cities
P1	200	C1,C2
P2	200	C2, C3
P3	180	C2, C4, C6
P4	210	C5,C6
……	…..	……….
i-th power plant	P[i]	List of cities

Answer 1

As indicated in the problem, we have 3 main notions to consider, power plants, produced energy, and relevant cities. Power plants can simply be accepted as variables in CSP where relevant cities become available domains for each variable. Produced energy becomes related to the lower bound and upper bound limits(1000 and 1500 respectively). It is also said that each city must have at least 1 power plant around, so this is another constraint to be considered.

While reading the domains, we should count how many times a city appears in the domains. If a city appears only in a single domain, a related power plant station is a necessary one. Therefore, the power plants can be separated into necessary and optional ones. This notion will be very handy for further propagation.

First, node consistency can be used, eliminate those variables, which have produced energy over 1500. So, basically, they fail the unary constraint and if there is a city that only related to that power plant, that means there is no solution to the problem because it fails the constraint that each city must have at least 1 power station.

Secondly, we can have path consistency applied to check whether, really, there is a path that can take us to the solution. It should be checked that the produced power summation of all power plant stations is not less than 1000 and the produced power summation of necessary plant stations where a unique city-related(this city only appears on this domain) is not over 1500. If these ones fail that means there is no solution to the problem.

After the consistency check, the backtracking search can start. We can use a heuristic to weigh the necessity of the power plant station. The weight of the variable is dependent on the number of the unique cities it has in the domain, for example, let's say we have 2 power stations 1 and 2 unique cities in the domain respectively. The first one will have 10**1 + # of remaining domain size(domain size - 1) and the second one will have 10**2 + # of remaining domain size(domain size - 2). Once we choose the variable, the domain values will be eliminated from the remaining variables' domains. If any variable remains with 0 domain, we store them in a list called optionals. They might be required if the power produced was not enough with the necessary ones.

Comments

I like the concepts presented.  However, I am not sure about the domain values.  For example, if a power plant is next to 2 cities, then what would the domain value be of that power plant variable?

Instead, I propose that the domain should just be {0,1}.  If it is on, set to 1, and set to 0 otherwise. Then, the constraints can be formed for each city: sum of variables should be at least 1.