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

Solving the quadratic Minimum Spanning Tree Problem

APPLIED MATHEMATICS AND COMPUTATION 2012年第23期218卷 11597-11612页

作者： Cordone, Roberto Passeri, Gianluca Univ Milan Dipartimento Sci Informaz I-20135 Milan Italy Univ Milan Dipartimento Tecnol Informaz I-26013 Crema Italy

Given an undirected graph with costs associated to its edges and pairs of edges, the quadratic Minimum Spanning Tree Problem (QMSTP) requires to determine a spanning tree of minimum total cost. This is a proper model for network problems in which both routing and interference costs need to be considered. It is NP-hard in the strong sense and not approximable unless P = NP. This paper describes a Tabu Search algorithm, with two independent and adaptively tuned tabu lists, and a Variable Neighbourhood Search algorithm. Both metaheuristics are based on the same neighbourhood, but the Tabu Search proves more effective and robust than the Variable Neighbourhood Search. To assess the quality of these results, we provide a comparison with the heuristic algorithms proposed in the recent literature and we reimplement, with minor improvements, an exact algorithm drawn from the literature, which confirms the optimality of the results obtained on small instances. (C) 2012 Elsevier Inc. All rights reserved.

关键词： quadratic Minimum Spanning Tree Problem binary quadratic programming Tabu Search Variable Neighbourhood Search Branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

A Second-Order Cone programming Method for Multiuser Detection Problem

引用

WIRELESS PERSONAL COMMUNICATIONS 2011年第2期60卷 335-344页

作者： Mu, Xuewen Zhang, Yaling Xidian Univ Dept Appl Math Xian 710071 Peoples R China Xian Sci & Technol Univ Dept Comp Sci Xian 710054 Peoples R China

Based on the binary quadratic programming model of the CDMA maximum likelihood multiuser detection problem, a detection strategy by the second-order cone programming method is presented. The proposed method relaxes the binary quadratic programming model as a second-order cone programming model. Coupled with the sign function, a suboptimal solution is obtained for the multiuser detection problem. Comparing with the reported semidefinite programming method, simulations demonstrate that the second-order cone programming method often yields the similar bit error rate (BER) performances for the multiuser detection problem, but the average CPU time of this method is significantly reduced.

关键词： Multiuser detection problem binary quadratic programming Second-order cone programming

来源：评论

学校读者我要写书评

暂无评论

The Next Generation of Beam Hopping Satellite Systems: Dynamic Beam Illumination With Selective Precoding

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2023年第4期22卷 2666-2682页

作者： Chen, Lin Ha, Vu Nguyen Lagunas, Eva Wu, Linlong Chatzinotas, Symeon Ottersten, Bjorn Univ Luxembourg Interdisciplinary Ctr Secur Reliabil & Trust SnT L-1855 Luxembourg Luxembourg

Beam Hopping (BH) is a popular technique considered for next-generation multi-beam satellite communication system which allows a satellite focusing its resources on where they are needed by selectively illuminating beams. While beam illumination plan can be adjusted according to its needs, the main limitation of convectional BH is the adjacent beam avoidance requirement needed to maintain acceptable levels of interference. With the recent maturity of precoding technique, a natural way forward is to consider a dynamic beam illumination scheme with selective precoding, where large areas with high-demand can be covered by multiple active precoded beams. In this paper, we mathematically model such beam illumination design problem employing an interference-based penalty function whose goal is to avoid precoding whenever possible subject to beam demand satisfaction constraints. The problem can be written as a binary quadratic programming (BQP). Next, two convexification frameworks are considered namely: (i) A Semi-Definition programming (SDP) approach particularly targeting BQP type of problems, and (ii) Multiplier Penalty and Majorization-Minimization (MPMM) based method which guarantees to converge to a local optimum. Finally, a greedy algorithm is proposed to alleviate complexity with minimal impact on the final performance. Supporting results based on numerical simulations show that the proposed schemes outperform the relevant benchmarks in terms of demand matching performance while minimizing the use of precoding.

关键词： Dynamic beam illumination selective precoding user scheduling binary quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Variable objective search

引用

JOURNAL OF HEURISTICS 2013年第4期19卷 697-709页

作者： Butenko, Sergiy Yezerska, Oleksandra Balasundaram, Balabhaskar Texas A&M Univ College Stn TX 77843 USA Oklahoma State Univ Stillwater OK 74078 USA

