Essec\Faculty\Model\Contribution {#2233 ▼
#_index: "academ_contributions"
#_id: "11973"
#_source: array:26 [
"id" => "11973"
"slug" => "11973-ilp-and-cp-formulations-for-the-lazy-bureaucrat-problem"
"yearMonth" => "2015-01"
"year" => "2015"
"title" => "ILP and CP Formulations for the Lazy Bureaucrat Problem"
"description" => "FURINI, F., LJUBIC, I. et SINNL, M. (2015). ILP and CP Formulations for the Lazy Bureaucrat Problem. Dans: Laurent Michel (ed.). <i>Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2015)</i>. 1st ed. Cham, New York: Springer, pp. 255-270. 
FURINI, F., LJUBIC, I. et SINNL, M. (2015). ILP and CP Formulations for the Lazy Bureaucrat Problem. "
"authors" => array:3 [
0 => array:3 [
"name" => "LJUBIC Ivana"
"bid" => "B00683004"
"slug" => "ljubic-ivana"
]
1 => array:1 [
"name" => "FURINI Fabio"
]
2 => array:1 [
"name" => "SINNL Markus"
]
]
"ouvrage" => "Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2015)"
"keywords" => array:3 [
0 => "computational study"
1 => "combinatorial optimization problems"
2 => "dynamic programming algorithm"
]
"updatedAt" => "2024-04-18 11:33:36"
"publicationUrl" => "https://link.springer.com/chapter/10.1007/978-3-319-18008-3_18"
"publicationInfo" => array:3 [
"pages" => "255-270"
"volume" => "LNTCS, volume 9075"
"number" => "18"
]
"type" => array:2 [
"fr" => "Chapitres"
"en" => "Book chapters"
]
"support_type" => array:2 [
"fr" => "Editeur"
"en" => "Publisher"
]
"countries" => array:2 [
"fr" => null
"en" => null
]
"abstract" => array:2 [
"fr" => """
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.\n Lazy reformulations of classical combinatorial optimization problems are new and challenging classes
\n
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. Three ILP formulations and their CP counterparts are studied and implemented. In addition, a dynamic
"""
"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.\n Lazy reformulations of classical combinatorial optimization problems are new and challenging classes
\n
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. Three ILP formulations and their CP counterparts are studied and implemented. In addition, a dynamic
"""
]
"authors_fields" => array:2 [
"fr" => "Systèmes d'Information, Data Analytics et Opérations"
"en" => "Information Systems, Data Analytics and Operations"
]
"indexedAt" => "2025-04-02T12:21:45.000Z"
"docTitle" => "ILP and CP Formulations for the Lazy Bureaucrat Problem"
"docSurtitle" => "Chapitres"
"authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, FURINI Fabio, SINNL Markus"
"docDescription" => "<span class="document-property-authors">LJUBIC Ivana, FURINI Fabio, SINNL Markus</span><br><span class="document-property-authors_fields">Systèmes d'Information, Data Analytics et Opérations</span> | <span class="document-property-year">2015</span> <span class="document-property-authors">LJUBIC Ivana, FURINI Fabio, SINNL Markus</span><br><span cla "
"keywordList" => "<a href="#">computational study</a>, <a href="#">combinatorial optimization problems</a>, <a href="#">dynamic programming algorithm</a> <a href="#">computational study</a>, <a href="#">combinatorial optimization problems</a>, <a href="# "
"docPreview" => "<b>ILP and CP Formulations for the Lazy Bureaucrat Problem</b><br><span>2015-01 | Chapitres </span>"
"docType" => "research"
"publicationLink" => "<a href="https://link.springer.com/chapter/10.1007/978-3-319-18008-3_18" target="_blank">ILP and CP Formulations for the Lazy Bureaucrat Problem</a> <a href="https://link.springer.com/chapter/10.1007/978-3-319-18008-3_18" target="_blank">ILP and CP "
]
+lang: "fr"
+"_type": "_doc"
+"_score": 8.784652
+"parent": null
}
