A general approach to using problem instance data for model refinement in constraint satisfaction problems

The initial formulation, or model, of a problem greatly influences the efficiency of the problem-solving process. Hence, modeling is critical in determining the performance of the problem-solving process and the quality of the produced solution. Unfortunately, modeling remains an art and has resisted automation. Additionally, slight variations in the characteristics of a given problem instance make it difficult to represent one class of problems using a unique model. Consequently, a robust approach to modeling is required.;My thesis presents an automated approach to modeling. I exploit information contained in the input data in order to customize the constraint model of a given problem instance. I apply my approach to the area of Constraint Programming, focusing on a class of problems where a solution is guaranteed to exist for all problem instances. Specifically, I enhance a generic constraint model of a Constraint Satisfaction Problem (CSP) by adding new constraints to this model. These additional constraints are selected from a library of constraints by testing features of the problem instance at hand. The resulting constraint model is customized such that it best represents the problem instance given the data provided as input.;The resulting framework is applicable to problems where instances are seeded with some initial input data. The techniques present in the framework are generally defined so they can be applied across domains. They cope with the uncertainty in the model refinement process by handling noisy data and incorrect inferences, generating additional information as needed. Furthermore, the framework uses Support Vector Machines (SVMs) to determine the scope of the inferred constraints and it automatically instantiates the constraint model in a format supported by a specialized constraint solver.;I evaluate the effectiveness of my approach in two domains, Sudoku puzzles and the building identification (BID) problem. I show how it can infer the most specific constraint model given the available public information, scale to large problem instances, and use a SVM model to efficiently determine constraint scopes. I also evaluate the effectiveness of the framework for the BID problem in areas such as New Orleans and Belgrade where non-homogenous problem structures co-exist and across different Sudoku puzzle variations, demonstrating the resulting improvement when using an inferred model over a generic one. Additionally, I evaluate the framework's ability to augment the initial set of data points with new ones when applying an iterative constraint-propagation algorithm, which leads to more accurate constraint models.