This paper introduces the variable objective search framework for combinatorial optimization. The method utilizes different objective functions used in alternative mathematical programming formulations of the same combinatorial optimization problem in an attempt to improve the solutions obtained using each of these formulations individually. The proposed technique is illustrated using alternative quadratic unconstrained binary formulations of the classical maximum independent set problem in graphs.

关键词： Variable objective search binary quadratic programming Maximum independent set

来源：评论

学校读者我要写书评

暂无评论

Combinatorial optimization with one quadratic term: Spanning trees and forests

引用

DISCRETE APPLIED MATHEMATICS 2014年 177卷 34-52页

作者： Buchheim, Christoph Klein, Laura TU Dortmund Fak Math D-44227 Dortmund Germany

The standard linearization of a binary quadratic program yields an equivalent reformulation as an integer linear program, but the resulting LP-bounds are very weak in general. We concentrate on applications where the underlying linear problem is tractable and exploit the fact that, in this case, the optimization problem is still tractable in the presence of a single quadratic term in the objective function. We propose to strengthen the standard linearization by the use of cutting planes that are derived from jointly considering each single quadratic term with the underlying combinatorial structure. We apply this idea to the quadratic minimum spanning tree and spanning forest problems and present complete polyhedral descriptions of the corresponding problems with one quadratic term, as well as efficient separation algorithms for the resulting polytopes. Computationally, we observe that the new inequalities significantly improve dual bounds with respect to the standard linearization, particularly for sparse graphs. (C) 2014 Elsevier B.V. All rights reserved.

关键词： quadratic spanning tree polytope binary quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Dantzig-Wolfe reformulations for binary quadratic problems

引用

MATHEMATICAL programming COMPUTATION 2022年第1期14卷 85-120页

作者： Ceselli, Alberto Letocart, Lucas Traversi, Emiliano Univ Milan Dipartimento Informat Via Celoria 18 I-20133 Milan Italy Univ Sorbonne Paris Nord CNRS LIPN UMR 7030 99 Ave Jean Baptiste Clement F-93430 Villetaneuse France

The purpose of this paper is to provide strong reformulations for binary quadratic problems. We propose a first methodological analysis on a family of reformulations combining Dantzig-Wolfe and quadratic Convex optimization principles. We show that a few reformulations of our family yield continuous relaxations that are strong in terms of dual bounds and computationally efficient to optimize. As a representative case study, we apply them to a cardinality constrained quadratic knapsack problem, providing extensive experimental insights. We report and analyze in depth a particular reformulation providing continuous relaxations whose solutions turn out to be integer optima in all our tests.

关键词： binary quadratic programming Decomposition methods quadratic convex reformulation Column generation

来源：评论

学校读者我要写书评

暂无评论

Test-assignment: a quadratic coloring problem

引用

JOURNAL OF HEURISTICS 2013年第4期19卷 549-564页

作者： Duives, Jelle Lodi, Andrea Malaguti, Enrico Univ Twente NL-7500 AE Enschede Netherlands Univ Bologna DEIS Bologna Italy

We consider the problem of assigning the test variants of a written exam to the desks of a classroom in such a way that desks that are close-by receive different variants. The problem is a generalization of the Vertex Coloring and we model it as a binary quadratic problem. Exact solution methods based on reformulating the problem in a convex way and applying a general-purpose solver are discussed as well as a Tabu Search algorithm. The methods are extensively evaluated through computational experiments on real-world instances. The problem arises from a real need at the Faculty of Engineering of the University of Bologna where the solution method is now implemented.

关键词： binary quadratic programming Reformulations Heuristics

来源：评论

学校读者我要写书评

暂无评论

Polynomial-size formulations and relaxations for the quadratic multiple knapsack problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2021年第3期291卷 871-882页

作者： Galli, Laura Martello, Silvano Rey, Carlos Toth, Paolo Univ Pisa Dipartimento Informat Largo B Pontecorvo 3 I-56127 Pisa Italy Univ Bologna DEI Guglielmo Marconi Viale Risorgimento 2 I-40136 Bologna Italy

