Polynomially Solvable Cases of Binary Quadratic Programs | |
Li, Duan1; Sun, Xiaoling2; Gu, Shenshen3; Gao, Jianjun1; Liu, Chunli4 | |
2010 | |
出处 | OPTIMIZATION AND OPTIMAL CONTROL: THEORY AND APPLICATIONS |
出版地 | 233 SPRING STREET, NEW YORK, NY 10013, UNITED STATES |
出版者 | SPRINGER |
页码 | 199-225 |
英文摘要 | We summarize in this chapter polynomially solvable subclasses of binary quadratic programming problems studied in the literature and report some new polynomially solvable subclasses revealed in our recent research. It is well known that the binary quadratic programming program is NP-hard in general. Identifying polynomially solvable subclasses of binary quadratic programming problems not only offers theoretical insight into the complicated nature of the problem but also provides platforms to design relaxation schemes for exact solution methods. We discuss and analyze in this chapter six polynomially solvable subclasses of binary quadratic programs, including problems with special structures in the matrix Q of the quadratic objective function, problems defined by a special graph or a logic circuit, and problems characterized by zero duality gap of the SDP relaxation. Examples and geometric illustrations are presented to provide algorithmic and intuitive insights into the problems. |
关键词 | binary quadratic programming polynomial solvability series-parallel graph logic circuit lagrangian dual SDP relaxation |
DOI标识 | 10.1007/978-0-387-89496-6_11 |
语种 | 英语 |
内容类型 | 专著章节 |
源URL | [http://10.2.47.112/handle/2XS4QKH4/3525] ![]() |
专题 | 上海财经大学 |
作者单位 | 1.Chinese Univ Hong Kong, Dept Syst Engn & Engn Management, Shatin, Hong Kong, Peoples R China; 2.Fudan Univ, Sch Management, Dept Management Sci, Shanghai 200433, Peoples R China; 3.Shanghai Univ, Dept Automat, Shanghai 200072, Peoples R China; 4.Shanghai Univ Finance & Econ, Dept Appl Math, Shanghai 200433, Peoples R China |
推荐引用方式 GB/T 7714 | Li, Duan,Sun, Xiaoling,Gu, Shenshen,et al. Polynomially Solvable Cases of Binary Quadratic Programs. 233 SPRING STREET, NEW YORK, NY 10013, UNITED STATES:SPRINGER,2010:199-225. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论