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

STEEPEST-EDGE SIMPLEX ALGORITHMS FOR linear-programming

MATHEMATICAL programming 1992年第3期57卷 341-374页

作者： FORREST, JJ GOLDFARB, D COLUMBIA UNIV DEPT IND ENGN & OPERAT RESNEW YORKNY 10027 IBM CORP THOMAS J WATSON RES CTRYORKTOWN HTSNY 10598

We present several new steepest-edge simplex algorithms for solving linear programming problems, including variants of both the primal and the dual simplex method. These algorithms differ depending upon the space in which the problem is viewed as residing, and include variants in which this space varies dynamically. We present computational results comparing steepest-edge simplex algorithms and approximate versions of them against simplex algorithms that use standard pivoting rules on truly large-scale real-world linear programs with as many as tens of thousands of rows and columns. These results demonstrate unambiguously the superiority of steepest-edge pivot selection criteria to other pivot selection criteria in the simplex method.

关键词： STEEPEST-EDGE SIMPLEX METHOD large-scale linear programming DEVEX VARIANTS

来源：评论

学校读者我要写书评

暂无评论

Scalability Evaluation of NSLP Algorithm for Solving Non-Stationary linear programming Problems on Cluster Computing Systems 3rd

Scalability Evaluation of NSLP Algorithm for Solving Non-Sta...

引用

3rd Russian Supercomputing Days (RuSCDays)

作者： Sokolinskaya, Irina Sokolinsky, Leonid B. South Ural State Univ 76 Lenin Prospekt Chelyabinsk 454080 Russia

ISBN: (纸本)9783319712543;9783319712550

The paper is devoted to a scalability study of the NSLP algorithm for solving non-stationary high-dimension linear programming problem on the cluster computing systems. The analysis is based on the BSF model of parallel computations. The BSF model is a new parallel computation model designed on the basis of BSP and SPMD models. The brief descriptions of the NSLP algorithm and the BSF model are given. The NSLP algorithm implementation in the form of a BSF program is considered. On the basis of the BSF cost metric, the upper bound of the NSLP algorithm scalability is derived and its parallel efficiency is estimated. NSLP algorithm implementation using BSF skeleton is described. A comparison of scalability estimations obtained analytically and experimentally is provided.

关键词： Non-stationary linear programming problem large-scale linear programming NSLP algorithm BSF parallel computation model Cost metric Scalability bound Parallel efficiency estimation

来源：评论

学校读者我要写书评

暂无评论

On the Solution of linear programming Problems in the Age of Big Data 11th

On the Solution of Linear Programming Problems in the Age of...

引用

11th International Scientific Conference on Parallel Computational Technologies (PCT)

作者： Sokolinskaya, Irina Sokolinsky, Leonid B. South Ural State Univ 76 Lenin Prospekt Chelyabinsk 454080 Russia

ISBN: (纸本)9783319670355;9783319670348

The Big Data phenomenon has spawned large-scale linear programming problems. In many cases, these problems are nonstationary. In this paper, we describe a new scalable algorithm called NSLP for solving high-dimensional, non-stationary linear programming problems on modern cluster computing systems. The algorithm consists of two phases: Quest and Targeting. The Quest phase calculates a solution of the system of inequalities defining the constraint system of the linear programming problem under the condition of dynamic changes in input data. To this end, the apparatus of Fejer mappings is used. The Targeting phase forms a special system of points having the shape of an n-dimensional axisymmetric cross. The cross moves in the n-dimensional space in such a way that the solution of the linear programming problem is located all the time in an e-vicinity of the central point of the cross.

关键词： NSLP algorithm Non-stationary linear programming problem large-scale linear programming Fejer mapping

来源：评论

学校读者我要写书评

暂无评论

Scalable Algorithm for Non-stationary linear programming Problems Solving 2

Scalable Algorithm for Non-stationary Linear Programming Pro...

引用

2nd International Ural Conference on Measurements (UralCon)

作者： Sokolinskaya, I. M. South Ural State Univ Chelyabinsk Russia

ISBN: (纸本)9781538605219

