What is a constraint?

A constraint is a condition of an optimization problem that the solution must satisfy. The set of candidate solutions that satisfy all constraints is called the feasible set. The nurse scheduling problem consists of many constraints. It is necessary to meet all Constraints to get a feasible solution. In other words, if a AND set of the constraints becomes to be an empty set, then there is no solution. It is easy if the Constraints are two or three to use a Venn diagram, but note the number of Constraints is hundreds of thousands in the nurse scheduling problem if we look into it in detail.

rep2 rep2

This situation is similar to piling up the building blocks of Constraint so that they do not fall over.


When we have piled all the building blocks up, the solution exists, but if it falls over, there is no solution due to an empty set in the middle. rep2