Decomposition and Linearization for 0-1 Quadratic Programming

Sourour Elloumi; Alain Faye; Eric Soutif

doi:10.1023/a:1019236832495

Decomposition and Linearization for 0-1 Quadratic Programming

Sourour Elloumi
, Alain Faye
, Eric Soutif

CEDRIC-CNAM
CEDRIC-IIE(CNAM)

Research output: Contribution to journal › Article › peer-review

Abstract

This paper presents a general decomposition method to compute bounds for constrained 0-1 quadratic programming. The best decomposition is found by using a Lagrangian decomposition of the problem. Moreover, in its simplest version this method is proved to give at least the bound obtained by the LP-relaxation of a non-trivial linearization. To illustrate this point, some computational results are given for the 0-1 quadratic knapsack problem.

Original language	English
Pages (from-to)	79-93
Number of pages	15
Journal	Annals of Operations Research
Volume	99
Issue number	1-4
DOIs	https://doi.org/10.1023/a:1019236832495
Publication status	Published - 1 Jan 2000
Externally published	Yes

Keywords

Lagrangian decomposition
Linearization
Mixed integer programming
Quadratic 0-1 programming

Access to Document

10.1023/a:1019236832495

Cite this

@article{b183b738a8074130bed9936f8b9839c5,

title = "Decomposition and Linearization for 0-1 Quadratic Programming",

abstract = "This paper presents a general decomposition method to compute bounds for constrained 0-1 quadratic programming. The best decomposition is found by using a Lagrangian decomposition of the problem. Moreover, in its simplest version this method is proved to give at least the bound obtained by the LP-relaxation of a non-trivial linearization. To illustrate this point, some computational results are given for the 0-1 quadratic knapsack problem.",

keywords = "Lagrangian decomposition, Linearization, Mixed integer programming, Quadratic 0-1 programming",

author = "Sourour Elloumi and Alain Faye and Eric Soutif",

year = "2000",

month = jan,

day = "1",

doi = "10.1023/a:1019236832495",

language = "English",

volume = "99",

pages = "79--93",

journal = "Annals of Operations Research",

issn = "0254-5330",

number = "1-4",

}

TY - JOUR

T1 - Decomposition and Linearization for 0-1 Quadratic Programming

AU - Elloumi, Sourour

AU - Faye, Alain

AU - Soutif, Eric

PY - 2000/1/1

Y1 - 2000/1/1

N2 - This paper presents a general decomposition method to compute bounds for constrained 0-1 quadratic programming. The best decomposition is found by using a Lagrangian decomposition of the problem. Moreover, in its simplest version this method is proved to give at least the bound obtained by the LP-relaxation of a non-trivial linearization. To illustrate this point, some computational results are given for the 0-1 quadratic knapsack problem.

AB - This paper presents a general decomposition method to compute bounds for constrained 0-1 quadratic programming. The best decomposition is found by using a Lagrangian decomposition of the problem. Moreover, in its simplest version this method is proved to give at least the bound obtained by the LP-relaxation of a non-trivial linearization. To illustrate this point, some computational results are given for the 0-1 quadratic knapsack problem.

KW - Lagrangian decomposition

KW - Linearization

KW - Mixed integer programming

KW - Quadratic 0-1 programming

U2 - 10.1023/a:1019236832495

DO - 10.1023/a:1019236832495

M3 - Article

AN - SCOPUS:0034562988

SN - 0254-5330

VL - 99

SP - 79

EP - 93

JO - Annals of Operations Research

JF - Annals of Operations Research

IS - 1-4

ER -

Decomposition and Linearization for 0-1 Quadratic Programming

Abstract

Keywords

Access to Document

Fingerprint

Cite this