| 摘要 |
Embodiments of the present invention are concerned with methods of reducing domains of variables for use in a resource allocation problem. In particular, embodiments can be used for identifying inconsistencies in problem specifications and identifying the source of such inconsistencies. Embodiments are suitable for use in resource allocation problems, such as planning, scheduling, timetabling, routing, transmitter placement, frequency allocation, and network configuration, among others. The methods firstly involve assigning different consistency degrees to different constraints and secondly involve changing the consistency type of some of the constraints during execution of the problem, and re-starting constraint propagation when an inconsistency has been discovered. This contrasts with existing systems, which hard-wire consistency type to propagation algorithm, and operate in so-called Stop-On-Inconsistency mode, where, if an inconsistency has been detected, the constraint propagation and network updating can only be restarted if one of the constraints responsible for the inconsistency is removed from the problem. With existing systems, identifying which constraint is responsible for the inconsistency is a challenging task, and can involve unnecessary removal of several constraints. In addition to enabling detection of actual causes of the inconsistency (e.g. task unallocated if the others are already allocated), embodiments of the invention lead to a consistent, eventually solved, sub-problem, together with another sub-problem comprising all of the incompatible tasks.
|
