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

SOME EXPERIENCES WITH SOLVING SEMIDEFINITE programming RELAXATIONS OF binary quadratic OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2014年第4期31卷 1450022-1450022页

作者： Engau, Alexander Univ Colorado Dept Math & Stat Sci Denver CO 80217 USA China Agr Univ Int Coll Beijing Beijing 100083 Peoples R China

We present two recent integer programming models in molecular biology and study practical reformulations to compute solutions to some of these problems. In extension of previously tested linearization techniques, we formulate corresponding semidefinite relaxations and discuss practical rounding strategies to find good feasible approximate solutions. Our computational results highlight the possible advantages and remaining challenges of this approach especially on large-scale problems.

关键词： Combinatorial optimization integer programming binary quadratic programming semidefinite programming doubly non-negative relaxation computational biology protein folding protein similarity rotamer assignment contact map overlap

来源：评论

学校读者我要写书评

暂无评论

SDP-based Benders decomposition for solving p -median quadratic facility location problems

引用

Computers & Operations Research 2025年 182卷

作者： Yingying Yang Hoa T. Bui Ryan Loxton ARC Centre for Transforming Maintenance through Data Science Curtin University Perth Australia Curtin Centre for Optimisation and Decision Science Curtin University Perth Australia

The p -median facility location problem involves selecting the locations for p facilities from a set of potential locations, to balance the trade-off between facility establishment costs and distance to end users. In this paper, we introduce an extension, named the p -median quadratic facility location problem, that also considers inter-facility distance—important in applications where the facilities serve as intermediate hubs linking sites in different regions. This creates a quadratic term in the objective that makes the problem nonlinear. We develop a Benders decomposition method that uses a tight semi-definite programming relaxation of the Benders master problem, instead of solving the nonlinear master problem directly. We incorporate this decomposition strategy into a branch and bound framework to ensure convergence. Our numerical results show that this method outperforms the linear reformulation and classical Benders decomposition techniques, working independently or in tandem.

关键词： Facility location problem binary quadratic programming Benders decomposition Semi-definite programming

来源：评论

学校读者我要写书评

暂无评论

A Continuous Relaxation Method for Multiuser Detection Problem

引用

WIRELESS PERSONAL COMMUNICATIONS 2013年第3期71卷 2067-2077页

作者： Mu, Xuewen Zhang, Yaling Xidian Univ Dept 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 code division multiple access maximum likelihood multiuser detection problem, a detection strategy by the continuous relaxation method is presented. The proposed method relaxes the binary quadratic programming as a nonlinear programming, which is a quadratic objective function with simple quadratic constraints. A feasible direction method is used to solve the nonlinear programming. Based on the KKT solution of the nonlinear programming, a near optimal solution is obtained for the multiuser detection problem. Simulation results show that the bit error rate performances of a detection strategy based on the continuous relaxation method is low. Furthermore, average CPU time of continuous relaxation method is much lower than that of the semidefinite programming relaxation method, especially for the large-scale detection problems. This approach provides good approximations to the optimal maximum likelihood performance.

关键词： Multiuser detection problem binary quadratic programming Continuous relaxation method Semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Discovering the Thematic Object in Commercial Videos

引用

IEEE MULTIMEDIA 2011年第3期18卷 56-64页

作者： Zhao, Gangqiang Yuan, Junsong Xu, Jiang Wu, Ying Nanyang Technol Univ Singapore 639798 Singapore Northwestern Univ Dept Elect Engn & Comp Sci Evanston IL 60208 USA

The thematic object in a commercial video is representative of its content. The authors propose a data-mining method for thematic object discovery in commercials by finding spatially collocated visual features.

关键词： Videos Visualization Feature extraction Video sequences Data mining Search problems Optimization branch-and-bound search thematic video object discovery spatially collocated word group binary quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Global equilibrium search applied to the unconstrained binary quadratic optimization problem

引用

OPTIMIZATION METHODS & SOFTWARE 2008年第1期23卷 129-140页

作者： Pardalos, Panos M. Prokopyev, Oleg A. Shylo, Oleg V. Shylo, Vladimir P. Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Univ Pittsburgh Dept IE Pittsburgh PA USA NAS Ukraine Inst Cybernet Kiev Ukraine

