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

ON THE COMPLEXITY OF FOLLOWING THE CENTRAL PATH OF linear-PROGRAMS BY linear EXTRAPOLATION-II

mathematical programming 1991年第3期52卷 527-553页

作者： SONNEVEND, G STOER, J ZHAO, G 1. Institut für Angewandte Mathemaik und Statistik Universit?t Würzburg Am Hubland W-8700 Würzburg Germany

A class of algorithms is proposed for solving linear programming problems (with m inequality constraints) by following the central path using linear extrapolation with a special adaptive choice of steplengths. The latter is based on explicit results concerning the convergence behaviour of Newton's method to compute points on the central path x(r), r > 0, and this allows to estimate the complexity, i.e. the total number N = N(R, delta) of steps needed to go from an initial point x(R) to a final point x(delta), R > delta > 0, by an integral of the local "weighted curvature" of the (primal-dual) path. Here, the central curve is parametrized with the logarithmic penalty parameter r down 0. It is shown that for large classes of problems the complexity integral, i.e. the number of steps N, is not greater than const m(alpha) log(R/delta), where alpha < 1/2 e.g. alpha = 1/4 or alpha = 3/8 (note that alpha = 1/2 gives the complexity of zero order methods). We also provide a lower bound for the complexity showing that for some problems the above estimation can hold only for alpha greater-than-or-equal-to 1/3. As a byproduct, many analytical and structural properties of the primal-dual central path are obtained: there are, for instance, close relations between the weighted curvature and the logarithmic derivatives of the slack variables;the dependence of these quantities on the parameter r is described. Also, related results hold for a family of weighted trajectories, into which the central path can be embedded.

关键词： mathematical programming, linear

来源：评论

学校读者我要写书评

暂无评论

Incremental linear constraint solving and detection of implicit equalities

引用

ORSA journal on computing 1991年第4期3卷 269-274页

作者： Stuckey, Peter J. Univ of Melbourne Parkville

The incremental linear constraint satisfaction problem consists of repeatedly solving the satisfiability problem for a growing set of linear constraints. This problem is important to constraint logic programming systems where constraints are discovered one at a time and added to a current constraint set, and the satisfiability of this constraint set must be known at all times. Implicit equalities of a system of constraints are inequality constraints that are satisfied as an equality in all solutions of the system of constraints. Detecting implicit equalities is important in determining the minimal (canonical) representation of a system of linear constraints. In incremental constraint solving systems detecting implicit equalities provides information that can simplify further constraint solving. We present an algorithm which efficiently solves the incremental linear constraint satisfaction problem and detects all the implicit equalities present in the constraints. The algorithm forms a basis for the inequality constraint solver in the CLP (R) system.

关键词： mathematical programming, linear

来源：评论

学校读者我要写书评

暂无评论

Approaches to diagnosing infeasible linear programs

引用

ORSA journal on computing 1991年第3期3卷 253-261页

作者： Greenberg, Harvey J. Murphy, Frederic H. Univ of Colorado at Denver Denver United States

This paper addresses the problem of diagnosing an infeasible linear program. In practice, there are several approaches one may take, most generally using the Phase I dual variables as an initial guide. Other approaches, however, have emerged to complement the traditional ones. These and new approaches are presented here with the aim of building a toolkit for automatic reasoning when an LP expert is not available.

关键词： mathematical programming, linear

来源：评论

学校读者我要写书评

暂无评论

CONSTRAINT IMPROVEMENTS FOR MILP-BASED HARDWARE SYNTHESIS 91

CONSTRAINT IMPROVEMENTS FOR MILP-BASED HARDWARE SYNTHESIS

引用

28TH CONF ON DESIGN AUTOMATION

作者： HAFER, L School of Computing Science Simon Fraser University Burnaby B.C. V5A 1S6

ISBN: (纸本)0897913957

Work which improves the performance of mixed-integer linear programming (MILP)-based hardware synthesis by tightening the constraint system is describe. Two improvements are described. The first estimates the minimum time that a value can usefully exist and adds constraints which express this. The second reformulates scheduling constraints which prevent component usage conflicts to better match a novel LP-based branch-and-bound algorithm.

关键词： mathematical programming, linear

来源：评论

学校读者我要写书评

暂无评论

THE OMEGA TEST - A FAST AND PRACTICAL INTEGER programming ALGORITHM FOR DEPENDENCE ANALYSIS 91

THE OMEGA TEST - A FAST AND PRACTICAL INTEGER PROGRAMMING AL...

引用

