检索结果-内蒙古大学图书馆

Convex reformulation for binary quadratic programming problems via average objective value maximization

OPTIMIZATION LETTERS 2015年第3期9卷 523-535页

作者： Lu, Cheng Guo, Xiaoling Tsinghua Univ Dept Elect Engn Beijing 100084 Peoples R China Univ Chinese Acad Sci Coll Engn & Informat Technol Beijing 100049 Peoples R China

quadratic convex reformulation is an important method for improving the performance of a branch-and-bound based binary quadratic programming solver. In this paper, we study a new convex reformulation method. By this reformulation, the efficiency of a branch-and-bound algorithm can be improved significantly. We also compare this new reformulation method with other proposed methods, whose effectiveness has been proven. Numerical experimental results show that our reformulation method performs better than the compared methods for certain types of binary quadratic programming problems.

关键词： binary quadratic programming Lower bounds Branch-and-bound Convex reformulation

来源：评论

学校读者我要写书评

暂无评论

An Entropy-Regularized ADMM For binary quadratic programming

引用

JOURNAL OF GLOBAL OPTIMIZATION 2023年第2-4期87卷 447-479页

作者： Liu, Haoming De, Kangkang Liu, Haoyang Wen, Zaiwen Peking Univ Beijing Int Ctr Math Res Beijing Peoples R China Peking Univ Ctr Data Sci Beijing Int Ctr Math Res Beijing Peoples R China Peking Univ Coll Engn Beijing Peoples R China

We propose an entropy regularized splitting model using low-rank factorization for solving binary quadratic programming with linear inequality constraints. Different from the semidefinite programming relaxation model, our model preserves the rank-one constraint and aims to find high quality rank-one solutions directly. The factorization transforms the variables into low-rank matrices, while the entropy term enforces the low-rank property of the splitting variable. A customized alternating direction method of multipliers is utilized to solve the proposed model. Specifically, our method uses the augmented Lagrangian function to deal with inequality constraints, and solves one subproblem on the oblique manifold by a regularized Newton method. Numerical results on the multiple-input multiple-output detection problem, the maxcut problem and the quadratic 0 - 1 problem indicate that our proposed algorithm has advantage over the SDP methods.

关键词： binary quadratic programming Alternating direction method of multipliers Riemannian manifold Entropy penalty Low-rank factorization

来源：评论

学校读者我要写书评

暂无评论

f-Flip strategies for unconstrained binary quadratic programming

引用

ANNALS OF OPERATIONS RESEARCH 2016年第1-2期238卷 651-657页

作者： Glover, Fred Hao, Jin-Kao Univ Colorado Leeds Sch Business Boulder CO 80309 USA Univ Angers LERIA F-49045 Angers France Inst Univ France Paris France

Unconstrained binary quadratic programming (UBQP) provides a unifying modeling and solution framework for solving a remarkable range of binary optimization problems, including many accompanied by constraints. Current methods for solving UBQP problems customarily rely on neighborhoods consisting of flip moves that select one or more binary variables and "flip" their values to the complementary value (from 1 to 0 or from 0 to 1). We introduce a class of approaches called f-flip strategies that include a fractional value f as one of those available to the binary variables during intermediate stages of solution. A variety of different f-flip strategies, particularly within the context of multi-start algorithms, are proposed for pursuing intensification and diversification goals in metaheuristic algorithms, accompanied by special rules for evaluating and executing f-flips efficiently.

关键词： 0-1 Optimization binary quadratic programming Metaheuristics Multi-start algorithms Computational efficiency

来源：评论

学校读者我要写书评

暂无评论

On duality gap in binary quadratic programming

引用

JOURNAL OF GLOBAL OPTIMIZATION 2012年第2期53卷 255-269页

作者： Sun, X. L. Liu, C. L. Li, D. Gao, J. J. Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China Fudan Univ Sch Management Dept Management Sci Shanghai 200433 Peoples R China Shanghai Univ Finance & Econ Dept Appl Math Shanghai 200433 Peoples R China

We investigate in this paper the duality gap between the binary quadratic optimization problem and its semidefinite programming relaxation. We show that the duality gap can be underestimated by , where is the distance between {-1, 1} and certain affine subspace, and (+1) is the smallest positive eigenvalue of a perturbed matrix. We also establish the connection between the computation of and the cell enumeration of hyperplane arrangement in discrete geometry.

关键词： binary quadratic programming Duality gap Semidefinite programming relaxation Cell enumeration of hyperplane arrangement

来源：评论

学校读者我要写书评

暂无评论

On duality gap in binary quadratic programming

On duality gap in binary quadratic programming

引用

International Conference on Optimization and its Applications (ICOIA)

关键词： binary quadratic programming Duality gap Semidefinite programming relaxation Cell enumeration of hyperplane arrangement

来源：评论

学校读者我要写书评

暂无评论

引用

8th Annual Genetic and Evolutionary Computation Conference

作者： Amunrud, Jason Julstrom, Bryant A. St Cloud State Univ Dept Comp Sci St Cloud MN 56301 USA

