检索结果-南通市图书馆

Maximum-likelihood detection based on branch and bound algorithm for MIMO systems

在线全文

学校读者我要写书评

暂无评论

Science in China(Series F) 2008年第3期51卷 306-319页

作者： LI Zi CAI YueMing Institute of Communications Engineering PLA University of Science and Technology Nanjing 210007 China National Mobile Communications Research Laboratory Southeast University Nanjing 210096 China

Maximum likelihood detection for MIMO systems can be formulated as an integer quadratic programming problem. In this paper, we introduce depth-first branch and bound algorithm with variable dichotomy into MIMO detection. More nodes may be pruned with this structure. At each stage of the branch and bound algorithm, active set algorithm is adopted to solve the dual subproblem. In order to reduce the complexity further, the Cholesky factorization update is presented to solve the linear system at each iteration of active set algorithm efficiently. By relaxing the pruning conditions, we also present the quasi branch and bound algorithm which implements a good tradeoff between performance and complexity. Numerical results show that the complexity of MIMO detection based on branch and bound algorithm is very low, especially in low SNR and large constellations.

关键词： multiple-input multiple-output (MIMO) detection branch and bound active set dual Cholesky factorization

A branch and bound Algorithm for the Protein Folding Problem in the HP Lattice Model

在线全文

学校读者我要写书评

暂无评论

Genomics, Proteomics & Bioinformatics 2005年第4期3卷 225-230页

作者： Mao Chen Wen-Qi Huang School of Computer Science and Technology Huazhong University of Science and Technology Wuhan 430074China.

A branch and bound algorithm is proposed for the two-dimensional protein folding problem in the HP lattice model. In this algorithm, the benefit of each possible location of hydrophobic monomers is evaluated and only promising nodes are kept for further branching at each level. The proposed algorithm is compared with other well-known methods for 10 benchmark sequences with lengths ranging from 20 to 100 monomers. The results indicate that our method is a very efficient and promising tool for the protein folding problem.

关键词： protein folding HP model branch and bound lattice

branch and bound Algorithm for Globally Solving Minimax Linear Fractional Programming

在线全文

学校读者我要写书评

暂无评论

Chinese Quarterly Journal of Mathematics 2024年第4期39卷 388-398页

作者： WANG Hui-man SHEN Pei-ping LIANG Yu-xin School of Mathematics and Statistics North China University of Water Resources and Electric PowerZhengzhou 450046China

In this paper,we study the minimax linear fractional programming problem on a non-empty bounded set,called problem(MLFP),and we design a branch and bound algorithm to find a globally optimal solution of(MLFP).Firstly,we convert the problem(MLFP)to a problem(EP2)that is equivalent to ***,by applying the convex relaxation technique to problem(EP2),a convex quadratic relaxation problem(CQRP)is ***,the overall framework of the algorithm is given and its convergence is proved,the worst-case iteration number is also ***,experimental data are listed to illustrate the effectiveness of the algorithm.

关键词： Minimax linear fractional programming Global optimal solution branch and bound

分枝与定界(branch and bound)方法简介

在线全文

学校读者我要写书评

暂无评论

运筹学学报 1982年第1期 12-19页

作者：管梅谷山东师范学院

1引言不少组合最优化问题可以归结为下面的形式:max f (x)或min f(x),这里s是一个有限集合。让我们看几个例子。[例1]分配问题(Assignment Problem,以下简称为AP)设有n个人A,A,…,A,另外有n件工作B,Bm,…;B,又设A做工作B可以生产的价值... 详细信息

1引言不少组合最优化问题可以归结为下面的形式:max f (x)或min f(x),这里s是一个有限集合。让我们看几个例子。[例1]分配问题(Assignment Problem,以下简称为AP)设有n个人A,A,…,A,另外有n件工作B,Bm,…;B,又设A做工作B可以生产的价值为C,现在要分配每一个人A做一件工作B,规定每一个人都恰好

关键词：最优值下界最优解定界 branch and bound 分枝

A Taxonomy of Exact Methods for Partial Max-SAT

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Journal of Computer Science & Technology 2013年第2期28卷 232-246页

作者： Mohamed El Bachir Menai Tasniem Nasser Al-Yahya Department of Computer Science College of Computer and Information Sciences King Saud University

Partial Maximum Boolean Satisfiability （Partial Max-SAT or PMSAT） is an optimization variant of Boolean satisfiability （SAT） problem, in which a variable assignment is required to satisfy all hard clauses and a maximum number of soft clauses in a Boolean formula. PMSAT is considered as an interesting encoding domain to many reaHife problems for which a solution is acceptable even if some constraints are violated. Amongst the problems that can be formulated as such are planning and scheduling. New insights into the study of PMSAT problem have been gained since the introduction of the Max-SAT evaluations in 2006. Indeed, several PMSAT exact solvers have been developed based mainly on the Davis- Putnam-Logemann-Loveland （DPLL） procedure and branch and bound （B^B） algorithms. In this paper, we investigate and analyze a number of exact methods for PMSAT. We propose a taxonomy of the main exact methods within a general framework that integrates their various techniques into a unified perspective. We show its effectiveness by using it to classify PMSAT exact solvers which participated in the 2007~2011 Max-SAT evaluations, emphasizing on the most promising research directions.

关键词： Partial Max-SAT Davis-Putnam-Logenmann-Loveland branch and bound unsatisfiability pseudo-Boolean optimization

A NEW GLOBAL OPTIMIZATION ALGORITHM FOR MIXED-INTEGER QUADRATICALLY CONSTRAINED QUADRATIC FRACTIONAL PROGRAMMING PROBLEM

