• DocumentCode
    3154562
  • Title

    A dynamic programming method with dominance technique for the knapsack sharing problem

  • Author

    Boyer, V. ; Baz, D. EI ; Elkihel, M.

  • Author_Institution
    CNRS, LAAS, Toulouse, France
  • fYear
    2009
  • fDate
    6-9 July 2009
  • Firstpage
    348
  • Lastpage
    353
  • Abstract
    In this paper, we propose an original method to solve exactly the knapsack sharing problem (KSP) by using a dynamic programming with dominance technique. The original problem (KSP) is decomposed in a set of knapsack problems. Our method is tested on uncorrelated and correlated instances from the literature. Computational experiences show that our method is able to find an optimal solution of large instances within reasonable computing time.
  • Keywords
    dynamic programming; knapsack problems; combinatorial optimization; dominance technique; dynamic programming method; knapsack sharing problem; max-min programming; Approximation algorithms; Dynamic programming; Heuristic algorithms; Indium phosphide; Mathematical programming; Testing; Uninterruptible power systems; Upper bound; Combinatorial optimization; Dynamic programming; Knapsack sharing problem; Max-min programming;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computers & Industrial Engineering, 2009. CIE 2009. International Conference on
  • Conference_Location
    Troyes
  • Print_ISBN
    978-1-4244-4135-8
  • Electronic_ISBN
    978-1-4244-4136-5
  • Type

    conf

  • DOI
    10.1109/ICCIE.2009.5223827
  • Filename
    5223827
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3154562