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.
作者：
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.
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.
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.
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.
This paper deals with a portfolio selection problem with fuzzy return rates. A possibilistic mean variance (FMVC) portfolio selection model was proposed. The possibilistic programming problem can be transformed into a...
详细信息
This paper deals with a portfolio selection problem with fuzzy return rates. A possibilistic mean variance (FMVC) portfolio selection model was proposed. The possibilistic programming problem can be transformed into a linear optimal problem with an additional quadratic constraint by possibilistic theory. For such problems there are no special standard algorithms. We propose a cutting plane algorithm to solve (FMVC). The nonlinear programming problem can be solved by sequence linear programming problem. A numerical example is given to illustrate the behavior of the proposed model and algorithm. (C) 2009 Elsevier Inc. All rights reserved.
暂无评论