Show simple item record

dc.contributor.authorMarques-Silva, Joao
dc.contributor.authorArgelich Romà, Josep
dc.contributor.authorGraça, Ana
dc.contributor.authorLynce, Inês
dc.date.accessioned2016-06-23T09:17:32Z
dc.date.issued2011
dc.identifier.issn1012-2443
dc.identifier.urihttp://hdl.handle.net/10459.1/57277
dc.description.abstractMulti-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.ca_ES
dc.description.sponsorshipThis 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.ca_ES
dc.language.isoengca_ES
dc.publisherSpringer Verlagca_ES
dc.relationMICINN/PN2008-2011/TIN2009-14704-C03-01ca_ES
dc.relationMICINN/PN2008-2011/TIN2010-20967-C04-03ca_ES
dc.relation.isformatofReproducció del document publicat a https://doi.org/10.1007/s10472-011-9233-2ca_ES
dc.relation.ispartofAnnals of Mathematics and Artificial Intelligence, 2011, vol. 62, núm. 3, p. 317-343ca_ES
dc.rights(c) Springer Science+Business Media B.V., 2011ca_ES
dc.subjectBoolean optimizationca_ES
dc.subjectLexicographic optimizationca_ES
dc.subjectMaximum satisfiabilityca_ES
dc.subjectPseudo-Boolean optimizationca_ES
dc.titleBoolean lexicographic optimization: algorithms & applicationsca_ES
dc.typearticleca_ES
dc.identifier.idgrec018596
dc.type.versionpublishedVersionca_ES
dc.rights.accessRightsinfo:eu-repo/semantics/restrictedAccessca_ES
dc.identifier.doihttps://doi.org/10.1007/s10472-011-9233-2
dc.relation.projectIDinfo:eu-repo/grantAgreement/EC/FP7/217069ca_ES
dc.relation.projectIDinfo:eu-repo/grantAgreement/EC/FP7/214898
dc.date.embargoEndDate10000-01-01


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record