• français
    • English
  • français 
    • français
    • English
  • Connexion
JavaScript is disabled for your browser. Some features of this site may not work without it.
Accueil

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

ILP and CP Formulations for the Lazy Bureaucrat Problem

Thumbnail
Date
2015
Description
LNCS, Vol. 9075
Indexation documentaire
Recherche opérationnelle
Subject
combinatorial optimization
Code JEL
C61; C44
Réf version publiée
http://dx.doi.org/10.1007/978-3-319-18008-3_18
Titre de l'ouvrage
Integration of AI and OR Techniques in Constraint Programming 12th International Conference, CPAIOR 2015, Barcelona, Spain, May 18-22, 2015, Proceedings
Auteur
Laurent Michel
Nom de l'éditeur
Springer
Ville de l'éditeur
Berlin Heidelberg
Année
2015
ISBN
978-3-319-18007-6; 978-3-319-18008-3
URL de l'ouvrage
10.1007/978-3-319-18008-3
URI
https://basepub.dauphine.fr/handle/123456789/16411
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
Furini, Fabio
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ljubić, Ivana
Sinnl, Markus
Type
Communication / Conférence
Nombre de pages du document
255-270
Résumé en anglais
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Cette création est mise à disposition sous un contrat Creative Commons.