TY - JOUR
T1 - Boolean lexicographic optimization
T2 - algorithms & applications
AU - Marques-Silva, João
AU - Argelich, Josep
AU - Graça, Ana
AU - Lynce, Inês
N1 - Funding Information:
This work was partially funded by SFI PI Grant 09/IN.1/I2618, EU grants FP7-ICT-217069 and FP7-ICT-214898, FCT grant ATTEST (CMU-PT/ELE/0009/2009), FCT PhD grant SFRH/BD/ 28599/2006, CICYT Projects TIN2009-14704-C03-01 and TIN2010-20967-C04-03, and by INESC-ID multiannual funding from the PIDDAC program funds.
PY - 2011/7
Y1 - 2011/7
N2 - Multi-Objective Combinatorial Optimization (MOCO) problems find a wide range of practical application problems, some of which involving Boolean variables and constraints. This paper develops and evaluates algorithms for solving 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. Finally, the paper also shows that lexicographic optimization conditions are observed in the majority of the problem instances from the MaxSAT evaluations, motivating the development of dedicated algorithms that can exploit lexicographic optimization conditions in general MaxSAT problem instances.
AB - Multi-Objective Combinatorial Optimization (MOCO) problems find a wide range of practical application problems, some of which involving Boolean variables and constraints. This paper develops and evaluates algorithms for solving 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. Finally, the paper also shows that lexicographic optimization conditions are observed in the majority of the problem instances from the MaxSAT evaluations, motivating the development of dedicated algorithms that can exploit lexicographic optimization conditions in general MaxSAT problem instances.
KW - Boolean optimization
KW - Haplotyping with pedigrees
KW - Lexicographic optimization
KW - Maximum satisfiability
KW - Pseudo-Boolean optimization
KW - Software package dependencies
UR - http://www.scopus.com/inward/record.url?scp=84856553406&partnerID=8YFLogxK
U2 - 10.1007/s10472-011-9233-2
DO - 10.1007/s10472-011-9233-2
M3 - Article
AN - SCOPUS:84856553406
SN - 1012-2443
VL - 62
SP - 317
EP - 343
JO - Annals of Mathematics and Artificial Intelligence
JF - Annals of Mathematics and Artificial Intelligence
IS - 3-4
ER -