Show simple item record

Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorFurini, Fabio
hal.structure.identifier
dc.contributor.authorIori, Manuel
hal.structure.identifierFaculty of Engineering [Bologna]
dc.contributor.authorMartello, Silvano
hal.structure.identifier
dc.contributor.authorYagiura, Mutsunori
dc.date.accessioned2017-03-16T11:44:29Z
dc.date.available2017-03-16T11:44:29Z
dc.date.issued2015
dc.identifier.issn1091-9856
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16371
dc.language.isoenen
dc.subjectrobust optimizationen
dc.subjectknapsack problemen
dc.subjectinterval min–max regreten
dc.subjectlocal searchen
dc.subjectLagrangian relaxationen
dc.subjectbranch and cuten
dc.subject.ddc003en
dc.titleHeuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe consider a generalization of the 0–1 knapsack problem in which the profit of each item can take any value in a range characterized by a minimum and a maximum possible profit. A set of specific profits is called a scenario. Each feasible solution associated with a scenario has a regret, given by the difference between the optimal solution value for such scenario and the value of the considered solution. The interval min–max regret knapsack problem (MRKP) is then to find a feasible solution such that the maximum regret over all scenarios is minimized. The problem is extremely challenging both from a theoretical and a practical point of view. Its decision version is complete for the second level of the polynomial hierarchy hence it is most probably not in 𝒩𝒫. In addition, even computing the regret of a solution with respect to a scenario requires the solution of an 𝒩𝒫-hard problem. We examine the behavior of classical combinatorial optimization approaches when adapted to the solution of the MRKP. We introduce an iterated local search approach and a Lagrangian-based branch-and-cut algorithm and evaluate their performance through extensive computational experiments.en
dc.relation.isversionofjnlnameINFORMS Journal on Computing
dc.relation.isversionofjnlvol27en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2015-05
dc.relation.isversionofjnlpages392-405en
dc.relation.isversionofdoi10.1287/ijoc.2014.0632en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-03-16T11:27:12Z
hal.faultCode{"duplicate-entry":{"hal-01491105":{"doi":"1.0"}}}
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record