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

Long steps in an O(n3L) algorithm for linear programming

学校读者我要写书评

暂无评论

mathematical programming, Series A 1992年第3期54卷 251-265页

作者： Anstreicher, Kurt M. Bosch, Robert A. Yale Univ New Haven United States

We consider partial updating in Ye's affine potential reduction algorithm for linear programming. We show that using a Goldstein-Armijo rule to safeguard a linesearch of the potential function during primal steps is sufficient to control the number of updates. We also generalize the dual step construction to apply with partial updating. The result is the first O(n3L) algorithm for linear programming whose steps are not constrained by the need to remain approximately centered. The fact that the algorithm has a rigorous 'primal-only' initialization actually reduces the complexity to less than O(m1.5n1.5L).

关键词： mathematical programming, linear

Duality in infinite dimensional linear programming

学校读者我要写书评

暂无评论

mathematical programming, Series A 1992年第1-6期53卷 79-97页

作者： Romeijn, H.Edwin Smith, Robert L. Bean, James C. Erasmus Univ Rotterdam Rotterdam Netherlands

We consider the class of linear programs with infinitely many variables and constraints having the property that every constraint contains at most finitely many variables while every variable appears in at most finitely many constraints. Examples include production planning and equipment replacement over an infinite horizon. We form the natural dual linear programming problem and prove strong duality under a transversality condition that dual prices are asymptotically zero. That is, we show, under this transversality condition, that optimal solutions are attained in both primal and dual problems and their optimal values are equal. The transversality condition, and hence strong duality, is established for an infinite horizon production planning problem.

关键词： mathematical programming, linear

Simplex algorithm for piecewise-linear programming III. Computational analysis and applications

学校读者我要写书评

暂无评论

mathematical programming, Series A 1992年第2期53卷 213-235页

作者： Fourer, Robert Northwestern Univ Evanston United States

The first two parts of this paper have developed a simplex algorithm for minimizing convex separable piecewise-linear functions subject to linear constraints. This concluding part argues that a direct piecewise-linear simplex implementation has inherent advantages over an indirect approach that relies on transformation to a linear program. The advantages are shown to be implicit in relationships between the linear and piecewise-linear algorithms, and to be independent of many details of implementation. Two sets of computational results serve to illustrate these arguments;the piecewise-linear simplex algorithm is observed to run 2-6 times faster than a comparable linear algorithm, not including any additional expense that might be incurred in setting up the equivalent linear program. Further support for the practical value of a good piecewise-linear programming algorithm is provided by a survey of many varied applications.

关键词： mathematical programming, linear

Additive bounding procedure for the asymmetric travelling salesman problem

学校读者我要写书评

暂无评论

mathematical programming, Series A 1992年第2期53卷 173-197页

作者： Fischetti, Matteo Toth, Paolo Univ of Bologna Bologna Italy

In this paper, new lower bounds for the asymmetric travelling salesman problem are presented, based on spanning arborescences. The new bounds are combined in an additive procedure whose theoretical performance is compared with that of the Balas and Christofides procedure (1981). Both procedures have been imbedded in a simple branch and bound algorithm and experimentally evaluated on hard test problems.

关键词： mathematical programming, linear

Upper bound on the expectation of simplicial functions of multivariate random variables

学校读者我要写书评

暂无评论

mathematical programming, Series A 1992年第1期55卷 69-80页

作者： Dula, Jose H. Southern Methodist Univ Dallas United States

We introduce an upper bound on the expectation of a special class of sublinear functions of multivariate random variables defined over the entire Euclidean space without an independence assumption. The bound can be evaluated easily requiring only the solution of systems of linear equations thus permitting implementations in high-dimensional space. Only knowledge on the underlying distribution means and second moments is necessary. We discuss pertinent techniques on dominating general sublinear functions by using simpler sublinear and polyhedral functions and second order quadratic functions.

关键词： mathematical programming, linear

linear programming approach to solving bilinear programmes

学校读者我要写书评

暂无评论

mathematical programming, Series A 1992年第1期56卷 45-50页

作者： White, Douglas Univ of Manchester Manchester United Kingdom

This paper discusses the maximization of a bilinear function over two independent polytopes. The maximization problem is converted into a max-min problem, using duality. This problem is then solved via a sequence of dual linear programmes, whose constraint vectors are successively determined by tth order optima of a master linear programme.

关键词： mathematical programming, linear

On Anstreicher's combined phase I-phase II projective algorithm for linear programming

学校读者我要写书评

暂无评论

mathematical programming, Series A 1992年第1期55卷 1-15页

作者： Todd, Michael J. Cornell Univ Ithaca United States

Anstreicher has proposed a variant of Karmarkar's projective algorithm that handles standard-form linear programming problems nicely. We suggest modifications to his method that we suspect will lead to better search directions and a more useful algorithm. Much of the analysis depends on a two-constraint linear programming problem that is a relaxation of the sealed original problem.

关键词： mathematical programming, linear

Traveling salesman problem in graphs with some excluded minors

学校读者我要写书评

暂无评论

mathematical programming, Series A 1992年第2期53卷 147-172页

作者： Fonlupt, Jean Naddef, Denis Univ J. Fourier Grenoble France

Given a graph and a length function defined on its edge-set, the Traveling Salesman Problem can be described as the problem of finding a family of edges (an edge may be chosen several times) which forms a spanning Eulerian subgraph of minimum length. In this paper we characterize those graphs for which the convex hull of all solutions is given by the nonnegativity constraints and the classical cut constraints. This characterization is given in terms of excluded minors. A constructive characterization is also given which uses a small number of basic graphs.

关键词： mathematical programming, linear

Traveling salesman games

学校读者我要写书评

暂无评论

mathematical programming, Series A 1992年第2期53卷 199-211页

作者： Potters, Jos A.M. Curiel, Imma J. Tijs, Stef H. Univ of Nijmegen Nijmegen Netherlands

In this paper we discuss the problem of how to divide the total cost of a round trip along several institutes among the institutes visited. We introduce two types of cooperative games - fixed-route traveling salesman games and traveling salesman games - as a tool to attack this problem. Under very mild conditions we prove that fixed-route traveling salesman games have non-empty cores if the fixed route is a solution of the classical traveling salesman problem. Core elements provide us with fair cost allocations. A traveling salesman game may have an empty core, even if the cost matrix satisfies the triangle inequality. In this paper we introduce a class of matrices defining TS-games with non-empty cores.

关键词： mathematical programming, linear