排序方式: 共有17条查询结果,搜索用时 15 毫秒
11.
István Maros 《Annals of Operations Research》2003,124(1-4):193-203
In the simplex method for linear programming the algorithmic step of checking the reduced costs of nonbasic variables is called the “pricing” step. If these reduced costs are all of the “right sign” the current basis (and solution) is optimal, if not, this procedure selects a candidate vector that looks profitable for inclusion in the basis. While theoretically the choice of any profitable vector will lead to a finite termination (provided degeneracy is handled properly) but the number of iterations until termination depends very heavily on the actual choice (which is defined by the selection rule applied). Pricing has long been an area of heuristics to help make better selection. As a result, many different and sophisticated pricing strategies have been developed, implemented and tested. So far none of them is known to be dominating all others in all cases. Therefore, advanced simplex solvers need to be equipped with many strategies so that the most suitable one can be activated for each individual problem instance. In this paper we present a general pricing scheme. It creates a large flexibility in pricing. It is controlled by three parameters. With different settings of the parameters many of the known strategies can be reproduced as special cases. At the same time, the framework makes it possible to define new strategies or variants of them. The scheme is equally applicable to general and network simplex algorithms. 相似文献
12.
Nalân Gülpinar Gregory Gutin Gautam Mitra István Maros 《Computational Optimization and Applications》2000,15(3):235-247
In this paper, we present an alternative multi-stage generalized upper bounds (GUB) based approach for detecting an embedded pure network structure in an LP problem. In order to identify a GUB structure, we use two different approaches; the first is based on the notion of Markowitz merit count and the second exploits independent sets in the corresponding graphs. Our computational experiments show that the multi-stage GUB algorithm based on these approaches performs favourably when compared with other well known algorithms. 相似文献
13.
14.
Nalâv Gülpinar Gautam Mitra István Maros 《Computational Optimization and Applications》2002,21(1):71-93
In this paper, we investigate how an embedded pure network structure arising in many linear programming (LP) problems can be exploited to create improved sparse simplex solution algorithms. The original coefficient matrix is partitioned into network and non-network parts. For this partitioning, a decomposition technique can be applied. The embedded network flow problem can be solved to optimality using a fast network flow algorithm. We investigate two alternative decompositions namely, Lagrangean and Benders. In the Lagrangean approach, the optimal solution of a network flow problem and in Benders the combined solution of the master and the subproblem are used to compute good (near optimal and near feasible) solutions for a given LP problem. In both cases, we terminate the decomposition algorithms after a preset number of passes and active variables identified by this procedure are then used to create an advanced basis for the original LP problem. We present comparisons with unit basis and a well established crash procedure. We find that the computational results of applying these techniques to a selection of Netlib models are promising enough to encourage further research in this area. 相似文献
15.
A characteristic feature of the primal network simplex algorithm (NSA) is that it usually makes a large number of degenerate iterations. Though cycling and even stalling can be avoided by recently introduced pivot rules for NSA, the practical efficiency of these rules is not known yet. For the case when the simplex algorithm is used to solve the continuous linear programming (LP) problem there exists a practical anti-cycling procedure that proved to be efficient. It is based on an expanding relaxation of the individual bound on the variables. In this paper we discuss the adaptation of this method to NSA, taking advantage of the special integer nature of network problems. We also give an account of our experience with these ideas as they are experimentally implemented in the MINET network LP solver. Reductions of CPU time have been achieved on a smaller set of specially structured real-life problems.This research was supported in part by Hungarian Research Fund OTKA 2587, and by DAAD 314 108 060 0 while the author was at Universität Heidelberg, Germany, October, 1990. 相似文献
16.
Organic materials in aqueous solution are determined by the carbon dioxide formed by complete oxidation. This is distilled in a special apparatus into barium hydroxide solution covered with pentane and the excess of alkali titrated, 0.06–6 mg of organic carbon can be determined. 相似文献
17.
Carboxylic acids which decompose spontaneously on boiling or by oxidation in aqueous solutions can be determined by titration of the carbon dioxide formed after distillation as described previously. Acetonedicarboxylic acid and p-aminosalicylic acid are determined by spontaneous decarboxylation. Hydrolysis must precede the determination for acetoacetic ester, phenylethylcyanoacetic ethyl ester and for carbonic acid esters. Oxidative decarboxylation allows determinations of glyoxylic acid, aldonic acids, sugar dicarboxylic acids, formic acid, oxalic acid and α-amino acids. The titration of the carbon dioxide formed can be done with 0.1 or 0.01 N solutions. The interference of atmospheric carbon dioxide is avoided by the use of pentane as a sealing liquid. 相似文献