QQ客服 官方微博 反馈留言

	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.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。