We describe a heuristic method for solving the unconstrained binary quadratic optimization problem based on a global equilibrium search framework. We investigate performance of the proposed approach and compare it with the best available solver [G. Palubeckis, Multistart tabu search strategies for the unconstrained binary quadratic optimization problem, Ann. Oper. Res., 131 (2004), pp. 259-282;G. Palubeckis, Unconstrained binary quadratic optimization. Available at http://***/similar to gintaras/*** (Last accessed December 2006).] on well-known benchmarks instances. The reported computational results indicate a high efficiency of the heuristic.

关键词： global equilibrium search tabu search binary quadratic programming

来源：评论

学校读者我要写书评

暂无评论

A quadratic simplex algorithm for primal optimization over zero-one polytopes

引用

DISCRETE APPLIED MATHEMATICS 2024年 347卷 285-296页

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

A primal quadratic simplex algorithm tailored to the optimization over the vertices of a polytope is presented. Starting from a feasible vertex, it performs either strictly improving or admissible non -deteriorating steps in order to determine a locally optimum basic feasible solution in terms of the quadratic objective function. The algorithm so generalizes over local improvement methods for according applications, including in particular quadratic optimization problems whose feasible solutions correspond to vertices of a 0-1 polytope. Computational experiments for unconstrained binary quadratic programs, maximum cut, and the quadratic assignment problem serve as a proof of concept and underline the importance of a pivoting rule that is able to accept at least a restricted class of degenerate steps. (c) 2024 Elsevier B.V. All rights reserved.

关键词： Simplex algorithm Linearly-constrained quadratic programming binary quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Joint Power Allocation and Beam Scheduling in Beam-Hopping Satellites: A Two-Stage Framework With a Probabilistic Perspective

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2024年第10期23卷 14685-14701页

作者： Chen, Lin Wu, Linlong Lagunas, Eva Wang, Anyue Lei, Lei Chatzinotas, Symeon Ottersten, Bjorn Univ Luxembourg Interdisciplinary Ctr Secur Reliabil & Trust SnT L-1855 Luxembourg Luxembourg Xi An Jiao Tong Univ Sch Informat & Commun Engn Xian 710049 Peoples R China

Beam-hopping (BH) technology, integral to multi-beam satellite systems, adapts beam activation to the variable communication demands of terrestrial users. The optimization of power allocation and beam illumination scheduling constitutes the core design challenge in BH systems, especially under the constraint on a limited number of simultaneously active beams due to restricted radio frequency chain availability. This paper proposes a two-stage BH design solution, which minimizes energy consumption in BH satellite communications while accommodating the heterogeneous demands of users. The first stage addresses the coupling variables of power and beam status by recasting the allocation and scheduling problem through a statistical lens, thus breaking down the intricate relationship between variables. To manage the resulting non-convex challenge, we propose an iterative method that capitalizes on the optimality conditions inherent to this problem. This method is designed to procure a statistically-informed solution that aligns with our reformulated interpretation. Subsequently, the second stage maps this solution into a concrete beam illumination schedule, employing binary quadratic programming techniques. A penalty-based iterative method is applied, ensuring convergence to a locally optimal solution. Through numerical simulations, the proposed framework has been validated for its efficacy in improving energy efficiency and accurately matching demands.

关键词： Satellites Lighting Satellite broadcasting Resource management Vectors Payloads Wireless communication Energy minimization power control beam hopping binary quadratic programming

来源：评论

学校读者我要写书评

暂无评论

ON INTEGRALITY IN SEMIDEFINITE programming FOR DISCRETE OPTIMIZATION

引用

SIAM JOURNAL ON OPTIMIZATION 2024年第1期34卷 1071-1096页

作者： De Meijer, Frank Sotirov, Renata Delft Univ Technol Delft Inst Appl Math NL-2628 CD Delft Netherlands Tilburg Univ Dept Econometr & OR NL-5037 AB Tilburg Netherlands

It is well known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max -cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been derived. Based on a comprehensive study on discrete positive semidefinite matrices, we introduce a generic approach to derive mixed -integer SDP (MISDP) formulations of binary quadratically constrained quadratic programs and binary quadratic matrix programs. Applying a problem -specific approach, we derive more compact MISDP formulations of several problems, such as the quadratic assignment problem, the graph partition problem, and the integer matrix completion problem. We also show that several structured problems allow for novel compact MISDP formulations through the notion of association schemes. Complementary to the recent advances on algorithmic aspects related to MISDP, this work opens new perspectives on solution approaches for the here considered problems.

关键词： mixed-integer semidefinite programming discrete positive semidefinite matrices binary quadratic programming quadratic matrix programming association schemes

来源：评论

学校读者我要写书评

暂无评论

Construction and improvement algorithms for dispersion problems

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2015年第1期242卷 21-33页

作者： Aringhieri, Roberto Cordone, Roberto Grosso, Andrea Univ Turin Dipartimento Informat I-10149 Turin Italy Univ Milan Dipartimento Informat I-20135 Milan Italy

Given a set N, a pairwise distance function d and an integer number m, the Dispersion Problems (DPs) require to extract from N a subset M of cardinality m, so as to optimize a suitable function of the distances between the elements in M. Different functions give rise to a whole family of combinatorial optimization problems. In particular, the max-sum DP and the max-min DP have received strong attention in the literature. Other problems (e.g., the max-minsum DP and the min-diffsum DP) have been recently proposed with the aim to model the optimization of equity requirements, as opposed to that of more classical efficiency requirements. Building on the main ideas which underly some state-of-the-art methods for the max-sum DP and the max-min DP, this work proposes some constructive procedures and a Tabu Search algorithm for the new problems. In particular, we investigate the extension to the new context of key features such as initialization, tenure management and diversification mechanisms. The computational experiments show that the algorithms applying these ideas perform effectively on the publicly available benchmarks, but also that there are some interesting differences with respect to the DPs more studied in the literature. As a result of this investigation, we also provide optimal results and bounds as a useful reference for further studies. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Dispersion problems binary quadratic programming Tabu Search

来源：评论

学校读者我要写书评

暂无评论

Inductive linearization for binary quadratic programs with linear constraints: a computational study

引用

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 2024年第1期22卷 47-87页

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

The computational utility of inductive linearizations for binary quadratic programs when combined with a mixed-integer programming solver is investigated for several combinatorial optimization problems and established... 详细信息

关键词： Non-linear programming binary quadratic programming Mixed-integer programming Linearization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：