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

Accelerating revised simplex method Using GPU-Based Basis Update

IEEE ACCESS 2020年 8卷 52121-52138页

作者： Shah, Usman Ali Yousaf, Suhail Ahmad, Iftikhar Rehman, Safi Ur Ahmad, Muhammad Ovais Univ Engn & Technol Peshawar Dept Comp Sci & Informat Technol Peshawar Pakistan Univ Engn & Technol Peshawar Intelligent Syst Design Lab Natl Ctr Artificial Intelligence Peshawar Pakistan Karakoram Int Univ Dept Min Engn Gilgit 15100 Pakistan Karlstad Univ Dept Math & Comp Sci S-65188 Karlstad Sweden

Optimization problems lie at the core of scientific and engineering endeavors. Solutions to these problems are often compute-intensive. To fulfill their compute-resource requirements, graphics processing unit (GPU) technology is considered a great opportunity. To this end, we focus on linear programming (LP) problem solving on GPUs using revised simplex method (RSM). This method has potentially GPU-friendly tasks, when applied to large dense problems. Basis update (BU) is one such task, which is performed in every iteration to update a matrix called basis-inverse matrix. The contribution of this paper is two-fold. Firstly, we experimentally analyzed the performance of existing GPU-based BU techniques. We discovered that the performance of a relatively old technique, in which each GPU thread computed one element of the basis-inverse matrix, could be significantly improved by introducing a vector-copy operation to its implementation with a sophisticated programming framework. Second, we extended the adapted element-wise technique to develop a new BU technique by using three inexpensive vector operations. This allowed us to reduce the number of floating-point operations and conditional processing performed by GPU threads. A comparison of BU techniques implemented in double precision showed that our proposed technique achieved 17.4 & x0025;and 13.3 & x0025;average speed-up over its closest competitor for randomly generated and well-known sets of problems, respectively. Furthermore, the new technique successfully updated basis-inverse matrix in relatively large problems, which the competitor was unable to update. These results strongly indicate that our proposed BU technique is not only efficient for dense RSM implementations but is also scalable.

关键词： Graphics processing units Linear programming Sparse matrices Standards Task analysis Memory management Iterative methods Dense matrices GPU GPGPU linear programming revised simplex method

来源：评论

学校读者我要写书评

暂无评论

Parallelizing the dual revised simplex method

引用

MATHEMATICAL PROGRAMMING COMPUTATION 2018年第1期10卷 119-142页

作者： Huangfu, Q. Hall, J. A. J. FICO House Int SqStarley Way Birmingham B37 7GN W Midlands England Univ Edinburgh Sch Math James Clerk Maxwell BldgPeter Guthrie Tait Rd Edinburgh EH9 3FD Midlothian Scotland Univ Edinburgh Maxwell Inst Math Sci James Clerk Maxwell BldgPeter Guthrie Tait Rd Edinburgh EH9 3FD Midlothian Scotland

This paper introduces the design and implementation of two parallel dual simplex solvers for general large scale sparse linear programming problems. One approach, called PAMI, extends a relatively unknown pivoting strategy called suboptimization and exploits parallelism across multiple iterations. The other, called SIP, exploits purely single iteration parallelism by overlapping computational components when possible. Computational results show that the performance of PAMI is superior to that of the leading open-source simplex solver, and that SIP complements PAMI in achieving speedup when PAMI results in slowdown. One of the authors has implemented the techniques underlying PAMI within the FICO Xpress simplex solver and this paper presents computational results demonstrating their value. In developing the first parallel revised simplex solver of general utility, this work represents a significant achievement in computational optimization.

关键词： Linear programming revised simplex method Parallel computing

来源：评论

学校读者我要写书评

暂无评论

revised simplex method and its application for solving fuzzy linear programming problems

引用

EUROPEAN JOURNAL OF INDUSTRIAL ENGINEERING 2012年第3期6卷 259-280页

