ILP and CP Formulations for the Lazy Bureaucrat Problem
Furini, Fabio; Ljubić, Ivana; Sinnl, Markus (2015), ILP and CP Formulations for the Lazy Bureaucrat Problem, in Laurent Michel, Integration of AI and OR Techniques in Constraint Programming 12th International Conference, CPAIOR 2015, Barcelona, Spain, May 18-22, 2015, Proceedings, Springer : Berlin Heidelberg, p. 255-270. 10.1007/978-3-319-18008-3_18
Type
Communication / ConférenceDate
2015Book title
Integration of AI and OR Techniques in Constraint Programming 12th International Conference, CPAIOR 2015, Barcelona, Spain, May 18-22, 2015, ProceedingsBook author
Laurent MichelPublisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-319-18007-6; 978-3-319-18008-3
Pages
255-270
Publication identifier
Metadata
Show full item recordAuthor(s)
Furini, FabioLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ljubić, Ivana
Sinnl, Markus
Abstract (EN)
Lazy 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.Subjects / Keywords
combinatorial optimizationRelated items
Showing items related by title and author.
-
Furini, Fabio; Ljubić, Ivana; Malaguti, Enrico; Paronuzzi, Paolo (2020) Article accepté pour publication ou publié
-
Furini, Fabio; Ljubić, Ivana; Sinnl, Markus (2017) Article accepté pour publication ou publié
-
San Segundo, Pablo; Coniglio, Stefano; Furini, Fabio; Ljubić, Ivana (2019) Article accepté pour publication ou publié
-
Cordeau, Jean-François; Furini, Fabio; Ljubić, Ivana (2019) Article accepté pour publication ou publié
-
Furini, Fabio; Ljubić, Ivana; Martin, Sébastien; San Segundo, Pablo (2019) Article accepté pour publication ou publié