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

6th International Conference on Wireless Communications, Networking and Mobile Computing (WICOM)

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

ISBN: (纸本)9781424437092

Based on the special kind of spreading sequence and semidefinite programming relaxation, A new multiuser detector for asynchronous code division multiple access system is presented. At each transmitter, the special spreading sequence whose second half is the replica of the first is employed. Maximum-likelihood(ML) multiuser detection only need detect 2K once. Then ML detection can be efficiently and accurately approximated using the semidefinite relaxation. Its time complexity decrease to the order of O(2K(3.5)), while the Viterbi Algorithm (optimum detector) requires a exponentially computational complexity. We compare the performances of the new SDP method and a joint method of block coordinate ascent and semidefinite programming relaxation(BCA-SDR) method for the asynchronous multiuser detection problem in various situations, and simulations demonstrate that the new semidefinite programming method often yields better bit error rate (BER) performances than the BCA-SDR method, but the average CPU time of this method is significantly reduced.

关键词： Asynchronous multiuser detection problem binary quadratic programming semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Efficient Multi-Robot Task Allocation with Nonsmooth Objective Functions for Persistent Monitoring in Large Dispersed Areas 20

Efficient Multi-Robot Task Allocation with Nonsmooth Objecti...

引用

IEEE 20th International Conference on Automation Science and Engineering (CASE)

作者： Fikri, Muhamad Rausyan Atman, Made Widhi Surya Nikulin, Yury Gusrialdi, Azwirman Tampere Univ Fac Engn & Nat Sci Automat Technol & Mech Engn Tampere 33720 Finland Univ Turku Dept Math & Stat Vesilinnantie 5 Turku 20014 Finland

ISBN: (纸本)9798350358513;9798350358520

This paper considers the multi-robot task allocation problem for persistent monitoring over large dispersed areas. The problem is formulated as a binary optimization problem with nonsmooth objective functions. To solve this optimization problem, we first propose quadratic objective functions to approximate the original nonsmooth objective functions. Inspired by the nature of the constraint of the problem, a simple strategy is presented to ensure the concavity of the quadratic functions. Finally, the fact that the constraint matrix of the optimization problem is totally unimodular allows us to relax the binary decision variables into continuous ones without changing the optimal solutions. We demonstrate using a case study that compared to the original problem, the proposed approximation provides less computational burden for small-size problems with occasional negligible trade-offs in the optimality of the solution. The comparison of the two objective functions for task allocation is also provided.

关键词： binary quadratic programming Concave Function Totally Unimodular Multi-Robot Task Allocation

来源：评论

学校读者我要写书评

暂无评论

Switching Losses Minimized Harmonic Elimination for Two-level Inverters 13

Switching Losses Minimized Harmonic Elimination for Two-leve...

引用

13th IEEE Energy Conversion Congress and Exposition (IEEE ECCE)

作者： Yang, Kehu Pan, Suna Li, Huawei China Univ Min & Technol Sch Mech Elect & Informat Engn Beijing Peoples R China Beijing Inst Aerosp Test Technol Beijing Peoples R China

ISBN: (纸本)9781728151359

In selective harmonic elimination (SHE), if there are N switching angles, N-1 harmonics can be eliminated, however, can we use fewer switching angles to eliminate the same number of harmonics? No one has ever thought about this question. In this paper, based on the discrete representation of two-level PWM waveforms, a binary quadratic programming (BQP) model is proposed to minimize the switching losses and meanwhile eliminate the harmonics. In this model, the switching losses which is closely related to the jump times of the PWM waveform is formulated to a quadratic objective function, and the numerical approximation of the Fourier coefficients are treated as the constraints which control the fundamental and eliminate the harmonics. This BQP model is solved by using the optimization toolbox YALMIP and some results are given, in which the switching angles required to eliminate the same number of harmonics are significantly reduced compared to the SHE method. Experiments on a two-level inverter verify the correctness of this method.

关键词： harmonic elimination switching losses binary quadratic programming

来源：评论

学校读者我要写书评

暂无评论

BiqCrunch: A Semidefinite Branch-and-Bound Method for Solving binary quadratic Problems

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2017年第4期43卷 32-32页

