Essec\Faculty\Model\Contribution {#6196
  #_index: "academ_contributions"
  #_id: "622"
  #_source: array:26 [
    "id" => "622"
    "slug" => "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."
    "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."
      "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."
    ]
    "authors_fields" => array:2 [
      "fr" => "Systèmes d’Information, Sciences de la Décision et Statistiques"
      "en" => "Information Systems, Decision Sciences and Statistics"
    ]
    "indexedAt" => "2024-04-19T15:22:10.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, Sciences de la Décision et Statistiques</span> | <span class="document-property-year">2017</span>"
    "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>"
    "docPreview" => "<b>An Effective Dynamic Programming Algorithm for the Minimum-Cost Maximal Knapsack Packing Problem</b><br><span>2017-10 | Articles </span>"
    "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>"
  ]
  +lang: "fr"
  +"_type": "_doc"
  +"_score": 9.106091
  +"parent": null
}