Vasco Manquinho,

D – Departamento de Engenharia Informática, Instituto Superior Técnico, Universidade de Lisboa –

Abstract:

New algorithms for Pseudo-Boolean Optimization have been motivated by the recent advances in Propositional Satisfiability (SAT) algorithms. These new techniques developed in SAT algorithms are powerful mechanisms in manipulating problem constraints, but they are not effective in dealing with information from the cost function in Pseudo-Boolean Optimization problem instances.
In this dissertation we propose a new algorithmic framework for solving the Pseudo-Boolean Optimization problem. We start by introducing a new algorithm that integrates SAT-based techniques such has non-chronological backtracking, Boolean constraint propagation and constraint learning with classical branch and bound techniques, namely the use of lower bound estimation procedures on the value of the cost function. Moreover, we provide conditions for using several lower bound estimation procedures with SAT-based techniques and introduce the notion of bound conflict learning. Finally, we also propose the use of cutting plane techniques commonly used in Integer Linear Programming within a SAT-based framework. Experimental results show that our algorithm is more effective in solving several Pseudo-Boolean Optimization problem instances and provide a significant contribution to this area.

 

Date: 2006-Jul-20     Time: 14:00:00     Room: ANFITEATRO DO COMPLEXO I DO IST

For more information: