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

binary quadratic programming formulation for routing and wavelength assignment problem in all-optical WDM networks

OPTICAL SWITCHING AND NETWORKING 2013年第4期10卷 354-365页

作者： Ebrahimzadeh, Amin Rahbar, Akbar Ghaffarpour Alizadeh, Behrooz Sahand Univ Technol Elect Engn Res Ctr Comp Networks Res Lab Tabriz Iran Sahand Univ Technol Dept Math Tabriz Iran

Routing and wavelength assignment (RWA) is the most concern in wavelength routed optical networks. This paper proposes a novel binary quadratic programming (BQP) formulation for the static RWA problem in order to balance traffic load among a network links more fairly. Subsequently, a greedy heuristic algorithm namely variable-weight routing and wavelength assignment (VW-RWA) is proposed to solve the developed BQP problem. In this method, the weight of a link is proportional to the link congestion. Performance evaluation results for different practical network topologies show that our proposed algorithm can decrease the number of required wavelengths in the network, blocking rate and variance of used wavelengths in each link. Besides, it is shown that the number of required wavelengths to establish call requests for a given network topology can be reduced at lower cost compared to other heuristics. (C) 2013 Elsevier B.V. All rights reserved.

关键词： All-optical networks Static routing and wavelength assignment binary quadratic programming Integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Solving the maximum vertex weight clique problem via binary quadratic programming

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第2期32卷 531-549页

作者： Wang, Yang Hao, Jin-Kao Glover, Fred Lu, Zhipeng Wu, Qinghua Northwestern Polytech Univ Sch Management 127 Youyi West Rd Xian 710072 Peoples R China Univ Angers LERIA 2 Blvd Lavoisier F-49045 Angers France Inst Univ France Paris France OptTek Syst Inc 2241 17th St Boulder CO 80302 USA Huazhong Univ Sci & Technol Sch Comp Sci & Technol Wuhan 430074 Peoples R China Huazhong Univ Sci & Technol Sch Management Wuhan 430074 Peoples R China

In recent years, the general binary quadratic programming (BQP) model has been widely applied to solve a number of combinatorial optimization problems. In this paper, we recast the maximum vertex weight clique problem (MVWCP) into this model which is then solved by a probabilistic tabu search algorithm designed for the BQP. Experimental results on 80 challenging DIMACS-W and 40 BHOSLIB-W benchmark instances demonstrate that this general approach is viable for solving the MVWCP problem.

关键词： Maximum vertex weight clique binary quadratic programming Probabilistic tabu search

来源：评论

学校读者我要写书评

暂无评论

Global Optimization of binary quadratic programming: A Neural Network Based Algorithm and Its FPGA Implementation

引用

NEURAL PROCESSING LETTERS 2019年第3期53卷 1665-1684页

作者： Gu, Shenshen Chen, Xinyi Wang, Lin Shanghai Univ Sch Mechatron Engn & Automat 99 Shangda Rd Shanghai Peoples R China

The global optimization of binary quadratic programming (BQP) has very important theory and wide application in various fields. Since BQP is a classic NP-hard problem, traditional algorithms will be very time-consuming when the dimension is very large. The neural network based algorithms have significant advantages in solving large scale optimization problems. However, directly applying neural network based algorithm cannot guarantee finding the global optimal solution of BQP. In this paper, we propose a neural network based algorithm for BQP by analyzing and utilizing geometric characteristics of the objective function isosurface and combining the advantages and properties of neural network as well as branch-and-bound method. Furthermore, the neural network algorithm is implemented with field-programmable gate array (FPGA) to take advantage of the parallel structure. System Generator which can be used to convert the design into HDL code automatically is adopted so that the calculation of upper and lower bounds can be deployed to FPGA. The numerical simulation illustrates the effectiveness and efficiency of the algorithm. Meanwhile, simulation results show the feasibility of applying the proposed algorithm to FPGA hardware.

