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

A cutting plane algorithm FOR MINIMUM PERFECT 2-MATCHINGS

COMPUTING 1987年第4期39卷 327-344页

作者： GROTSCHEL, M HOLLAND, O UNIV BONN INST OPERAT RESD-5300 BONN 1FED REP GER

We describe an implementation of a cutting plane algorithm for the minimum weight perfect 2-matching problem. This algorithm is based on Edmonds' complete description of the perfect 2-matching polytope and uses the simplex algorithm for solving the LP-relaxations coming up. cutting planes are determined by fast heuristics, or, if these fail, by an efficient implementation of the Padberg-Rao procedure, specialized for 2-matching constraints. With this algorithm 2-matching problems on complete graphs with up to 1000 nodes (i.e., 499,500 variables) have been solved in less than 1 hour CPU time on a medium speed computer.

关键词： 05-04 05C45 90C10 Matching cutting plane algorithm polyhedral combinatorics

来源：评论

学校读者我要写书评

暂无评论

Multi-objective synthesis using LMI formulations for application of the cutting plane algorithm

引用

EUROPEAN JOURNAL OF CONTROL 2006年第1期12卷 40-56页

作者： Abbas-Turki, Mohamed Duc, Gilles Clement, Benoit Dept Automat F-91192 Gif Sur Yvette France CNES Direct Lanceurs Pond Point Espace F-91023 Evry France

The problem of designing a controller to meet different specifications or deciding that no such controller exists is addressed in this paper by linking three types of tools: the Youla parameterization allows searching for a controller in a convex set;for formulations using linear matrix inequalities (LMI) are proposed for different practical specifications and the corresponding convex problem is solved using a cutting plane algorithm. Such an approach is dei,eloped by overcoming the problem of the huge number of additional variables which often occurs in the LMI framework, particulary when used in conjunction with the Youla parameterization. Its efficiency is discussed by considering two practical control problems.

关键词： cutting plane algorithm KYP lemma multiobjective control Youla parameterization LMI

来源：评论

学校读者我要写书评

暂无评论

A nontangential cutting plane algorithm

引用

OPERATIONS RESEARCH LETTERS 2002年第1期30卷 49-56页

作者： Lawphongpanich, S Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA

One method for solving the Lagrangian dual problem of a convex program is the cutting plane algorithm. Although this algorithm generally requires cuts that are tangential, or nearly so, to the dual function, this paper demonstrates that the algorithm still converges to an optimal solution when cuts are nontangential or generated by not solving the subproblems to optimality or nearly so. Computational results from randomly generated linear and quadratic programming problems indicate that nontangential cuts can lead to a more efficient algorithm. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： cutting plane algorithm decomposition large-scale systems

来源：评论

学校读者我要写书评

暂无评论

A faster cutting plane algorithm with accelerated line search for linear SVM

引用

PATTERN RECOGNITION 2017年 67卷 127-138页

作者： Chu, Dejun Zhang, Changshui Tao, Qing Tsinghua Univ Dept Automat State Key Lab Intelligent Technol & Syst Tsinghua Natl Lab Informat Sci & Technol TNList Beijing Peoples R China Army Officer Acad PLA Hefei Peoples R China

cutting plane algorithm (CPA) is a generalization of iterative first-order gradient method, in which the objective function is approximated successively by supporting hyperplanes. CPA has been tailored to solve regularized loss minimization in machine learning by exploiting the regularization structure. In particular, for linear Support Vector Machine (SVM) embedding a line search procedure effectively remedies the fluctuations of function value and speeds up the convergence in practical issue. However, the existing line search strategy based on sorting algorithm takes O(mlogm) time. In this paper, we propose a more effective line search solver which spends only linear time. It can be extended to multiclass SVM in which an optimized explicit piecewise linear function finding algorithm is prearranged. The total SVM training time is proved to reduce theoretically and experiments consistently confirm the effectiveness of the proposed algorithms. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Linear support vector machine Binary classification Root finding cutting plane algorithm

来源：评论

学校读者我要写书评

暂无评论

An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2021年第1期291卷 67-83页

作者： Seker, Oylum Ekim, Tinaz Taskin, Z. Caner Univ Toronto Dept Mech & Ind Engn Toronto ON M5S 3G8 Canada Bogazici Univ Dept Ind Engn TR-34342 Istanbul Turkey

We consider the selective graph coloring problem, which is a generalization of the classical graph coloring problem. Given a graph together with a partition of its vertex set into clusters, we want to choose exactly one vertex per cluster so that the number of colors needed to color the selected set of vertices is minimized. This problem is known to be NP-hard. In this study, we focus on an exact cutting plane algorithm for selective graph coloring in perfect graphs. Since there exists no suite of perfect graph instances to the best of our knowledge, we also propose an algorithm to randomly (but not uniformly) generate perfect graphs, and provide a large collection of instances available online. We conduct computational experiments to test our method on graphs with varying size and densities, and compare our results with a state-of-the-art algorithm from the literature and with solving an integer programming formulation of the problem by CPLEX. Our experiments demonstrate that our solution strategy significantly improves the solvability of the problem. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Graph theory Selective graph coloring Partition coloring cutting plane algorithm Perfect graph generation

来源：评论

学校读者我要写书评

暂无评论

Bounding option prices by semidefinite programming: A cutting plane algorithm

引用

MANAGEMENT SCIENCE 2002年第5期48卷 665-678页

