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

parametric simplex algorithms for a class of NP-Complete problems whose average number of steps is polynomial

Computational Optimization and Applications 1992年第2期1卷 227-239页

作者： Konno, Hiroshi Kuno, Takahito Yajima, Yasutoshi Institute of Human and Social Sciences Tokyo Institute of Technology Tokyo Japan Institute of Information Sciences and Electronics University of Tsukuba Tsukuba Japan Department of Industrial Engineering and Management Tokyo Institute of Technology Tokyo Japan

We will show that the average number of steps of parametric simplex algorithms for obtaining global minima of rank-one and rank-two bilinear-programming problems are lower-order polynomial functions of the problem size under the standard assumptions on the distribution of the data imposed in the probabilistic analysis of the simplex method. This means that there exist algorithms for some special class of NP-complete problems, whose average number of arithmetics are polynomial order of the problem size. © 1992 Kluwer Academic Publishers.

关键词： bilinear-programming complexity global optimization parametric simplex algorithm probabilistic analysis

来源：评论

学校读者我要写书评

暂无评论

parametric simplex algorithms for solving a special class of nonconvex minimization problems

引用

Journal of Global Optimization 1991年第1期1卷 65-81页

作者： Konno, Hiroshi Yajima, Yasutoshi Matsui, Tomomi Institute of Human and Social Sciences Tokyo Institute of Technology Tokyo 152 2-12-1 Oh-Okayama Meguru-ku Japan Department of Industrial Engineering and Management Tokyo Institute of Technology Tokyo Japan Department of System Sciences Tokyo Institute of Technology Tokyo Japan

It is shown that parametric linear programming algorithms work efficiently for a class of nonconvex quadratic programming problems called generalized linear multiplicative programming problems, whose objective function is the sum of a linear function and a product of two linear functions. Also, it is shown that the global minimum of the sum of the two linear fractional functions over a polytope can be obtained by a similar algorithm. Our numerical experiments reveal that these problems can be solved in much the same computational time as that of solving associated linear programs. Furthermore, we will show that the same approach can be extended to a more general class of nonconvex quadratic programming problems. © 1991 Kluwer Academic Publishers.

关键词： linear multiplicative programming minimization of products parametric simplex algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimization of the sum of three linear fractional functions

引用

JOURNAL OF GLOBAL OPTIMIZATION 1999年第4期15卷 419-432页

作者： Konno, H Abe, N Tokyo Inst Technol Dept Ind Engn & Management Tokyo 152 Japan

In this paper, we will propose an efficient and reliable heuristic algorithm for minimizing and maximizing the sum of three linear fractional functions over a polytope. These problems are typical nonconvex minimization problems of practical as well as theoretical importance. This algorithm uses a primal-dual parametric simplex algorithm to solve a subproblem in which the value of one linear function is fixed. A subdivision scheme is employed in the space of this linear function to obtain an approximate optimal solution of the original problem. It turns out that this algorithm is much more efficient and usually generates a better solution than existing algorithms. Also, we will develop a similar algorithm for minimizing the product of three linear fractional functions.

关键词： global optimization linear fractional function parametric simplex algorithm branch and bound method

来源：评论

学校读者我要写书评

暂无评论

A finite algorithm for globally optimizing a class of rank-two reverse convex programs

引用

JOURNAL OF GLOBAL OPTIMIZATION 1998年第3期12卷 247-265页

作者： Kuno, T Yamamoto, Y Univ Tsukuba Inst Informat Sci & Elect Tsukuba Ibaraki 305 Japan Univ Tsukuba Inst Policy & Planning Sci Tsukuba Ibaraki 305 Japan

In this paper, we propose an algorithm for solving a linear program with an additional rank-two reverse convex constraint. Unlike the existing methods which generate approximately optimal solutions, the algorithm provides a rigorous optimal solution to this nonconvex problem by a finite number of dual pivot operations. Computational results indicate that the algorithm is practical and can solve fairly large scale problems.

关键词： global optimization reverse convex program rank-two quasiconcave function parametric simplex algorithm

来源：评论

学校读者我要写书评

暂无评论

LINEAR MULTIPLICATIVE PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1992年第1期56卷 51-64页

作者： KONNO, H KUNO, T UNIV TSUKUBA INST INFORMAT SCI & ELECTRTSUKUBAIBARAKI 305JAPAN

An algorithm for solving a linear multiplicative programming problem (referred to as LMP) is proposed. LMP minimizes the product of two linear functions subject to general linear constraints. The product of two linear functions is a typical non-convex function, so that it can have multiple local minima. It is shown, however, that LMP can be solved efficiently by the combination of the parametric simplex method and any standard convex minimization procedure. The computational results indicate that the amount of computation is not much different from that of solving linear programs of the same size. In addition, the method proposed for LMP can be extended to a convex multiplicative programming problem (CM P), which minimizes the product of two convex functions under convex constraints.

关键词： NONCONVEX QUADRATIC PROGRAMMING PROBLEM GLOBAL OPTIMIZATION parametric simplex algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for solving rank two and rank three bilinear programming problems

引用

Journal of Global Optimization 1991年第2期1卷 155-171页

作者： Yajima, Yasutoshi Konno, Hiroshi Department of Industrial Engineering and Management Tokyo Institute of Technology Japan Institute of Human and Social Sciences Tokyo Institute of Technology Japan

Finitely convergent algorithms for solving rank two and three bilinear programming problems are proposed. A rank k bilinear programming problem is a nonconvex quadratic programming problem with the following structure: {Mathematical expression} where X ⊂ Rⁿ¹ and Y ⊂ Rⁿ² are non-empty and bounded polytopes. We show that a variant of parametric simplex algorithm can solve large scale rank two bilinear programming problems efficiently. Also, we show that a cutting-cake algorithm, a more elaborate variant of parametric simplex algorithm can solve medium scale rank three problems. © 1991 Kluwer Academic Publishers.

关键词： Bilinear programming global minimization nonconvex quadratic programming problem parametric simplex algorithm

来源：评论

学校读者我要写书评

暂无评论

A comparative study of two key algorithms in multiple objective linear programming

引用

JOURNAL OF algorithmS & COMPUTATIONAL TECHNOLOGY 2019年第13期13卷 -页

作者： Nyiam, Paschal B. Salhi, Abdellah Univ Essex Dept Math Sci Wivenhoe Pk Colchester CO4 3SQ Essex England

Multiple objective linear programming problems are solved with a variety of algorithms. While these algorithms vary in philosophy and outlook, most of them fall into two broad categories: those that are decision space-based and those that are objective space-based. This paper reports the outcome of a computational investigation of two key representative algorithms, one of each category, namely the parametric simplex algorithm which is a prominent representative of the former and the primal variant of Bensons Outer-approximation algorithm which is a prominent representative of the latter. The paper includes a procedure to compute the most preferred nondominated point which is an important feature in the implementation of these algorithms and their comparison. Computational and comparative results on problem instances ranging from small to medium and large are provided.

关键词： Multiple objective linear programming parametric simplex algorithm outer-approximation algorithm most preferred nondominated point multiple criteria decision making

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：