作者： Nasseri, S. H. Attari, H. Ebrahimnejad, A. Mazandaran Univ Dept Math Babol Sar Iran Islamic Azad Univ Dept Math Qaemshahr Branch Qaemshahr Iran

Linear programming models play an important role in management, economic, data envelopment analysis, operations research and many industrial applications. In many practical situations there is a kind of ambiguity in the parameters of these models which can be expressed by means of fuzzy numbers. In the literature of fuzzy mathematical programming there are many types of the fuzzy linear programming problems. But in this paper, we deal with a kind of linear programming which includes the triangular fuzzy numbers in its parameters. For finding the solution of these problems, we propose a revised simplex algorithm for an extended linear programming problem which is equivalent to the original fuzzy linear programming problem. An illustrative example is presented to clarify the proposed approach. A fuzzy DEA model has been also considered as a practical application to illustrate the effectiveness of the proposed approach. [Received 20 December 2009;revised 29 September 2010;Accepted 11 November 2010]

关键词： fuzzy linear programming revised simplex method ranking of fuzzy numbers fuzzy data envelopment analysis DEA

来源：评论

学校读者我要写书评

暂无评论

Efficient revised simplex method for SVM Training

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS 2011年第10期22卷 1650-1661页

作者： Sentelle, Christopher Anagnostopoulos, Georgios C. Georgiopoulos, Michael Univ Cent Florida Dept Elect Engn & Comp Sci Orlando FL 32816 USA Florida Inst Technol Dept Elect Engn Melbourne FL 32900 USA

Existing active set methods reported in the literature for support vector machine (SVM) training must contend with singularities when solving for the search direction. When a singularity is encountered, an infinite descent direction can be carefully chosen that avoids cycling and allows the algorithm to converge. However, the algorithm implementation is likely to be more complex and less computationally efficient than would otherwise be required for an algorithm that does not have to contend with the singularities. We show that the revised simplex method introduced by Rusin provides a guarantee of nonsingularity when solving for the search direction. This method provides for a simpler and more computationally efficient implementation, as it avoids the need to test for rank degeneracies and also the need to modify factorizations or solution methods based upon those rank degeneracies. In our approach, we take advantage of the guarantee of nonsingularity by implementing an efficient method for solving the search direction and show that our algorithm is competitive with SVM-QP and also that it is a particularly effective when the fraction of nonbound support vectors is large. In addition, we show competitive performance of the proposed algorithm against two popular SVM training algorithms, SVMLight and LIBSVM.

关键词： Active set method null space method quadratic programming revised simplex method support vector machine

来源：评论

学校读者我要写书评

暂无评论

On the Decomposition method for Linear Programming Decoding of LDPC Codes

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2010年第12期58卷 3448-3458页

作者： Liu, Haiyang Qu, Wenze Liu, Bin Chen, Jie Chinese Acad Sci Inst Microelect Beijing 100029 Peoples R China

In this paper, we focus on solving the linear programming (LP) problem that arises in the decoding of low-density parity-check (LDPC) codes by means of the revised simplex method. In order to take advantage of the structure of the LP problem, we reformulate the dual LP and apply the idea of Dantzig-Wolfe (D-W) decomposition method to solve the problem. Each subproblem in the D-W decomposition method is an LP over a convex polyhedral cone. We define the convex polyhedral cone as local parity-check cone and discuss its special structures. Then, we enumerate its extreme rays and use these extreme rays to design an efficient method for the general LP decoding problem. The proposed method exhibits advantages in reducing both the storage and computational requirements.

关键词： Low-density parity-check (LDPC) codes linear programming (LP) decoding revised simplex method Dantzig-Wolfe (D-W) decomposition local parity-check cone

来源：评论

学校读者我要写书评

暂无评论

Optimal matrix-segmentation by rectangles

引用

DISCRETE APPLIED MATHEMATICS 2009年第9期157卷 2015-2030页

作者： Engel, Konrad Univ Rostock Inst Math D-18051 Rostock Germany