作者： Gotoh, J Konno, H Univ Tsukuba Inst Policy & Planning Sci Tsukuba Ibaraki 3058573 Japan Chuo Univ Dept Ind & Syst Engn Bunkyo Ku Tokyo 1128551 Japan

In a recent article, Bertsimas and Popescu showed that a tight upper bound on a European-type call option price, given the first n moments of the distribution of the underlying security price, can be obtained by solving an associated semidefinite programming problem (SDP). The purpose of this paper is to improve and extend their results. We will show that a tight lower bound can be calculated by solving another SDP. Also, we will show that these problems can be solved very quickly by a newly developed cutting plane algorithm when n is less than six or seven.

关键词： bounds on option prices semidefinife programming problem cutting plane algorithm

来源：评论

学校读者我要写书评

暂无评论

A cutting plane algorithm for computing k-edge survivability of a network

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2004年第3期156卷 579-589页

作者： Myung, YS Kim, HJ Dankook Univ Dept Business Adm Chungnam 330714 South Korea Univ Ulsan Dept Management Informat Syst Ulsan 680749 South Korea

Given an undirected network and a set of traffic demands between pairs of nodes, k-edge survivability of a given network is defined as the percentage of the total traffic surviving the failure of k edges in the worst case. The problem of computing k-edge survivability is known to be NP-hard and no algorithm other than simple enumeration has been found. In this paper, we develop an efficient algorithm for generating lower and upper bounds of k-edge survivability of a network. We present a preprocessing procedure of reducing the problem size, a heuristic of providing a lower bound, and a cutting plane algorithm of obtaining an upper bound. Computational results for evaluating the performance of the proposed algorithm are also presented. (C) 2003 Elsevier B.V. All rights reserved.

关键词： integer programming network survivability polyhedral analysis cutting plane algorithm

来源：评论

学校读者我要写书评

暂无评论

The Detection of Earnings Manipulation: The Three-Phase cutting plane algorithm Using Mathematical Programming

引用

JOURNAL OF FORECASTING 2010年第5期29卷 442-466页

作者： Dikmen, Burcu Kucukkocaoglu, Guray Space Technol Res Inst Sci & Technol Res Council Turkey Ankara Turkey Baskent Univ Fac Econ & Adm Sci TR-06490 Ankara Turkey

The primary goal of this study was to propose an algorithm using mathematical programming to detect earnings management practices. In order to evaluate the ability of this proposed algorithm, the traditional statistical models are used as a benchmark vis-a-vis their time series counterparts. As emerging techniques in the area of mathematical programming yield better results, application of suitable models is expected to result in highly performed forecasts. The motivation behind this paper is to develop an algorithm which will succeed in detecting companies that appeal to financial manipulation. The methodology is based on cutting plane formulation using mathematical programming. A sample of 126 Turkish manufacturing firms described over 10 financial ratios and indexes are used for detecting factors associated with false financial statements. The results indicate that the proposed three-phase cutting plane algorithm outperforms the traditional statistical techniques which are widely used for false financial statement detections. Furthermore, the results indicate that the investigation of financial information can be helpful towards the identification of false financial statements and highlight the importance of financial ratios/indexes such as Days' Sales in Receivables Index (DSRI), Gross Margin Index (GMI), Working Capital Accruals to Total Assets (TATA) and Days to Inventory Index (DINV). Copyright (C) 2009 John Wiley & Sons, Ltd.

关键词： mathematical programming mathematical model cutting plane algorithm earnings management false financial statements

来源：评论

学校读者我要写书评

暂无评论

A simple finite cutting plane algorithm for integer programs

引用

OPERATIONS RESEARCH LETTERS 2012年第6期40卷 578-580页

作者： Neto, Jose CNRS Samovar UMR 5157 Telecom SudParis Inst Mines Telecom F-91011 Evry France

A cutting plane algorithm is presented in order to solve linear integer programs in a finite number of iterations, under the assumption that the feasible region is bounded. The procedure also applies to the resolution of mixed integer programs in a finite number of iterations under the additional assumption that the optimal objective value is integral. (c) 2012 Elsevier B.V. All rights reserved.

关键词： Integer programming cutting plane algorithm Finiteness

来源：评论

学校读者我要写书评

暂无评论

A PRACTICAL GEOMETRICALLY CONVERGENT cutting plane algorithm

引用

SIAM JOURNAL ON NUMERICAL ANALYSIS 1995年第2期32卷 631-644页

作者： DEMPSTER, MAH MERKOVSKY, RR DALHOUSIE UNIV DEPT MATH STAT & COMP SCIHALIFAXNS B3H 3J5CANADA PURDUE UNIV CALUMET DEPT MATH SCIHAMMONDIN 46323

In this paper we consider a practical variation of the Cheney-Goldstein-Kelley cutting plane algorithm which solves linear relaxations using the lexicographic dual simplex method and allows for the deletion of inactive cuts. The algorithm presented can be shown to exhibit a geometric global rate of convergence asymptotically under mild assumptions. Other proofs of the rate of convergence for this type of algorithm require restrictive assumptions such as strict convexity of the objective function or a Haar condition. The approach taken here requires only that at each iteration of the algorithm a cut is produced for each convex constraint.

关键词： cutting plane algorithm OUTER APPROXIMATION algorithm LEXICOGRAPHIC DUAL SIMPLEX METHOD GEOMETRIC RATE OF CONVERGENCE

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：