Show simple item record

dc.contributor.authorSoutif, Eric
dc.contributor.authorQuadri, Dominique
dc.date.accessioned2010-06-29T09:36:16Z
dc.date.available2010-06-29T09:36:16Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/4485
dc.language.isoenen
dc.subjectinteger quadratic knapsack problemen
dc.subjectseparable objective functionen
dc.subjectdirect expansionen
dc.subjectbinary expansionen
dc.subjectpiecewise interpolationen
dc.subject.ddc003en
dc.titleRewriting integer variables into zero-one variables: some guidelines for the integer quadratic multi-knapsack problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThis paper is concerned with the integer quadratic multidimensional knapsack problem (QMKP) where the objective function is separable. Our objective is to determine which expansion technique of the integer variables is the most appropriate to solve (QMKP) to optimality using the upper bound method proposed by Quadri et al. (2007). To the best of our knowledge the upper bound method previously mentioned is the most effective method in the literature concerning (QMKP). This bound is computed by transforming the initial quadratic problem into a 0–1 equivalent piecewise linear formulation and then by establishing the surrogate problem associated. The linearization method consists in using a direct expansion initially suggested by Glover (1975) of the integer variables and in applying a piecewise interpolation to the separable objective function. As the direct expansion results in an increase of the size of the problem, other expansions techniques may be utilized to reduce the number of 0–1 variables so as to make easier the solution to the linearized problem. We will compare theoretically the use in the upper bound process of the direct expansion (I) employed in Quadri et al. (2007) with two other basic expansions, namely: (II) a direct expansion with additional constraints and (III) a binary expansion. We show that expansion (II) provides a bound which value is equal to the one computed by Quadri et al (2007). Conversely, we provide the proof of the non applicability of expansion (III) in the upper bound method. More specifically, we will show that if (III) is used to rewrite the integer variables into 0–1 variables then a linear interpolation can not be applied to transform (QMKP) into an equivalent 0–1 piecewise linear problem.en
dc.relation.isversionofjnlnameOperational Research
dc.relation.isversionofjnlvol7en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2007
dc.relation.isversionofjnlpages299-314en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/BF02942392en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record