Multiple-choice Knapsack Constraint in Graphical Models - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Access content directly
Conference Papers Year : 2022

Multiple-choice Knapsack Constraint in Graphical Models


Graphical models, such as cost function networks (CFNs), can compactly express large decomposable functions, which leads to efficient inference algorithms. Most methods for computing lower bounds in Branch-and-Bound minimization compute feasible dual solutions of a specific linear relaxation. These methods are more effective than solving the linear relaxation exactly, with better worst-case time complexity and better performance in practice. However, these algorithms are specialized to the structure of the linear relaxation of a CFN and cannot, for example, deal with constraints that cannot be expressed in extension, such as linear constraints of large arity. In this work, we show how to extend soft local consistencies, a set of approximate inference techniques for CFNs, so that they handle linear constraints, as well as combinations of linear constraints with at-most-one constraints. We embedded the resulting algorithm in TOULBAR2, an exact Branch-and-Bound solver for CFNs which has demonstrated superior results in several graphical model competitions and is state-of-the-art for solving large computational protein design (CPD) problems. We significantly improved performance of the solver in CPD with diversity guarantees. It also compared favorably with integer linear programming solvers on knapsack problems with conflict graphs.
No file

Dates and versions

hal-04106508 , version 1 (25-05-2023)



Pierre Montalbano, Simon de Givry, George Katsirelos. Multiple-choice Knapsack Constraint in Graphical Models. 19. International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), Jun 2022, Los Angeles, United States. pp.282-299, ⟨10.1007/978-3-031-08011-1_19⟩. ⟨hal-04106508⟩
4 View
0 Download



Gmail Facebook Twitter LinkedIn More