The quadratic Multiple Knapsack Problem generalizes, simultaneously, two well-known combinatorial optimization problems that have been intensively studied in the literature: the (single) quadratic Knapsack Problem and the Multiple Knapsack Problem. The only exact algorithm for its solution uses a formulation based on an exponential-size number of variables, that is solved via a Branch-and-Price algorithm. This work studies polynomial-size formulations and upper bounds. We derive linear models from classical reformulations of 0-1 quadratic programs and analyze theoretical properties and dominances among them. We define surrogate and Lagrangian relaxations, and we compare the effectiveness of the Lagrangian relaxation when applied to a quadratic formulation and to a Level 1 reformulation linearization that leads to a decomposable structure. The proposed methods are evaluated through extensive computational experiments. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization quadratic multiple knapsack binary quadratic programming Lagrangian relaxation Reformulation linearization technique

来源：评论

学校读者我要写书评

暂无评论

Switching Frequency Minimized Harmonic Mitigation: A Multiobjective Optimized Modulation Strategy for High- Power Converters

引用

IEEE TRANSACTIONS ON POWER ELECTRONICS 2023年第9期38卷 11080-11090页

作者： Pan, Suna Yang, Kehu Wu, Mingzhe Li, Xiongfeng Wang, Jiawen Li, Yun Wei Yu, Wensheng China Univ Min & Technol Sch Mech Elect & Informat Engn Beijing 100083 Peoples R China Univ Alberta Dept Elect & Comp Engn Edmonton AB T6G 1H9 Canada Beijing Univ Posts & Telecommun Sch Elect Engn Beijing 100876 Peoples R China

In order to explore the minimum switching frequency required to regulate certain amount of harmonic components, a novel switching frequencyminimized harmonic mitigation (SFMHM) model is proposed in this article, which can regulate N-1 harmonics with far less than N switching angles. By flexibly adjusting the threshold values, the proposed model can achieve both harmonic elimination and mitigation objectives. Based on pulsewidth modulation (PWM) discretization and supported by quadratic programming, the switching frequency in the proposed model is expressed as a quadratic objective function of the PWM waveform. The objectives as fundamental control and selected harmonic mitigations are realized by treating the numerical approximations of the Fourier coefficients as constraints, which are finally transformed into an optimization model with binary variables and can be easily solved by some optimization toolboxes, such as YALMIP. Some computing results show that, compared with the conventional selective harmonic elimination/mitigation (SHE/SHM) methods, the number of switching angles required to mitigate the same number of harmonics under the proposed method has been significantly reduced. The switching frequency can be reduced a lot compared with the conventional SHE/SHM methods, e.g., by 40% for some modulation indexes. Simulations and experiments verify the correctness of proposed SFMHM model.

关键词： binary quadratic programming harmonic mitigation multiobjective optimization switching frequency

来源：评论

学校读者我要写书评

暂无评论

Membership testing for Bernoulli and tail-dependence matrices

引用

JOURNAL OF MULTIVARIATE ANALYSIS 2018年 168卷 240-260页

作者： Krause, Daniel Scherer, Matthias Schwinn, Jonas Werner, Ralf Tech Univ Munich Math Finance Parkring 11 D-85748 Garching Germany Univ Augsburg Inst Math Univ Str 14 D-86159 Augsburg Germany

Testing a given matrix for membership in the family of Bernoulli matrices is a long-standing problem;the many applications of Bernoulli vectors in computer science, finance, medicine, and operations research emphasize its practical relevance. After the three-variate case was covered by Chaganty and Joe (2006) by means of partial correlations, a novel approach towards this problem was taken by Fiebig et al. (2017) for low-dimensional settings, i.e., d <= 6. The latter authors were the first to exploit the close relationship between the probabilistic world of Bernoulli matrices and the well-studied correlation and cut polytopes. Inspired by this approach, we use results from Deza and Laurent (1997), Embrechts et al. (2016), and Fiebig et al. (2017) in a pre-phase of a novel algorithm to check necessary as well as sufficient conditions, before actually testing a matrix for Bernoulli compatibility. In our main approach, however, we build upon an early attempt by Lee (1993) based on the vertex representation of the correlation polytope and directly solve the corresponding linear program. To deal appropriately with the issue of exponentially many primal variables, we propose a specifically tailored column generation method. A straightforward, yet novel, analysis of the arising subproblem of determining the most violated dual constraint in the column generation process leads to an exact algorithm for membership testing. Although the membership problem is known to be NP-complete, we observe very promising performance up to dimension d = 40 on a broad variety of test problems. An important byproduct of the numerical solution is a representation for Bernoulli matrices with (only) d(2) many vertices that gives rise to an efficient simulation routine. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Bernoulli-compatible matrix binary quadratic programming Column generation Tail-dependence matrix

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：