作者： Krislock, Nathan Malick, Jerome Roupin, Frederic Northern Illinois Univ De Kalb IL 60115 USA CNRS Lab J Kunztmann Grenoble France Univ Paris 13 CNRS UMR 7030 LIPN Sorbonne Paris Cite F-93430 Villetaneuse France No Illinois Univ Dept Math Sci De Kalb IL 60115 USA

This article presents BiqCrunch, an exact solver for binary quadratic optimization problems. BiqCrunch is a branch-and-bound method that uses an original, efficient semidefinite-optimization-based bounding procedure. It has been successfully tested on a variety of well-known combinatorial optimization problems, such as Max-Cut, Max-k-Cluster, and Max-Independent-Set. The code is publicly available online;a web interface and many conversion tools are also provided.

关键词： binary quadratic programming exact resolution NP-hard semidefinite relaxations quasi-Newton

来源：评论

学校读者我要写书评

暂无评论

BiqBin: A Parallel Branch-and-bound Solver for binary quadratic Problems with Linear Constraints

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2022年第2期48卷 15-15页

作者： Gusmeroli, Nicolo Hrga, Timotej Luzar, Borut Povh, Janez Siebenhofer, Melanie Wiegele, Angelika Alpen Adria Univ Klagenfurt Univ Str 65-67 A-9020 Klagenfurt Austria Univ Ljubljana Fac Mech Engn Askerceva C 6 Ljubljana 1000 Slovenia Fac Informat Studies Novo Mesto Slovenia Fac Informat Studies Novo Mesto Ljubljanska Cesta 31a Novo Mesto 6038000 Slovenia

We present BiqBin, an exact solver for linearly constrained binary quadratic problems. Our approach is based on an exact penalty method to first efficiently transform the original problem into an instance of Max-Cut, and then to solve the Max-Cut problem by a branch-and-bound algorithm. All the main ingredients are carefully developed using new semidefinite programming relaxations obtained by strengthening the existing relaxations with a set of hypermetric inequalities, applying the bundle method as the bounding routine and using new strategies for exploring the branch-and-bound tree. Furthermore, an efficient C implementation of a sequential and a parallel branch-and-bound algorithm is presented. The latter is based on a load coordinator-worker scheme using MPI for multi-node parallelization and is evaluated on a high-performance computer. The new solver is benchmarked against BiqCrunch, GUROBI, and SCIP on four families of (linearly constrained) binary quadratic problems. Numerical results demonstrate that BiqBin is a highly competitive solver. The serial version outperforms the other three solvers on the majority of the benchmark instances. We also evaluate the parallel solver and show that it has good scaling properties. The general audience can use it as an on-line service available at http://***.

关键词： Solvers semidefinite programming binary quadratic programming parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Multi-wave tabu search for the boolean quadratic programming problem with generalized upper bound constraints

引用

COMPUTERS & OPERATIONS RESEARCH 2023年 150卷

作者： Shang, Zhen Hao, Jin-Kao Zhao, Songzheng Wang, Yang Ma, Fei Changan Univ Sch Econ & Management Middle Sect Naner Huan Rd Xian 710064 Peoples R China Northwestern Polytech Univ Sch Management 127 Youyi West Rd Xian 710072 Peoples R China Univ Angers LERIA 2 Blvd Lavoisier F-49045 Angers France

The boolean quadratic programming problem with generalized upper bound constraints (BQP-GUB) is an NP-hard problem with many practical applications. In this study, we propose an effective multi-wave tabu search algorithm for solving BQP-GUB. The algorithm performs a sequence of search waves, where each wave alternates between the forward and reverse phases, and the transition between two adjacent waves depends on a hybrid perturbation phase. The forward phase employs tabu search to reach a critical solution and the reverse phase follows to reverse previously performed moves and perform an equal number of moves by referring to the search information gathered from the latest search process. The hybrid perturbation phase randomly chooses a directed strategy, a frequency guided strategy and a recency guided strategy to achieve search diversification. Experimental results on 78 standard instances indicate that the proposed algorithm is able to improve the lower bounds for 6 instances and match the best solutions in the literature for most instances within competitive time.

关键词： binary quadratic programming Tabu search Hybrid metaheuristic Graph theory

来源：评论

学校读者我要写书评

暂无评论

A Dual Bounding Framework Through Cost Splitting for binary quadratic Optimization

引用