4TH ANNUAL CONF ON HIGH PERFORMANCE COMPUTING ( SUPERCOMPUTING 91 )

作者： PUGH, W Univ. of Maryland College Park MD

ISBN: (纸本)0818691581

The author describes Omega test, an integer programming algorithm that can determine whether a dependence exists between two array references, and if so, under what conditions. Evidence is presented that suggests that the Omega test is competitive with approximate algorithms used in practice and suitable for use in production compilers. The Omega test is based on an extension of Fourier-Motzkin variable elimination to integer programming, and has worst-case exponential time complexity. However, it is shown that for many situations in which other (polynomial) methods are accurate, the Omega test has low-order polynomial time complexity. The Omega test can be used to simplify integer programming problems, rather than just deciding them. This has many applications, including accurately and efficiently computing dependence direction and distance vectors.

关键词： mathematical programming, linear

来源：评论

学校读者我要写书评

暂无评论

Fast approximation algorithms for fractional packing and covering problems

Fast approximation algorithms for fractional packing and cov...

引用

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science

作者： Plotkin, Serge A. Shmoys, David B. Tardos, Eva Stanford Univ CA USA

ISBN: (纸本)0818624450

Fast algorithms that find approximate solutions for a general class of problems, which are called fractional packing and covering problems, are presented. The only previously known algorithms for solving these problems are based on general linear programming techniques. The techniques developed greatly outperform the general methods in many applications, and are extensions of a method previously applied to find approximate solutions to multicommodity flow problems. The algorithms are based on a Lagrangian relaxation technique, and an important result is a theoretical analysis of the running time of a Lagrangian relaxation based algorithm. Several applications of the algorithms are presented.

关键词： mathematical programming, linear

来源：评论

学校读者我要写书评

暂无评论

A lexisearch algorithm for traveling salesman problem

引用

1991 IEEE International Joint Conference on Neural Networks - IJCNN '91

作者： Pandit, S.N.N. Srinivas, Koduri Dept of Stat Osmania Univ Hyderabad India

ISBN: (纸本)0780302273

A data-guided lexisearch algorithm for the traveling salesman problem (TSP) is presented along with an illustrative example. The algorithm is a modification of the lexisearch approach to TSP as proposed by S. N. N. Pandit (1962). By utilizing the information provided by appropriate statistics computed from the cost data of the TSP, the nodes of the network cities are renamed and an alphabet table is defined for the search algorithm developed for the TSP. It is shown that even this little preprocessing of the data before a standard algorithm was applied improves the computational efficiency substantially.

关键词： mathematical programming, linear

来源：评论

学校读者我要写书评

暂无评论

Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices

Polynomial algorithms for LP over a subring of the algebraic...

引用

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science

作者： Adler, Ilan Beling, Peter A.

ISBN: (纸本)0818624450

It is shown that a modified variant of the interior point method can solve linear programs (LPs) whose coefficients are real numbers from a subring of the algebraic integers. By defining the encoding size of such numbers to be the bit size of the integers that represent them in the subring, it is proved that the modified algorithm runs in time polynomial in the encoding size of the input coefficients, the dimension of the problem, and the order of the subring. The Tardos scheme is then extended to this case, yielding a running time that is independent of the objective and right-hand side data. As a consequence of these results, it is shown that LPs with real circulant coefficient matrices can be solved in strongly polynomial time. It is also shown how the algorithm can be applied to LPs whose coefficients belong to the extension of the integers by a fixed set of square roots.

关键词： mathematical programming, linear

来源：评论

学校读者我要写书评

暂无评论

Dynamic three-dimensional linear programming

Dynamic three-dimensional linear programming

引用

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science

作者： Eppstein, David Dept of Inf & Comput Sci Univ of California Irvine CA USA

ISBN: (纸本)0818624450

linear programming optimizations on the intersection of k polyhedra in R3, represented by their outer recursive decompositions, are performed in expected time O(k log k log n + √k log k log3 n). This result is used to derive efficient algorithms for dynamic linear programming problems in which constraints are inserted and deleted, and queries must optimize specified objective functions. As an application, an improved solution to the planar 2-center problem is described.

关键词： mathematical programming, linear

来源：评论

学校读者我要写书评

暂无评论

Interior Point Methods for linear programming: Theory and Practice

Interior Point Methods for Linear Programming: Theory and Pr...

引用

Interior Point Methods for linear programming: Theory and Practice

This issue contains 12 conference papers. The topics covered are: affine scaling methods;potential reduction methods;search directions;convergence;vector and multivector fields;path following;large scale linear progra... 详细信息

关键词： mathematical programming, linear

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：