Title

Modeling and Solving a Resource Allocation Problem with Soft Constraint Techniques

Authors

Weixiong Zhang, Washington University in St. LouisFollow

Document Type

Technical Report

Publication Date

2002-05-23

Filename

wucse-2002-13.pdf

DOI:

10.7936/K7668BH2

Technical Report Number

WUCSE-2002-13

Abstract

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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7668BH2

Recommended Citation

Zhang, Weixiong, "Modeling and Solving a Resource Allocation Problem with Soft Constraint Techniques" Report Number: WUCSE-2002-13 (2002). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/1131