在线全文

学校读者我要写书评

暂无评论

Journal of Computational Mathematics 2024年第3期42卷 784-813页

作者： Bo Zhang Yuelin Gao Xia Liu Xiaoli Huang School of Civil and Hydraulic Engineering School of Mathematics and StatisticsNingxia UniversityYinchuan 750021China School of Mathematics and Information Science North Minzu UniversityYinchuan 750021China Ningxia Province Key Laboratory of Intelligent Information and Data Processing Yinchuan 750021China School of Mathematics and Statistics Ningxia UniversityYinchuan 750021China

The mixed-integer quadratically constrained quadratic fractional programming(MIQCQFP)problem often appears in various fields such as engineering practice,management science and network ***,most of the solutions to such problems are often designed for their unique *** paper puts forward a new global optimization algorithm for solving the problem *** first convert the MIQCQFP into an equivalent generalized bilinear fractional programming(EIGBFP)problem with integer ***,we linearly underestimate and linearly overestimate the quadratic functions in the numerator and the denominator respectively,and then give a linear fractional relaxation technique for EIGBFP on the basis of non-negative *** that,combining rectangular adjustment-segmentation technique and midpointsampling strategy with the branch-and-bound procedure,an efficient algorithm for solving MIQCQFP globally is ***,a series of test problems are given to illustrate the effectiveness,feasibility and other performance of this algorithm.

关键词： Global optimization branch and bound Quadratic fractional programming Mixed integer programming

Global Optimization Method for Linear Multiplicative Programming

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2015年第2期31卷 325-334页

作者： Xue-gang ZHOU Bing-yuan CAO Kun WU School of Mathematics and Information Science Key Laboratory of Mathematics and Interdisciplinary Sciences of Guangdong Higher Education Institutes Guangzhou University Department of Applied Mathematics Guangdong University of Finance School of Mathematical Science and Computing Technology Center South University

In this paper, a new global algorithm is presented to globally solve the linear multiplicative programming（LMP）. The problem（LMP） is firstly converted into an equivalent programming problem（LMP（H））by introducing p auxiliary variables. Then by exploiting structure of（LMP（H））, a linear relaxation programming（LP（H）） of（LMP（H）） is obtained with a problem（LMP） reduced to a sequence of linear programming problems. The algorithm is used to compute the lower bounds called the branch and bound search by solving linear relaxation programming problems（LP（H））. The proposed algorithm is proven that it is convergent to the global minimum through the solutions of a series of linear programming problems. Some examples are given to illustrate the feasibility of the proposed algorithm.

关键词： linear multiplicative programming global optimization linear programming branch and bound

Optimal Component Types for the Design of Construction Processes

在线全文

学校读者我要写书评

暂无评论

Tsinghua Science and Technology 2008年第S1期13卷 317-324页

作者： Felix Enge Wolfgang Huhnt Chair of Process Modelling in Civil Engineering Berlin Institute of Technology

Within the project preparation phase, experienced professionals manually map design information onto process information with the aim to develop realistic and practical schedules. Unfortunately, the mapping itself is neither part of any underlying data model nor is it supported by current scheduling tools. As a consequence the process of setting up the data model for a schedule is still not supported formally. Huhnt and Enge described a modelling technique that addresses the missing linkage between design and process information[1]. The approach makes use of so called component types. These are template sub-processes that describe the fabrication procedure of typical building components. Decomposing the building into com-ponents and assigning a component type to each component allows for formal support while scheduling. Depending on the decomposition of the building into components and the complexity of the involved component types the specification effort differs. The question about optimal component types arises: Which layout of building components and component types results in minimal specification effort? This paper presents a branch and bound algorithm to determine optimal component types. For a given schedule, which has been modelled based on component types, all possible decompositions into sub-processes are determined. During the decomposition process the encountered configurations are compared. Those with minimal specifica-tion effort are registered. Theoretical and practical examples are examined and discussed.

关键词： scheduling process modelling planning processes construction processes branch and bound pattern matching search algorithm optimization

Optimization of observing sequence based on nominal trajectories of symmetric observing con guration

在线全文

学校读者我要写书评

暂无评论

Astrodynamics 2018年第1期2卷 25-37页

作者： Hongwei Yang Gao Tang Fanghua Jiang School of Aerospace Engineering Tsinghua UniversityBeijing 100084China Department of Mechanical Engineering and Materials Science Duke UniversityDurhamNC 27708USA

This paper presents the crucial method for obtaining our team's results in the 8th Global Trajectory Optimization Competition(GTOC8).Because the positions and velocities of spacecraft cannot be completely determined by one observation on one radio source,the branch and bound method for sequence optimization of multi-asteroid exploration cannot be directly applied *** overcome this diculty,an optimization method for searching the observing sequence based on nominal low-thrust trajectories of the symmetric observing con guration is *** the symmetric observing con guration,the normal vector of the triangle plane formed by the three spacecraft rotates in the ecliptic plane periodically and approximately points to the radio sources which are close to the ecliptic *** possible observing opportunities are selected and ranked according to the nominal trajectories designed by the symmetric observing con ***,the branch and bound method is employed to nd the optimal sequence of the radio source with thrice ***,this method is also used to nd the optimal sequence of the left radio *** nominal trajectories are then corrected for accurate *** performance index of our result is 128,286,317.0 km which ranks the second place in GTOC8.

关键词： branch and bound optimization symmetric observing configuration GTOC low thrust