Boolean Lexicographic Optimization: Algorithms & Applications
Abstract: Multi-Objective Combinatorial Optimization (MOCO) problems find a wide range of practical application problems, some of which involving Boolean variables and constraints. Boolean Lexicographic Optimization (BLO) are MOCO problems, defined on Boolean domains, and where the optimality criterion is lexicographic. The proposed algorithms build on existing algorithms for either Maximum Satisfiability (MaxSAT), Pseudo-Boolean Optimization (PBO), or Integer Linear Programming (ILP). Experimental results, obtained on problem instances from haplotyping with pedigrees and software package dependencies, show that the proposed algorithms can provide significant performance gains over state of the art MaxSAT, PBO and ILP algorithms.
For further information see:
J. Marques-Silva, J. Argelich, A. Graça and I. Lynce, Boolean Lexicographic Optimization: Algorithms & Applications, Annals of Mathematics and Artificial Intelligence, In Press, DOI 10.1007/s10472-011-9233-2.
Benchmarks:
Part of the BLO benchmarks, Haplotyping with Pedigrees (HwP) subset, are real problem instances from a genetic problem called haplotype inference. These instances are characterized by two cost functions and preference is given to one of them. The models used for creating the HwP instances are described in the following papers:
A. Graça, I. Lynce, J. Marques-Silva and A. Oliveira, Efficient and Accurate Haplotype Inference by Combining Parsimony and Pedigree Information, Algebraic and Numeric Biology, volume 6479 of LNCS, 2010.
A. Graça, I. Lynce, J. Marques-Silva and A. Oliveira, Haplotype Inference Combining Pedigrees and Unrelated Individuals, Workshop on Constraint Based Methods for Bioinformatics, 2009.
These 500 benchmarks, in three different formats, can be downloaded here:
Contacts:
If you have any comments or questions, please email:
jpms_at_ucd.ie (algorithms) or
assg_at_sat.inesc-id.pt (benchmarks).