Canonical dual approach to solving 0-1 quadratic programming problems

Shu Cherng Fang; David Yang Gao; Ruey Lin Sheu; Soon Yi Wu

doi:10.3934/jimo.2008.4.125

Canonical dual approach to solving 0-1 quadratic programming problems

Shu Cherng Fang, David Yang Gao, Ruey Lin Sheu, Soon Yi Wu

Department of Mathematics

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

56 Citations (Scopus)

Abstract

By using the canonical dual transformation developed recently, we derive a pair of canonical dual problems for 0-1 quadratic programming problems in both minimization and maximization form. Regardless convexity, when the canonical duals are solvable, no duality gap exists between the primal and corresponding dual problems. Both global and local optimality conditions are given. An algorithm is presented for finding global minimizers, even when the primal objective function is not convex. Examples are included to illustrate this new approach.

Original language	English
Pages (from-to)	125-142
Number of pages	18
Journal	Journal of Industrial and Management Optimization
Volume	4
Issue number	1
DOIs	https://doi.org/10.3934/jimo.2008.4.125
Publication status	Published - 2008

All Science Journal Classification (ASJC) codes

Business and International Management
Strategy and Management
Control and Optimization
Applied Mathematics

Access to Document

10.3934/jimo.2008.4.125

Fingerprint Dive into the research topics of 'Canonical dual approach to solving 0-1 quadratic programming problems'. Together they form a unique fingerprint.

Cite this

@article{e354909cd9cd490da7754061966ffb53,

title = "Canonical dual approach to solving 0-1 quadratic programming problems",

abstract = "By using the canonical dual transformation developed recently, we derive a pair of canonical dual problems for 0-1 quadratic programming problems in both minimization and maximization form. Regardless convexity, when the canonical duals are solvable, no duality gap exists between the primal and corresponding dual problems. Both global and local optimality conditions are given. An algorithm is presented for finding global minimizers, even when the primal objective function is not convex. Examples are included to illustrate this new approach.",

author = "Fang, {Shu Cherng} and Gao, {David Yang} and Sheu, {Ruey Lin} and Wu, {Soon Yi}",

year = "2008",

doi = "10.3934/jimo.2008.4.125",

language = "English",

volume = "4",

pages = "125--142",

journal = "Journal of Industrial and Management Optimization",

issn = "1547-5816",

publisher = "American Institute of Mathematical Sciences",

number = "1",

}

TY - JOUR

T1 - Canonical dual approach to solving 0-1 quadratic programming problems

AU - Fang, Shu Cherng

AU - Gao, David Yang

AU - Sheu, Ruey Lin

AU - Wu, Soon Yi

PY - 2008

Y1 - 2008

N2 - By using the canonical dual transformation developed recently, we derive a pair of canonical dual problems for 0-1 quadratic programming problems in both minimization and maximization form. Regardless convexity, when the canonical duals are solvable, no duality gap exists between the primal and corresponding dual problems. Both global and local optimality conditions are given. An algorithm is presented for finding global minimizers, even when the primal objective function is not convex. Examples are included to illustrate this new approach.

AB - By using the canonical dual transformation developed recently, we derive a pair of canonical dual problems for 0-1 quadratic programming problems in both minimization and maximization form. Regardless convexity, when the canonical duals are solvable, no duality gap exists between the primal and corresponding dual problems. Both global and local optimality conditions are given. An algorithm is presented for finding global minimizers, even when the primal objective function is not convex. Examples are included to illustrate this new approach.

UR - http://www.scopus.com/inward/record.url?scp=56649105067&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=56649105067&partnerID=8YFLogxK

U2 - 10.3934/jimo.2008.4.125

DO - 10.3934/jimo.2008.4.125

M3 - Article

AN - SCOPUS:56649105067

VL - 4

SP - 125

EP - 142

JO - Journal of Industrial and Management Optimization

JF - Journal of Industrial and Management Optimization

SN - 1547-5816

IS - 1

ER -