ISBN: (纸本)9781595931863

When an evolutionary algorithm addresses a sequence of instances of the same problem, it can seed its population with solutions that it found for previous instances. This technique is called case injection. How similar must the instances be for case injection to help an EA's search? We consider this question by applying a genetic algorithm, without and with case injection, to sequences of instances of binary quadratic programming. When the instances are similar, case injection helps;when the instances differ sufficiently, case injection is no help at all.

关键词： case injection population seeding binary quadratic programming instance similarity

来源：评论

学校读者我要写书评

暂无评论

A Polynomial Time Solvable Algorithm to binary quadratic programming Problems with Q Being a Seven-Diagonal Matrix and Its Neural Network Implementation

A Polynomial Time Solvable Algorithm to Binary Quadratic Pro...

引用

11th International Symposium on Neural Networks (ISNN)

作者： Gu, Shenshen Peng, Jiao Cui, Rui Shanghai Univ Sch Mechatron Engn & Automat Shanghai Peoples R China

ISBN: (纸本)9783319124360;9783319124353

In this paper, we consider the binary quadratic programming problems (BQP). The unconstrained BQP is known to be NP-hard and has many practical applications like signal processing, economy, management and engineering. Due to this reason, many algorithms have been proposed to improve its effectiveness and efficiency. In this paper, we propose a novel algorithm based on the basic algorithm proposed in [1], [2], [3] to solve problem BQP with Q being a seven-diagonal matrix. It is shown that the proposed algorithm has good performance and high efficiency. To further improve its efficiency, the neural network implementation is realized.

关键词： binary quadratic programming NP-hard Neural network

来源：评论

学校读者我要写书评

暂无评论

A global continuation algorithm for solving binary quadratic programming problems

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2008年第3期41卷 349-362页

作者： Pan, Shaohua Tan, Tao Jiang, Yuxi S China Univ Technol Sch Math Sci Guangzhou 510640 Peoples R China Dalian Univ Technol Dept Engn Mech Dalian 116024 Peoples R China Dalian Jiaotong Univ Sch Management Dalian 116028 Peoples R China

In this paper, we propose a new continuous approach for the unconstrained binary quadratic programming (BQP) problems based on the Fischer-Burmeister NCP function. Unlike existing relaxation methods, the approach reformulates a BQP problem as an equivalent continuous optimization problem, and then seeks its global minimizer via a global continuation algorithm which is developed by a sequence of unconstrained minimization for a global smoothing function. This smoothing function is shown to be strictly convex in the whole domain or in a subset of its domain if the involved barrier or penalty parameter is set to be sufficiently large, and consequently a global optimal solution can be expected. Numerical results are reported for 0-1 quadratic programming problems from the OR-Library, and the optimal values generated are made comparisons with those given by the well-known SBB and BARON solvers. The comparison results indicate that the continuous approach is extremely promising by the quality of the optimal values generated and the computational work involved, if the initial barrier parameter is chosen appropriately.

关键词： binary quadratic programming Fischer-Burmeister function Logarithmic barrier function Global continuation algorithm

来源：评论

学校读者我要写书评

暂无评论

SOLVING UNCONSTRAINED binary quadratic programming PROBLEM BY GLOBAL EQUILIBRIUM SEARCH

引用

CYBERNETICS AND SYSTEMS ANALYSIS 2011年第6期47卷 889-897页

作者： Shylo, V. P. Shylo, O. V. Natl Acad Sci Ukraine VM Glushkov Inst Cybernet Kiev Ukraine Univ Pittsburgh Pittsburgh PA 15260 USA

A new algorithm based on global equilibrium search (GES) is developed to solve an unconstrained binary quadratic programming (UBQP) problem. It is compared with the best methods of solving this problem. The GES algori... 详细信息

关键词： binary quadratic programming approximate methods global equilibrium search computational experiment comparative analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

A New Relaxation Method for binary quadratic programming: An Application to Densest k-subgraph

A New Relaxation Method for Binary Quadratic Programming: An...

引用

2018 International Conference on Mathematics, Modelling, Simulation and Algorithms（MMSA2018）

作者： Chuanhao Guo Liping Tang School of Economics and Management Zhejiang Sci-Tech University College of Mathematics and Statistics Chongqing Technology and Business University

ISBN: (纸本)9781510863064

binary quadratic programming(BQP) problem was an NP-hard problem and had a large number of applications. In this paper, a new relaxation method, that was doubly nonnegative relaxation, was proposed for solving BQP problem. Moreover, we prove that the doubly nonnegative relaxation for BQP is equivalent to a new tighter semidifinite relaxation. When BQP problem reduces to densest k-subgraph problem, the doubly nonnegative relaxation is equivalent to a tighter semidifinite relaxation. Finally, some comparative numerical results are reported to show that the efficiency of the doubly nonnegative relaxation is more promising than that of semidefinite relaxation for solving some specific BQP problems.

关键词： binary quadratic programming doubly nonnegative relaxation semidefinite relaxation densest k-subgraph

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：