Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

This thesis presents HASSLE-GEN, a novel genetic algorithm aimed at learning weighted partial MAX-SAT models from labeled contextual examples. This problem involves jointly learning Boolean hard and soft constraints—as well as appropriate weights for the latter—from known solutions and non-solutions. The inclusion of contexts in the example set allows for learning from situational information. For instance, an example that is labeled as a solution and that comes with a particular context is possibly not a solution outside of that context. In this work, several blind and heuristic genetic operators are developed and empirically compared. The final algorithm is equipped with heuristic operators, as they are shown to realize superior performance. The algorithm also employs the deterministic crowding scheme, allowing it to learn high-quality models while maintaining a diverse population, which in turn results in better overall performance. In the experimental evaluation, HASSLE-GEN is shown to outperform the best existing approach, HASSLE-SLS, in various ways. Firstly, the novel method is able to learn high-quality models much faster than its competitor. It also learns good models more consistently (over different runs) than the existing method. Finally, it is able to simultaneously learn several distinct-looking high-quality models. This allows the user to select the model that fits best to their potential needs and preferences that are not captured in the set of examples. A second contribution made in this thesis is the development of a novel MAX-SAT model evaluation procedure. By making use of knowledge compilation techniques, a considerable speed-up in model evaluation is realized for small to medium-sized models. This is a significant result, as the evaluation of candidate models was a large bottleneck in the existing learning approach. The knowledge-compilation-based evaluation procedure can be employed regardless of what search algorithm is used. It has been implemented for both the existing and the new search approach.

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Combinatorial optimization plays a critical role in solving many real-life problems, where accurately modeling the problem is essential but often challenging. This challenge has introduced an interest in learning models from data. Existing approaches have explored learning integer linear programs (ILPs) from data, particularly from contextual data, to automate and refine this modeling process. However, these methods often show limited performance, especially in complex scenarios where distinguishing between different types of outcomes, such as suboptimal and infeasible solutions, could offer significant advantages. This thesis hypothesizes that introducing a third label to differentiate suboptimal examples from infeasible ones can enhance the learning process. To explore this, we evaluate the impact of this third label on learning constraints and cost vectors in ILPs, and investigate in what way to alter existing learning approaches to best operate in this new three-label setting. To this end, we perform a series of experiments involving various algorithms, including MISSLE variants, IncaLP, the structured perceptron, and cutting plane methods. Our research demonstrates that separating the learning tasks for constraints and cost vectors, enabled by the introduction of the suboptimal label, leads to more effective algorithmic performance. Specifically, in constraint learning, the MISSLE "constraint only" V1 variant and IncaLP showed improved results by focusing on feasibility, while the structured perceptron proved robust in minimizing regret during cost vector learning, even with imperfect constraints. Conversely, the cutting plane method, though effective under ideal conditions, struggled with imperfect constraints, often yielding trivial solutions. This study underscores the potential benefits of incorporating a third label in ILP learning and provides practical insights into algorithm selection and tuning, particularly when accurately representing constraints and cost vectors is critical in optimization problems.