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 th...
详细信息
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. cuttingplanes 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.
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...
详细信息
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.
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 pape...
详细信息
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 (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 regula...
详细信息
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.
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 o...
详细信息
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.
作者:
Gotoh, JKonno, HUniv 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 solvi...
详细信息
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.
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 ...
详细信息
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.
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 statistic...
详细信息
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 cuttingplane 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.
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...
详细信息
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.
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 inactiv...
详细信息
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.
暂无评论