Abstract
In this research, we deal with a specialization of the general software automation problem. We develop a classification-based method called MENDER for the synthesis of patchers" that satisfy resource assignment problems (RAPs). We define RAPs as special subclasses of constraint satisfaction problems (CSPs). A RAP is a problem of establishing a certain type of relationship (e.g., one-to-one, or many-to-one) between a set of consumers" and a set of resources". Solving a RAP involves choosing parameter values such that consumers relate to resources as prescribed. Patchers conduct local search through a space of fully instantiated structures. RAPs tend to be high-arity constraints which constrain global aspects of the target structure. Our own experiments, as well as evidence in the recent literature, have shown that RAPs can be satisfied more efficiently by patching than by methods based on sequential parameter-value instantiation. The classification-based method to design patchers for RAPs has four phases: (1) classification of the problem as a RAP, (2) retrieval of a patcher schema", (3) instantiation of the schema with information derived from the constraint, and (4) optimization of the patcher. Optimization is accomplished through a technique known as polarity analysis (PA). The results of PA can reduce the cost of the patcher's operator selection step by allowing it to focus on promising" operators. Our implementation of MENDER has synthesized patchers for RAPs in the domains of 2D-floorplanning, timetable design, and the n-queens problem. Empirical studies of the run-time performances of these patchers compared to the performances of generators yielded results that favored patching. Our results were predominantly statistically significant.