We study the problem of decomposing a nonnegative matrix into a nonnegative combination of 0-1-matrices whose ones form a rectangle such that the sum of the coefficients is minimal. We present for the case of two rows an easy algorithm that provides an optimal solution which is integral if the given matrix is integral. An additional integrality constraint makes the problem more difficult if the matrix has more than two rows. An algorithm that is based on the revised simplex method and uses only very few Gomory cuts yields exact integral solutions for integral matrices of reasonable size in a short time. For matrices of large dimension we propose a special greedy algorithm that provides sufficiently good results in numerical experiments. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Network flow Intensity-modulated radiation therapy (IMRT) Segmentation algorithm Linear programming Rectangular partition Matrix-decomposition Gomory cut revised simplex method

来源：评论

学校读者我要写书评

暂无评论

Hyper-sparsity in the revised simplex method and how to exploit it

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2005年第3期32卷 259-283页

作者： Hall, JAJ McKinnon, KIM Univ Edinburgh Sch Math JCMB Edinburgh EH9 3JZ Midlothian Scotland

The revised simplex method is often the method of choice when solving large scale sparse linear programming problems, particularly when a family of closely-related problems is to be solved. Each iteration of the revised simplex method requires the solution of two linear systems and a matrix vector product. For a significant number of practical problems the result of one or more of these operations is usually sparse, a property we call hyper-sparsity. Analysis of the commonly-used techniques for implementing each step of the revised simplex method shows them to be inefficient when hyper-sparsity is present. Techniques to exploit hyper-sparsity are developed and their performance is compared with the standard techniques. For the subset of our test problems that exhibits hyper-sparsity, the average speedup in solution time is 5.2 when these techniques are used. For this problem set our implementation of the revised simplex method which exploits hyper-sparsity is shown to be competitive with the leading commercial solver and significantly faster than the leading public-domain solver.

关键词： linear programming revised simplex method sparsity

来源：评论

学校读者我要写书评

暂无评论

Linear programming for database environment

Linear programming for database environment

引用

4th International Conference on Informatics in Control, Automation and Robotics

作者： Kawaguchi, Akira Perez, Jose Alfredo CUNY City Coll Dept Comp Sci New York NY 10031 USA

ISBN: (纸本)9789728865825

Solving large-scale optimization problems requires an integration of data-analysis and data-manipulation capabilities. Nevertheless, little attempt has been made to facilitate general linear programming solvers for database environments. Dozens of sophisticated tools and software libraries that implement linear programming model can be found. But, there is no database-embedded linear programming tool seamlessly and transparently utilized for database processing. The focus of this study is to fill out this kind of technical gap of data analysis and data manipulation, in the event of solving large-scale linear programming problems for the applications built on the database environment. Specifically, this paper studies the representation of the linear programming model in relational structures and the computational method to solve the linear programming problems. Foundations for and preliminary experimental results of this study are presented.

关键词： linear programming simplex method revised simplex method database stored procedure

来源：评论

学校读者我要写书评

暂无评论

Optimal matrix-segmentation by rectangles

引用

Electronic Notes in Discrete Mathematics 2006年 27卷 23-24页

作者： Engel, Konrad Institut für Mathematik Universität Rostock Rostock Germany

来源：评论

学校读者我要写书评

暂无评论

Two general methods for inverse optimization problems

引用

APPLIED MATHEMATICS LETTERS 1999年第2期12卷 69-72页

作者： Yang, C Zhang, J City Univ Hong Kong Dept Math Hong Kong Peoples R China

We formulate a group of inverse optimization problems as a uniform LP model and provide two computation methods. One is a column generation method which generates necessary columns for simplex method by solving the original optimization problem. Another is an application of the ellipsoid method which can solve the group of inverse problems in polynomial time provided that the original problem has a polynomial-order algorithm. (C) 1998 Elsevier Science Ltd. All rights reserved.

关键词： revised simplex method column generation method ellipsoid method

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：