ALGORITHMS FOR LINEAR PSEUDO-BOOLEAN OPTIMIZATION
Departamento de Engenharia Informática –
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:
Workshop “Metabolism and mathematical models: Two for a tango” – 2nd Edition
Title: Workshop Metabolism and mathematical models: Two for a tango – 2nd Edition
Dates: October 25-26, 2022
Location: This workshop will be held in a virtual way
The topic of this workshop is metabolism in general, with a special focus, although not exclusive, on parasitology. Besides an exploration of the biological, biochemical and biomedical aspects, the workshop will also aim at presenting some of the mathematical modelling, algorithmic theory and software development that have become crucial to explore such aspects.
This workshop is being organised in the context of two projects, both with the Inria European Team Erable. One of the projects involves a partnership with the University of São Paulo (USP), in São Paulo, Brazil, more specifically the Institute of Mathematics and Statistics (IME) and the Institute of Biomedical Sciences – Inria Associated Team Capoeira – and the other involves the Inesc-ID/IST in Portugal, ETH in Zürich and EMBL in Heidelberg – H2020 Twinning Project Olissipo.
The workshop is open to all members of these two projects but also, importantly, to the community in general.
The program and more details are available here.