关键词： binary quadratic programming Branch-and-bound Neural network FPGA implementation

来源：评论

学校读者我要写书评

暂无评论

An augmented Lagrangian method for binary quadratic programming based on a class of continuous functions

引用

OPTIMIZATION LETTERS 2016年第3期10卷 485-497页

作者： Mu, Xuewen Liu, Wenlong Xidian Univ Sch Math & Stat Xian 710071 Peoples R China Dalian Univ Technol Sch Informat & Commun Engn Dalian 116024 Peoples R China

In this paper, an augmented Lagrangian method is proposed for binary quadratic programming (BQP) problems based on a class of continuous functions. The binary constraints are converted into a class of continuous functions. The approach reformulates the BQP problem as an equivalent augmented Lagrangian function, and then seeks its minimizer via an augmented Lagrangian method, in which the sub-problem is solved by Barzilai-Borwein type method. Numerical results are reported for max-cut problem. The results indicate that the augmented Lagrangian approach is promising for large scale binary quadratic programming by the quality of the near optimal values and the low computational time.

关键词： binary quadratic programming Augmented Lagrangian method Max-cut Barzilai-Borwein type method Continuous functions

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A Fast binary quadratic programming Solver Based on Stochastic Neighborhood Search

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2022年第1期44卷 32-49页

作者： Lam, Benson Shu Yan Liew, Alan Wee-Chung Hang Seng Univ Hong Kong Dept Math Stat & Insurance Sin Lek Yuen Hong Kong Peoples R China Griffith Univ Sch Informat & Commun Technol Brisbane Qld Australia

Many image processing and pattern recognition problems can be formulated as binary quadratic programming (BQP) problems. However, solving a large BQP problem with a good quality solution and low computational time is still a challenging unsolved problem. Current methodologies either adopt an independent random search in a semi-definite space or perform search in a relaxed biconvex space. However, the independent search has great computation cost as many different trials are needed to get a good solution. The biconvex search only searches the solution in a local convex ball, which can be a local optimal solution. In this paper, we propose a BQP solver that alternatingly applies a deterministic search and a stochastic neighborhood search. The deterministic search iteratively improves the solution quality until it satisfies the KKT optimality conditions. The stochastic search performs bootstrapping sampling to the objective function constructed from the potential solution to find a stochastic neighborhood vector. These two steps are repeated until the obtained solution is better than many of its stochastic neighborhood vectors. We compare the proposed solver with several state-of-the-art methods for a range of image processing and pattern recognition problems. Experimental results showed that the proposed solver not only outperformed them in solution quality but also with the lowest computational complexity.

关键词： binary quadratic programming stochastic optimization binary restoration graph bisection optimization

来源：评论

学校读者我要写书评

暂无评论

Polynomial time solvable algorithms to a class of unconstrained and linearly constrained binary quadratic programming problems

引用

NEUROCOMPUTING 2016年 198卷 171-179页

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

binary quadratic programming (BQP) is a typical integer programming problem widely applied in the field of signal processing, economy, management and engineering. However, it is NP-hard and lacks efficient algorithms. Due to this reason, in this paper, some novel polynomial algorithms are proposed to solve a class of unconstrained and linearly constrained binary quadratic programming problems. We first deduce the polynomial time solvable algorithms to the unconstrained binary quadratic programming problems with Q being a seven-diagonal matrix (UBQP7) and a five-diagonal matrix (UBQP5) respectively with two different approaches. Then, the algorithm to unconstrained problem is combined with the dynamic programming method to solve the linearly constrained binary quadratic programming problem with Q being a five-diagonal matrix (LCBQP5). In addition, the polynomial solvable feature of these algorithms is analyzed and some specific examples are presented to illustrate these new algorithms. Lastly, we demonstrate their polynomial feature as well as their high efficiency. (C) 2016 Elsevier B.V. All rights reserved.