INFORMS JOURNAL ON COMPUTING 2024年第6期36卷 1359-1756, C2页

作者： Bayani, Mahdis Rostami, Borzou Adulyasak, Yossiri Rousseau, Louis-Martin Polytech Montreal Montreal PQ H3T 1J4 Canada Univ Montreal CIRRELT Montreal PQ H3T 1J4 Canada GERAD Montreal PQ H3T 2A7 Canada Univ Alberta Alberta Sch Business Edmonton AB T6G 2R3 Canada HEC Montreal Montreal PQ H3T 2A7 Canada

binary quadratic programming (BQP) is a class of combinatorial optimization problems comprising binary variables, quadratic objective functions, and linear/nonlinear constraints. This paper examines a unified framework to reformulate a BQP problem with linear constraints to a new BQP with an exponential number of variables defined on a graph. This framework relies on the concept of stars in the graph to split the quadratic costs into adjacent and nonadjacent components indicating in -star and out -of -star interactions. We exploit the star -based structure of the new reformulation to develop a decompositionbased column generation algorithm. In our computational experiments, we evaluate the performance of our methodology on different applications with different quadratic structures. The quadratic component of the problem is dealt with in the column generation master problem and its subproblem. Results indicate the superiority of the framework over one of the state-of-the-art solvers, GUROBI, when applied to various benchmark reformulations with adjacent -only or sparse quadratic cost matrices. The framework outperforms GUROBI in terms of both dual bound and computational time in almost all instances.

关键词： binary quadratic programming combinatorial optimization column generation semi-assignment problem multiple object tracking problem

来源：评论

学校读者我要写书评

暂无评论

On-Off Scheduling for Electric Vehicle Charging in Two-Links Charging Stations Using binary Optimization Approaches

引用

SENSORS 2021年第21期21卷 7149页

作者： Zdunek, Rafal Grobelny, Andrzej Witkowski, Jerzy Gnot, Radoslaw Igor Wroclaw Univ Sci & Technol Fac Elect Photon & Microsyst Wybrzeze Wyspianskiego 27 PL-50370 Wroclaw Poland Elocity Sp Zoo Pl Wolnica 13-10 PL-31060 Krakow Poland

In this study, we deal with the problem of scheduling charging periods of electrical vehicles (EVs) to satisfy the users' demands for energy consumption as well as to optimally utilize the available power. We assume three-phase EV charging stations, each equipped with two charging ports (links) that can serve up to two EVs in the scheduling period but not simultaneously. Considering such a specification, we propose an on-off scheduling scheme wherein control over an energy flow is achieved by flexibly switching the ports in each station on and off in a manner such as to satisfy the energy demand of each EV, flatten the high energy-consuming load on the whole farm, and to minimize the number of switching operations. To satisfy these needs, the on-off scheduling scheme is formulated in terms of a binary linear programming problem, which is then extended to a quadratic version to incorporate the smoothness constraints. Various algorithmic approaches are used for solving a binary quadratic programming problem, including the Frank-Wolfe algorithm and successive linear approximations. The numerical simulations demonstrate that the latter is scalable, efficient, and flexible in a charging procedure, and it shaves the load peak while maintaining smooth charging profiles.

关键词： electrical vehicles EV charging scheduling binary linear programming binary quadratic programming

来源：评论

学校读者我要写书评

暂无评论

binary programs for asymmetric betweenness problems and relations to the quadratic linear ordering problem

引用

EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION 2023年第1期11卷

作者： Mallach, Sven Univ Bonn High Performance Comp & Analyt Lab Friedrich Hirzebruch Allee 8 D-53115 Bonn Germany

We present and compare novel binary programs for linear ordering problems that involve the notion of asymmetric betweenness and expose relations to the quadratic linear ordering problem and its linearization. While two of the binary programs prove particularly superior from a computational point of view when many or all betweenness relations shall be modeled, the others arise as natural formulations that resemble important theoretical correspondences and provide a compact alternative for sparse problem instances. A reasoning for the strengths and weaknesses of the different formulations is derived by means of polyhedral considerations with respect to their continuous relaxations.& COPY;2023 The Author(s). Published by Elsevier Ltd on behalf of Association of European Operational Research Societies (EURO). This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： Linear ordering problem Betweenness problem Facility layout problem Mixed-integer programming binary quadratic programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：