Show simple item record

dc.contributor.authorFurini, Fabio*
dc.contributor.authorLjubić, Ivana*
dc.contributor.authorSinnl, Markus*
dc.date.accessioned2017-03-20T14:44:11Z
dc.date.available2017-03-20T14:44:11Z
dc.date.issued2015
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16411
dc.descriptionLNCS, Vol. 9075
dc.language.isoenen
dc.subjectcombinatorial optimization
dc.subject.ddc003en
dc.subject.classificationjelC61en
dc.subject.classificationjelC44en
dc.titleILP and CP Formulations for the Lazy Bureaucrat Problem
dc.typeCommunication / Conférence
dc.description.abstractenLazy reformulations of classical combinatorial optimization problems are new and challenging classes of problems. In this paper we focus on the Lazy Bureaucrat Problem (LBP) which is the lazy counterpart of the knapsack problem. Given a set of tasks with a common arrival time and deadline, the goal of a lazy bureaucrat is to schedule a least profitable subset of tasks, while having an excuse that no other tasks can be scheduled without exceeding the deadline.Three ILP formulations and their CP counterparts are studied and implemented. In addition, a dynamic programming algorithm that runs is pseudo-polynomial time and polynomial greedy heuristics are implemented and computationally compared with ILP/CP approaches. For the computational study, a large set of knapsack-type instances with various characteristics is used to examine the applicability and strength of the proposed approaches.
dc.identifier.citationpages255-270
dc.relation.ispartoftitleIntegration of AI and OR Techniques in Constraint Programming 12th International Conference, CPAIOR 2015, Barcelona, Spain, May 18-22, 2015, Proceedings
dc.relation.ispartofeditorLaurent Michel
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofdate2015
dc.relation.ispartofurl10.1007/978-3-319-18008-3
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-319-18007-6; 978-3-319-18008-3
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-18008-3_18
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2019-02-20T16:13:58Z
hal.person.labIds989*
hal.person.labIds*
hal.person.labIds*
hal.identifierhal-01492801*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record