关键词： binary quadratic programming Polynomial time solvable algorithm Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Optimizing LBP Structure For Visual Recognition Using binary quadratic programming

引用

IEEE SIGNAL PROCESSING LETTERS 2014年第11期21卷 1346-1350页

作者： Ren, Jianfeng Jiang, Xudong Yuan, Junsong Wang, Gang Nanyang Technol Univ Inst Media Innovat Being There Ctr Singapore 637553 Singapore Nanyang Technol Univ Sch Elect & Elect Engn Singapore 639798 Singapore

Local binary pattern (LBP) and its variants have shown promising results in visual recognition applications. However, most existing approaches rely on a pre-defined structure to extract LBP features. We argue that the optimal LBP structure should be task-dependent and propose a new method to learn discriminative LBP structures. We formulate it as a point selection problem: Given a set of point candidates, the goal is to select an optimal subset to compose the LBP structure. In view of the problems of current feature selection algorithms, we propose a novel Maximal Joint Mutual Information criterion. Then, the point selection is converted into a binary quadratic programming problem and solved efficiently via the branch and bound algorithm. The proposed LBP structures demonstrate superior performance to the state-of-the-art approaches on classifying both spatial patterns in scene recognition and spatial-temporal patterns in dynamic texture recognition.

关键词： binary quadratic programming dynamic texture recognition LBP structure optimization maximal joint mutual information scene recognition

来源：评论

学校读者我要写书评

暂无评论

On linearization techniques for budget-constrained binary quadratic programming problems

引用

OPERATIONS RESEARCH LETTERS 2016年第6期44卷 702-705页

作者： Yang, Mei-Jia Xia, Yong Zou, Hui-Min Beihang Univ Sch Math & Syst Sci Minist Educ State Key Lab Software Dev EnvironmLMIB Beijing 100191 Peoples R China Beijing Polytech Beijing 100176 Peoples R China

Glover's linearization technique is revisited for solving the binary quadratic programming problem with a budget constraint (BBQP). When compared with the recent two linearizations for (BBQP), it not only provides a tighter relaxation at the root node, but also has a much better computational performance for globally solving (BBQP). (C) 2016 Elsevier B.V. All rights reserved.

关键词： binary quadratic programming Budget constraint Linearization Linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

Radar Target Detection via Global Optimality Conditions for binary quadratic programming

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2023年 71卷 2502-2517页

作者： Zhao, Wenjing Cui, Guolong Jin, Minglu Wang, Yumiao Univ Elect Sci & Technol China Sch Informat & Commun Engn Chengdu 611731 Peoples R China Univ Elect Sci & Technol China Sch Elect Sci & Engn Chengdu 611731 Peoples R China Dalian Univ Technol Sch Informat & Commun Engn Dalian 116024 Peoples R China

This article considers the problem of radar target detection in compound Gaussian clutter background. Different from the existing detector design criteria, we propose two new detection schemes for the detection problem from the optimization perspective. Specifically, in the first scheme, the detection problem is firstly studied by introducing an auxiliary variable and transforming it into a maximum likelihood estimation problem. Under this scheme, the maximum likelihood detector and its improved version with parameter estimation are developed by using maximum likelihood criterion. In the second scheme, the detection problem is recast into a binary quadratic programming (BQP) problem. Resorting to the global optimality conditions and solution for the BQP problem, we design four BQP detectors named BQPH, BQPS, BQPM and BQPW with the aid of hard decision fusion, data fusion based on summation and taking median, and whitening respectively. At the analysis stage, the statistical distributions of the BQP detectors are modelled using t location-scale distribution, and the theoretical closed-form expressions of the false alarm probability, thresholds and detection probability of the four BQP detectors are further derived. Finally, simulation experiments on the simulated data and real sea clutter data are performed to highlight the effectiveness of the proposed detectors in comparison with several state-of-the-art detectors.

关键词： Radar target detection non-Gaussian clutter binary quadratic programming global optimality conditions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：