A Conflict-Free Learning Approach for MILP and WCSP Optimisation (Pierre Montalbano, Université de Tours)
1st International Workshop on Solving Linear Optimization Problems for Pseudo-Booleans and Yonder, Lund, Sweden, November 2024
Weighted Constraint Satisfaction Problems (WCSP) are an extension of the classic Constraint Satisfaction Problem (CSP), where costs (or weights) are associated with constraint violations. The objective is to find an assignment that minimizes the total constraint violation. Solving WCSPs typically relies on backtracking search and constraint propagation to compute lower bounds. It has the ability to handle global constraints, but it often requires a dedicated algorithm to propagate them.
Guided by the success of conflict-based learning methods in multiple domains (such as SAT, Pseudo-Boolean Optimization, or ILP), we designed a new conflict-free learning mechanism. This mechanism aims to memorize, through a linear constraint, the lower bounds of encountered sub-problems. If the same sub-problem (or a similar one) reappears in the search, propagating the previously learned constraint will help to obtain a stronger lower bound. This learning mechanism is conflict-free, meaning that it doesn't require a conflict to be triggered and can be used to learn a constraint at every node of a search tree.
Our approach integrates techniques from CP, ILP, and PBO, and we show how it can be embedded inside a classic MILP solver before extending it to WCSP solvers. We implemented this learning mechanism in a simple solver performing branch-and-bound and using CPLEX to solve the LP at every node. We show that it can significantly decrease the number of visited nodes for the knapsack problem or kb-tree (instances with a bounded treewidth).
See [ Ссылка ] for more information about the SLOPPY '24 workshop and links to available videos and slides. At [ Ссылка ] you find information about other seminars organized by the MIAO research group.
