Modeling and Solving a Resource Allocation Problem with Soft Constraint Techniques

We study a resource allocation problem, which is a central piece of a real-world crew scheduling problem. We first formulate the problem as a hybrid soft constraint satisfaction and optimization problem and show that its worst-case complexity is NP-complete. We then propose and study a set of decision and optimization modeling schemes for the problem. We consider the expressiveness of these modeling schemes for the problem. We consider the expressiveness of these modeling methods. Specifically, we experimentally investigate how these modeling schemes interplay with the best existing systematic search and local search methods. Our experimental results show that soft constraint techniques can be effective on large resource allocation problem instances, and an optimization approach is more efficient than a model checking approach based on decision models