Show simple item record

dc.contributor.authorFurini, Fabio
dc.contributor.authorTraversi, Emiliano
dc.date.accessioned2019-04-12T14:40:11Z
dc.date.available2019-04-12T14:40:11Z
dc.date.issued2018
dc.identifier.issn1572-9338
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18644
dc.language.isoenen
dc.subjectLinearisation techniquesen
dc.subjectBinary quadratic problemsen
dc.subjectMax cut problemen
dc.subjectQuadratic knapsack problemen
dc.subjectQuadratic stable set problemen
dc.subject.ddc003en
dc.titleTheoretical and computational study of several linearisation techniques for binary quadratic problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe perform a theoretical and computational study of the classical linearisation techniques (LT) and we propose a new LT for binary quadratic problems (BQPs). We discuss the relations between the linear programming (LP) relaxations of the considered LT for generic BQPs. We prove that for a specific class of BQP all the LTs have the same LP relaxation value. We also compare the LT computational performance for four different BQPs from the literature. We consider the Unconstrained BQP and the maximum cut of edge-weighted graphs and, in order to measure the effects of constraints on the computational performance, we also consider the quadratic extension of two classical combinatorial optimization problems, i.e., the knapsack and stable set problems.en
dc.relation.isversionofjnlnameAnnals of Operations Research
dc.relation.isversionofjnldate2018
dc.relation.isversionofjnlpages1-25en
dc.relation.isversionofdoi10.1007/s10479-018-3118-2en
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingouien
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-03-27T12:19:28Z
hal.person.labIds989
hal.person.labIds994


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record