• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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érence
Date
2015
Book title
Integration of AI and OR Techniques in Constraint Programming 12th International Conference, CPAIOR 2015, Barcelona, Spain, May 18-22, 2015, Proceedings
Book author
Laurent Michel
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-319-18007-6; 978-3-319-18008-3
Pages
255-270
Publication identifier
10.1007/978-3-319-18008-3_18
Metadata
Show full item record
Author(s)
Furini, Fabio
Laboratoire 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 optimization
JEL
C61 - Optimization Techniques; Programming Models; Dynamic Analysis
C44 - Operations Research; Statistical Decision Theory

Related items

Showing items related by title and author.

  • Thumbnail
    On integer and bilevel formulations for the k-vertex cut problem 
    Furini, Fabio; Ljubić, Ivana; Malaguti, Enrico; Paronuzzi, Paolo (2020) Article accepté pour publication ou publié
  • Thumbnail
    An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem 
    Furini, Fabio; Ljubić, Ivana; Sinnl, Markus (2017) Article accepté pour publication ou publié
  • Thumbnail
    A new branch-and-bound algorithm for the maximum edge-weighted clique problem 
    San Segundo, Pablo; Coniglio, Stefano; Furini, Fabio; Ljubić, Ivana (2019) Article accepté pour publication ou publié
  • Thumbnail
    Benders decomposition for very large scale partial set covering and maximal covering location problems 
    Cordeau, Jean-François; Furini, Fabio; Ljubić, Ivana (2019) Article accepté pour publication ou publié
  • Thumbnail
    The maximum clique interdiction problem 
    Furini, Fabio; Ljubić, Ivana; Martin, Sébastien; San Segundo, Pablo (2019) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo