Solving large-scale sparse semidefinite programs for combinatorial optimization

Benson SJ.; Zhang X.; Ye YY.

首页> 外文期刊>SIAM Journal on Optimization: A Publication of the Society for Industrial and Applied Mathematics >Solving large-scale sparse semidefinite programs for combinatorial optimization

【24h】

Solving large-scale sparse semidefinite programs for combinatorial optimization

机译：求解大规模稀疏半定程序以进行组合优化

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

We present a dual-scaling interior-point algorithm and show how it exploits the structure and sparsity of some large-scale problems. We solve the positive semidefinite relaxation of combinatorial and quadratic optimization problems subject to boolean constraints. We report the first computational results of interior-point algorithms for approximating maximum cut semidefinite programs with dimension up to 3,000. [References: 36]

机译：我们提出了一种双尺度内点算法，并展示了其如何利用某些大规模问题的结构和稀疏性。我们解决了受布尔约束约束的组合和二次优化问题的正半定松弛。我们报告了内部点算法的第一个计算结果，该算法用于逼近尺寸最大为3,000的最大割半定程序。 [参考：36]

著录项

来源
《SIAM Journal on Optimization: A Publication of the Society for Industrial and Applied Mathematics》 |2000年第2期|共19页
作者
Benson SJ.; Zhang X.; Ye YY.;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类应用数学;
关键词
Semidefinite programming; Dual potential reduction algorithm; Maximum cut problem; Interior-point methods; Algorithms; Graph;

机译：半定规划;双电位降低算法;最大割问题;内点法;算法;图;

相似文献

外文文献
中文文献
专利

1. Solving large-scale sparse semidefinite programs for combinatorial optimization [J] . Benson SJ., Zhang X., Ye YY. SIAM Journal on Optimization: A Publication of the Society for Industrial and Applied Mathematics . 2000,第2期

机译：求解大规模稀疏半定程序以进行组合优化
2. Implementation of a block-decomposition algorithm for solving large-scale conic semidefinite programming problems [J] . Renato D.C. Monteiro, Camilo Ortiz, Benar F. Svaiter Computational optimization and applications . 2014,第1期

机译：解决大规模圆锥半定规划问题的块分解算法的实现
3. Implementation of a Large-Scale Optimal Power Flow Solver Based on Semidefinite Programming [J] . Molzahn D.K., Holzer J.T., Lesieutre B.C., IEEE Transactions on Power Systems . 2013,第4期

机译：基于半定规划的大型最优潮流求解器的实现
4. An Easy Way to Build Parallel State-of-the-art Combinatorial Optimization Problem Solvers: A Computational Study on Solving Steiner Tree Problems and Mixed Integer Semidefinite Programs by using ugSCIP-*,*-Libraries [C] . Yuji Shinano, Daniel Rehfeldt, Tristan Gally IEEE International Parallel and Distributed Processing Symposium Workshops . 2019

机译：建立并行的最新组合优化问题求解器的简便方法：使用ug SCIP-*，*-Library解决Steiner树问题和混合整数半定程序的计算研究
5. Merging techniques for combinatorial optimization: Spectral graph theory and semidefinite programming. [D] . Kolla, Alexandra. 2009

机译：组合优化的合并技术：频谱图理论和半定规划。
6. SDU: A Semidefinite Programming-Based Underestimation Method for Stochastic Global Optimization in Protein Docking [O] . Ioannis Ch. Paschalidis, Yang Shen, Pirooz Vakili, -1

机译：SDU：蛋白质对接中的随机全局优化的基于半定规划的低估方法
7. Solving Sparse Semidefinite Programs by Matrix Completion (Part I) (Mathematical Science of Optimization) [O] . Fukuda Mituhiro, Nakata Kazuhide, Fujisawa Katsuki, 2000

机译：通过矩阵完成法求解稀疏半定程序（第一部分）（优化数学）

Solving large-scale sparse semidefinite programs for combinatorial optimization

摘要

著录项

相似文献

相关主题

期刊订阅