Michel Medema

Solving constraint satisfaction problems often involves a large amount of redundant exploration stemming from the existence of subproblems whose information can be reused for other subproblems. Subproblem dominance is a general notion of reusability that arises when one subproblem imposes more constraints on the remaining part of the search than another subproblem and allows the search to reuse the solutions of the dominating subproblem for the dominated subproblem. The search can exploit subproblem dominance by storing the subproblems that have been explored in a cache and abandoning the current subproblem whenever the cache contains a subproblem that dominates it. While using caching makes it possible to solve problems where subproblem dominance arises orders of magnitude faster, storing all of these subproblems can require a substantial amount of memory, making it impractical in many cases. This paper analyses the dominance between different subproblems for various constraint problems, revealing that only a relatively small number of subproblems dominate other subproblems. Based on these findings, two types of strategies are proposed for reducing the number of subproblems stored in the cache: limiting the number of subproblems that can be stored in the cache and periodically cleaning up the cache. An experimental evaluation demonstrates that these strategies provide an effective instrument for reducing the memory consumption of caching, allowing it to be used on a larger scale. However, there is a trade-off between saving memory and reducing redundant exploration, as removing subproblems from the cache may prevent dominance from being detected for certain subproblems.

A constraint satisfaction problem (CSP) is, in its most general form, an NP-complete problem. One of the several classes of tractable problems that exist contains all the problems with a restricted structure of the constraint scopes. This paper studies community structure, a particular type of restricted structure underpinning a class of tractable SAT problems with potentially similar relevance to CSPs. Using the modularity, it explores the community structure of a wide variety of problems with both academic and industrial relevance. Its impact on the search times of several general solvers, as well as one that uses tree-decomposition, is also analysed to determine whether constraint solvers exploit this type of structure. Nearly all CSP instances have a strong community structure, and those belonging to the same class have comparable modularity values. For the general solvers, strong correlations between the community structure and the search times are not apparent. A more definite correlation exists between the modularity and the search times of the tree-decomposition, suggesting that it might, in part, be able to take advantage of the community structure. However, combined with the relatively strong correlation between the modularity and the tree-width, it could also indicate a similarity between these two measures.

By virtue of the steady societal shift to the use of smart technologies built on the increasingly popular smart grid framework, we have noticed an increase in the need to analyze household electricity consumption at the individual level. In order to work efficiently, these technologies rely on load forecasting to optimize operations that are related to energy consumption (such as household appliance scheduling). This paper proposes a novel load forecasting method that utilizes a clustering step prior to the forecasting step to group together days that exhibit similar energy consumption patterns. Following that, we attempt to classify new days into pre-generated clusters by making use of the available context information (day of the week, month, predicted weather). Finally, using available historical data (with regard to energy consumption) alongside meteorological and temporal variables, we train a CNN-LSTM model on a per-cluster basis that specializes in forecasting based on the energy profiles present within each cluster. This method leads to improvements in forecasting performance (upwards of a 10% increase in mean absolute percentage error scores) and provides us with the added benefit of being able to easily highlight and extract information that allows us to identify which external variables have an effect on the energy consumption of any individual household.