The paper describes a new scalable algorithm called NSLP for high-dimension, non-stationary linear programming problem solving on the modern cluster computing systems. The algorithm consists of two phases: Quest and Targeting. The Quest phase calculates a solution for the system of inequalities defining the constraint system of the linear programming problem under the condition of the input data dynamic changes. To do this, it uses the apparatus of Fejer maps. The Targeting phase forms a special system of points having the shape of the n-dimensional axisymmetric cross. The cross moves in the n-dimensional space in such a way that the solution of the linear programming problem is permanently in the epsilon-vicinity of the cross central point.

关键词： NSLP-algorithm non-stationary linear programming problem large-scale linear programming Fejer map

来源：评论

学校读者我要写书评

暂无评论

A FIRST-ORDER SMOOTHING TECHNIQUE FOR A CLASS OF large-scale linear PROGRAMS

引用

SIAM JOURNAL ON OPTIMIZATION 2014年第2期24卷 598-620页

作者： Chen, Jieqiu Burer, Samuel Argonne Natl Lab Div Math & Comp Sci Argonne IL 60439 USA Univ Iowa Dept Management Sci Iowa City IA 52242 USA

We study a class of linear programming (LP) problems motivated by large-scale machine learning applications. After reformulating the LP as a convex nonsmooth problem, we apply Nesterov's primal-dual excessive-gap technique. The iteration complexity of the excessive-gap technique depends on a parameter theta that arises because we must bound the primal feasible set, which is originally unbounded. We also dynamically update theta to speed up the convergence. The application of our algorithm to two machine learning problems demonstrates several advantages of the excessive-gap technique over existing methods.

关键词： excessive-gap technique large-scale linear programming nonsmooth optimization machine learning

来源：评论

学校读者我要写书评

暂无评论

Robust preliminary analysis of large-scale linear model for optimal industrial investments

引用

JOURNAL OF THE FRANKLIN INSTITUTE-ENGINEERING AND APPLIED MATHEMATICS 2008年第2期345卷 154-165页

作者： Ioslovich, I. Gutman, P. -O. Technion Israel Inst Technol Fac Civil & Environm Engn IL-32000 Haifa Israel

Which equipment should be bought for a given sum to increase the profit of an industrial enterprize with a known specification of production within given limits? This problem is described as a large-scale linear program (LP) of a specific structure. An effective preliminary analysis for this structure was proposed in Ioslovich and Makarenkov [On methods of dimensionality reduction in linear programming, Econ. Math. Methods Moscow (in Russian) 11(3) (1975) 316-324] which aimed to reduce the size of the problem by detection of the redundant and active constraints. In this paper a robust system is considered, dealing with box-constrained uncertainties in the input coefficients. The analysis is based on robust evaluations of bounds for primal and dual constraints. A robust evaluation of uncertain duals presented in [I. Ioslovich, P.-O. Gutman, Robust redundancy determination and evaluation of the dual variables of linear programming problems in the presence of uncertainty, 1, in, V. Kucera, M. Sebek (Eds.), Proceedings of 3rd IFAC Symposium on Robust Control Design (ROCOND 2000), IFAC, Prague, Czech Republic, Elsevier Science, Amsterdam, 2000, paper 115] is essentially used. (C) 2007 The Franklin Institute. Published by Elsevier Ltd. All rights reserved.

关键词： industrial planning investments large-scale linear programming redundancy evaluation of dual variables robust reduction

来源：评论

学校读者我要写书评

暂无评论

Interior-point methods with decomposition for solving large-scale linear programs

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1999年第1期102卷 169-192页

作者： Zhao, GY Natl Univ Singapore Dept Math Kent Ridge Singapore

This paper deals with an algorithm incorporating the interior-point method into the Dantzig-Wolfe decomposition technique for solving large-scale linear programming problems, The algorithm decomposes a linear program into a main problem and a subproblem. The subproblem is solved approximately. Hence, inexact Newton directions are used in solving the main problem. We show that the algorithm is globally linearly convergent and has polynomial-time complexity.

