The aim of this paper is to present an experimental investigation of a Primal-Dual Exterior Point simplex algorithm (PDEPSA) for Linear Programming problems (LPs). There was a huge gap between the theoretical worst-ca...
详细信息
The aim of this paper is to present an experimental investigation of a Primal-Dual Exterior Point simplex algorithm (PDEPSA) for Linear Programming problems (LPs). There was a huge gap between the theoretical worst-case complexity and practical performance of simplex type algorithms. PDEPSA traverses across the interior of the feasible region in an attempt to avoid combinatorial complexities of vertex following algorithms. In order to gain an insight into the practical behaviour of the proposed algorithm, we have performed some computational experiments. Our computational results demonstrate that PDEPSA is faster comparable with simplex algorithm and the primal exterior point algorithm. A clear advantage is obtained by PDEPSA in number of iterations and CPU time.
The modified simplex algorithm (MDS) was applied to find the correct mixing ratios of multicomponent model solutions and essential oils for reconstructing these mixtures on the basis of their GC profiles. The MDS foun...
详细信息
The modified simplex algorithm (MDS) was applied to find the correct mixing ratios of multicomponent model solutions and essential oils for reconstructing these mixtures on the basis of their GC profiles. The MDS found the mixing ratio by maximizing the pattern similarity of simulated GC profiles to that of the true mixture. Five aqueous model solutions containing ten volatile compounds in different proportions at mg 1(-1) levels and five natural essential oils were mixed in different ratios to make the target mixtures. When the MDS was applied to standardized GC data for mixtures and model solutions or essential oils, the GC profiles of mixtures were deconvoluted into the correct combinations of model solutions or essential oils. For the essential oils, the ratios estimated from the initial deconvolution by MDS were useful as weighting factors to improve the accuracy of deconvolution. When irrelevant GC data on model solutions or essential oils were added to the data base for deconvolution, their effects were neglected by the MDS assigning very small values to them.
A number of algorithms have been designed for uncapacitated facility location problems. Computational experience with standard data sets seems to indicate the superiority of dual approaches, best known through efficie...
详细信息
A number of algorithms have been designed for uncapacitated facility location problems. Computational experience with standard data sets seems to indicate the superiority of dual approaches, best known through efficient subgradient or dual adjustment procedures. However, linear programming algorithms provide distinct advantages, in particular direct amenability to cutting-plane techniques. A streamlined dual simplex algorithm is designed based on a covering formulation of the problem and present computational results.
This note shows that the simplex method of solving Linear Programs can easily be modified to include upper bounds on dual variables implicitly. This results in a reduction in the number of columns required to express ...
详细信息
This note shows that the simplex method of solving Linear Programs can easily be modified to include upper bounds on dual variables implicitly. This results in a reduction in the number of columns required to express some LP problems. The modified simplex algorithm and a numerical example are given and the technique's utility discussed.
We consider multicommodity network flow problems, where external flow is allowed to vary and where flows of individual commodities may be constrained. For this problem, we describe the simplex algorithm. The simplex a...
详细信息
We consider multicommodity network flow problems, where external flow is allowed to vary and where flows of individual commodities may be constrained. For this problem, we describe the simplex algorithm. The simplex algorithm is based upon the inverse of the basis matrix. We discuss an approach where we only have to invert a working matrix with dimension at most equal to the number of arcs In the network. The dimension is independent of the number of commodities. The reduced cost of a nonbasic variable is found only using the working matrix that is explicitly inverted and some simple network operations. We also discuss how to pivot in the working matrix. The focus is on the detailed interpretation of the network structures arising in terms of cycles for the individual commodities. (C) 2002 John Wiley Sons, Inc.
We present a primal method for the solution of the semi-infinite linear programming problem with constraint index setS. We begin with a detailed treatment of the case whenS is a closed line interval in ?. A characteri...
详细信息
We present a primal method for the solution of the semi-infinite linear programming problem with constraint index setS. We begin with a detailed treatment of the case whenS is a closed line interval in ?. A characterization of the extreme points of the feasible set is given, together with a purification algorithm which constructs an extreme point from any initial feasible solution. The set of points inS where the constraints are active is crucial to the development we give. In the non-degenerate case, the descent step for the new algorithm takes one of two forms: either an active point is dropped, or an active point is perturbed to the left or right. We also discuss the form of the algorithm when the extreme point solution is degenerate, and in the general case when the constraint index set lies in ? p . The method has associated with it some numerical difficulties which are at present unresolved. Hence it is primarily of interest in the theoretical context of infinite-dimensional extensions of the simplex algorithm.
The simplex algorithm is a natural choice in applications requiring the analysis of spectra by curve fitting. The kinds of spectra which have been analyzed in this way include: positron lifetime spectra, NMR spectra f...
详细信息
The simplex algorithm is a natural choice in applications requiring the analysis of spectra by curve fitting. The kinds of spectra which have been analyzed in this way include: positron lifetime spectra, NMR spectra for which overlap of lines made the use of the computer program LAOCN3 unsuitable, energy dispersion spectra, Mössbauer spectra, spectra recorded with the use of heterodyne detection, and spectra consisting of multiple overlapping Gaussian components. Beckwith and Brumby used the simplex algorithm to simulate ESR spectra with the aim of determining the spectral parameters precisely. They applied their method to the analysis of ESR spectra of free radicals in solution, but stressed the generality of the method. Fajer et al. similarly used the simplex algorithm for the fitting of ESR spectra.
The random simplex algorithm for linear programming proceeds as follows: at each step, it moves from a vertex upsilon of the polytope to a randomly chosen neighbor of upsilon, the random choice being made from those n...
详细信息
The random simplex algorithm for linear programming proceeds as follows: at each step, it moves from a vertex upsilon of the polytope to a randomly chosen neighbor of upsilon, the random choice being made from those neighbors of upsilon that improve the objective function. We exhibit a polytope defined by n constraints in three dimensions with height O(log n), for which the expected running time of the random simplex algorithm is Omega(n/log n).
The paper proposes an optimization formulation of the control problem for modular multilevel converter (MMC). The main control stage computes arm voltages on average over a fixed switching period by minimizing control...
详细信息
ISBN:
(纸本)9781538663769
The paper proposes an optimization formulation of the control problem for modular multilevel converter (MMC). The main control stage computes arm voltages on average over a fixed switching period by minimizing control errors in order to satisfy as best as possible the desired references of input, circulating and output currents, while taking into account arm voltage limits. Then, mean-values of required arm voltages are achieved by phase shift pulse-width modulation (PSPWM) by computing duty cycles for each submodule while taking into account the issue of active balancing of the capacitor voltages in a secondary control stage. The proposed optimization problems are solved by using a numerical method based on the simplex algorithm and simulation results are shown in order to support the validity of the approach.
Let a1, ..., am be i.i.d. points uniformly on the unit sphere in ℝn, m ≥ n ≥ 3. and let X := {x ∈ ℝn|a1T x ≤ 1} be the random polyhedron generated by a1, ..., am. Furthermore, for linearly independent vectors u, ...
详细信息
Let a1, ..., am be i.i.d. points uniformly on the unit sphere in ℝn, m ≥ n ≥ 3. and let X := {x ∈ ℝn|a1T x ≤ 1} be the random polyhedron generated by a1, ..., am. Furthermore, for linearly independent vectors u, ū in ℝn, let S u, ū(X) be the number of shadow vertices of X in span(u, ū). The paper provides an asymptotic expansion of the expectation value s̄ n.m := 1/4E(S u, ū) for fixed n and m → ∞. s̄ n.m equals the expected number of pivot steps that the shadow vertex algorithm - a parametric variant of the simplex algorithm - requires in order to solve linear programming problems of type max uT x, x ∈ X, if the algorithm will be started with an X-vertex solving the problem max ūT x, x ∈ X. Our analysis is closely related to Borgwardt's probabilistic analysis of the simplex algorithm. We obtain a refined asymptotic analysis of the expected number of pivot steps required by the shadow vertex algorithm for uniformly on the sphere distributed data.
暂无评论