Essec\Faculty\Model\Contribution {#2233 ▼
#_index: "academ_contributions"
#_id: "622"
#_source: array:26 [
"id" => "622"
"slug" => "622-an-effective-dynamic-programming-algorithm-for-the-minimum-cost-maximal-knapsack-packing-problem"
"yearMonth" => "2017-10"
"year" => "2017"
"title" => "An Effective Dynamic Programming Algorithm for the Minimum-Cost Maximal Knapsack Packing Problem"
"description" => "FURINI, F., LJUBIC, I. et SINNL, M. (2017). An Effective Dynamic Programming Algorithm for the Minimum-Cost Maximal Knapsack Packing Problem. <i>European Journal of Operational Research</i>, 262(2), pp. 438-448. 
FURINI, F., LJUBIC, I. et SINNL, M. (2017). An Effective Dynamic Programming Algorithm for the Minim "
"authors" => array:3 [
0 => array:3 [
"name" => "LJUBIC Ivana"
"bid" => "B00683004"
"slug" => "ljubic-ivana"
]
1 => array:1 [
"name" => "FURINI F."
]
2 => array:1 [
"name" => "SINNL M."
]
]
"ouvrage" => ""
"keywords" => array:5 [
0 => "Combinatorial optimization"
1 => "Maximal knapsack packing"
2 => "Minimal knapsack cover"
3 => "Dynamic programming"
4 => "Integer programming"
]
"updatedAt" => "2021-09-24 10:33:27"
"publicationUrl" => "https://www.sciencedirect.com/science/article/abs/pii/S0377221717302928"
"publicationInfo" => array:3 [
"pages" => "438-448"
"volume" => "262"
"number" => "2"
]
"type" => array:2 [
"fr" => "Articles"
"en" => "Journal articles"
]
"support_type" => array:2 [
"fr" => "Revue scientifique"
"en" => "Scientific journal"
]
"countries" => array:2 [
"fr" => null
"en" => null
]
"abstract" => array:2 [
"fr" => "Given a set of items with profits and weights and a knapsack capacity, we study the problem of finding a maximal knapsack packing that minimizes the profit of the selected items. We propose an effective dynamic programming (DP) algorithm which has a pseudo-polynomial time complexity. We demonstrate the equivalence between this problem and the problem of finding a minimal knapsack cover that maximizes the profit of the selected items. In an extensive computational study on a large and diverse set of benchmark instances, we demonstrate that the new DP algorithm outperforms a state-of-the-art commercial mixed-integer programming (MIP) solver applied to the two best performing MIP models from the literature. Given a set of items with profits and weights and a knapsack capacity, we study the problem of findi "
"en" => "Given a set of items with profits and weights and a knapsack capacity, we study the problem of finding a maximal knapsack packing that minimizes the profit of the selected items. We propose an effective dynamic programming (DP) algorithm which has a pseudo-polynomial time complexity. We demonstrate the equivalence between this problem and the problem of finding a minimal knapsack cover that maximizes the profit of the selected items. In an extensive computational study on a large and diverse set of benchmark instances, we demonstrate that the new DP algorithm outperforms a state-of-the-art commercial mixed-integer programming (MIP) solver applied to the two best performing MIP models from the literature. Given a set of items with profits and weights and a knapsack capacity, we study the problem of findi "
]
"authors_fields" => array:2 [
"fr" => "Systèmes d'Information, Data Analytics et Opérations"
"en" => "Information Systems, Data Analytics and Operations"
]
"indexedAt" => "2025-04-02T08:21:48.000Z"
"docTitle" => "An Effective Dynamic Programming Algorithm for the Minimum-Cost Maximal Knapsack Packing Problem"
"docSurtitle" => "Articles"
"authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, FURINI F., SINNL M."
"docDescription" => "<span class="document-property-authors">LJUBIC Ivana, FURINI F., SINNL M.</span><br><span class="document-property-authors_fields">Systèmes d'Information, Data Analytics et Opérations</span> | <span class="document-property-year">2017</span> <span class="document-property-authors">LJUBIC Ivana, FURINI F., SINNL M.</span><br><span class="doc "
"keywordList" => "<a href="#">Combinatorial optimization</a>, <a href="#">Maximal knapsack packing</a>, <a href="#">Minimal knapsack cover</a>, <a href="#">Dynamic programming</a>, <a href="#">Integer programming</a> <a href="#">Combinatorial optimization</a>, <a href="#">Maximal knapsack packing</a>, <a href="#">Mi "
"docPreview" => "<b>An Effective Dynamic Programming Algorithm for the Minimum-Cost Maximal Knapsack Packing Problem</b><br><span>2017-10 | Articles </span> <b>An Effective Dynamic Programming Algorithm for the Minimum-Cost Maximal Knapsack Packing Problem< "
"docType" => "research"
"publicationLink" => "<a href="https://www.sciencedirect.com/science/article/abs/pii/S0377221717302928" target="_blank">An Effective Dynamic Programming Algorithm for the Minimum-Cost Maximal Knapsack Packing Problem</a> <a href="https://www.sciencedirect.com/science/article/abs/pii/S0377221717302928" target="_blank">An "
]
+lang: "fr"
+"_type": "_doc"
+"_score": 8.970983
+"parent": null
}