关键词： large-scale linear programming interior-point methods Dantzig-Wolfe decomposition algorithmic complexity

来源：评论

学校读者我要写书评

暂无评论

A largest-distance pivot rule for the simplex algorithm

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2008年第2期187卷 393-402页

作者： Pan, Ping-Qi SE Univ Dept Math Nanjing 210096 Peoples R China

We propose a new pivot rule for the simplex algorithm, which is demonstrative in the dual space intuitively. Although it is based on normalized reduced costs, like the steepest-edge rule and its variants, the rule is much simpler and cheaper than the latter. We report computational results obtained with the 47 largest Netlib problems in terms of the number of rows and columns, all of the 16 Kennington problems, and the 17 largest BPMPD problems. Over the total 80 problems, a variant of the rule outperformed the Devex rule with iterations and time ratio 1.43 and 3.24, respectively. (c) 2007 Elsevier B.V. All rights reserved.

关键词： large-scale linear programming simplex algorithm pivot rule largest-distance scaling

来源：评论

学校读者我要写书评

暂无评论

Dantzig-Wolfe and block coordinate-descent decomposition in large-scale integrated refinery-planning

引用

COMPUTERS & OPERATIONS RESEARCH 2009年第8期36卷 2472-2483页

作者： Alabi, Adebayo Castro, Jordi Univ Politecn Cataluna Dept Stat & Operat Res ES-08034 Barcelona Catalonia Spain

The integrated refinery-planning (IRP), an instrumental problem in the petroleum industry, is made of several subsystems, each of them involving a large number of decisions. Despite the complexity of the overall planning problem, this work presents a mathematical model of the refinery operations characterized by complete horizontal integration of subsystems from crude oil purchase through to product distribution. This is the main contribution from a modelling point of view. The IRP, with a planning horizon ranging from 2 to 300 days. results in a large-scale linear programming (LP) problem of up to one million constraints, 2.5 million variables and 59 millions of nonzeroes in the constraint matrix. large instances become computationally challenging for generic state-of-the-art LP solvers, such as CPLEX. To avoid this drawback, after the identification of the nonzero structure of the constraints matrix, structure-exploiting techniques such as Dantzig-Wolfe and block coordinate-descent decomposition were applied to IRP. It was also observed that interior-point methods are far more efficient than simplex ones in large IRP instances. These were the main contributions from the optimization viewpoint. A set of realistic instances were dealt with generic algorithms and these two decomposition methods. In particular the block coordinate-descent heuristic, with a reverse order of the subsystems, appeared as a promising approach for very large integrated refinery problems, obtaining either the optimal or an approximate feasible solution in all the instances tested. (c) 2008 Elsevier Ltd. All rights reserved.

关键词： Planning Petroleum industry large-scale linear programming Decomposition techniques

来源：评论

学校读者我要写书评

暂无评论

Interactive decision making for large-scale multiobjective linear programs with fuzzy numbers

引用

FUZZY SETS AND SYSTEMS 1997年第2期88卷 161-172页

作者： Sakawa, M Kato, K Department of Industrial and Systems Engineering Faculty of Engineering Hiroshima University Higashi-Hiroshima 739 Japan

In this paper, by considering the experts' imprecise or fuzzy understanding of the nature of the parameters in the problem-formulation process, large-scale multiobjective block-angular linear programming problems involving fuzzy numbers are formulated. Through the use of the alpha-level sets of fuzzy numbers, an extended Pareto optimality concept, called the alpha-Pareto optimality is introduced. To generate a candidate for the satisficing solution which is also alpha-Pareto optimal, decision maker is asked to specify the degree alpha and the reference objective values. It is shown that the corresponding alpha-Pareto optimal solution can be easily obtained by solving the minimax problems for which the Dantzig-Wolfe decomposition method is applicable. Then a linear programming-based interactive decision-making method for deriving a satisficing solution for the decision maker efficiently from an alpha-Pareto optimal solution set is presented. (C) 1997 Elsevier Science B.V.

关键词： large-scale linear programming multiobjective linear programming block angular structure fuzzy numbers interactive decision making

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：