dc.contributor.author Soutif, Eric dc.contributor.author Quadri, Dominique dc.date.accessioned 2010-06-29T09:36:16Z dc.date.available 2010-06-29T09:36:16Z dc.date.issued 2007 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/4485 dc.language.iso en en dc.subject integer quadratic knapsack problem en dc.subject separable objective function en dc.subject direct expansion en dc.subject binary expansion en dc.subject piecewise interpolation en dc.subject.ddc 003 en dc.title Rewriting integer variables into zero-one variables: some guidelines for the integer quadratic multi-knapsack problem en dc.type Article accepté pour publication ou publié dc.description.abstracten This 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.isversionofjnlname Operational Research dc.relation.isversionofjnlvol 7 en dc.relation.isversionofjnlissue 2 en dc.relation.isversionofjnldate 2007 dc.relation.isversionofjnlpages 299-314 en dc.relation.isversionofdoi http://dx.doi.org/10.1007/BF02942392 en dc.description.sponsorshipprivate oui en dc.relation.isversionofjnlpublisher Springer en dc.subject.ddclabel Recherche opérationnelle en
﻿