Simplex method and theory; notes on linear programming and extension-----part 62.

"Contract no. AF 49(638)-700."

Implementação paralela escalável e eficiente do algoritmo simplex padrão em arquitetura multicore

This work presents a scalable and efficient parallel implementation of the Standard Simplex algorithm in the multicore architecture to solve large scale linear programming problems. We present a general scheme explaining how each step of the standard Simplex algorithm was parallelized, indicating some important points of the parallel implementation. Performance analysis were conducted by comparing the sequential time using the Simplex tableau and the Simplex of the CPLEXR IBM. The experiments were executed on a shared memory machine with 24 cores. The scalability analysis was performed with problems of different dimensions, finding evidence that our parallel standard Simplex algorithm has a better parallel efficiency for problems with more variables than constraints. In comparison with CPLEXR , the proposed parallel algorithm achieved a efficiency of up to 16 times better

Data Flow Analysis and the Linear Programming Model

* The research is supported partly by INTAS: 04-77-7173 project, http://www.intas.be

OPUS: interactive software for solving linear programming models using the simplex algorithm

Includes bibliography

Implementing TURF analysis through binary linear programming

This paper introduces the approach of using Total Unduplicated Reach and Frequency analysis (TURF) to design a product line through a binary linear programming model. This improves the efficiency of the search for the solution to the problem compared to the algorithms that have been used to date. The results obtained through our exact algorithm are presented, and this method shows to be extremely efficient both in obtaining optimal solutions and in computing time for very large instances of the problem at hand. Furthermore, the proposed technique enables the model to be improved in order to overcome the main drawbacks presented by TURF analysis in practice.

Maximum likelihood Linear Programming Data Fusion for Speaker Recognition

Biometric system performance can be improved by means of data fusion. Several kinds of information can be fused in order to obtain a more accurate classification (identification or verification) of an input sample. In this paper we present a method for computing the weights in a weighted sum fusion for score combinations, by means of a likelihood model. The maximum likelihood estimation is set as a linear programming problem. The scores are derived from a GMM classifier working on a different feature extractor. Our experimental results assesed the robustness of the system in front a changes on time (different sessions) and robustness in front a change of microphone. The improvements obtained were significantly better (error bars of two standard deviations) than a uniform weighted sum or a uniform weighted product or the best single classifier. The proposed method scales computationaly with the number of scores to be fussioned as the simplex method for linear programming.

Analysis of feeding strategies for small-scale dairy systems in central Mexico using linear programming

A limitation of small-scale dairy systems in central Mexico is that traditional feeding strategies are less effective when nutrient availability varies through the year. In the present work, a linear programming (LP) model that maximizes income over feed cost was developed, and used to evaluate two strategies: the traditional one used by the small-scale dairy producers in Michoacan State, based on fresh lucerne, maize grain and maize straw; and an alternative strategy proposed by the LIP model, based on ryegrass hay, maize silage and maize grain. Biological and economic efficiency for both strategies were evaluated. Results obtained with the traditional strategy agree with previously published work. The alternative strategy did not improve upon the performance of the traditional strategy because of low metabolizable protein content of the maize silage considered by the model. However, the Study recommends improvement of forage quality to increase the efficiency of small-scale dairy systems, rather than looking for concentrate supplementation.

Efficient linear programming algorithm for the transmission network expansion planning problem

The transmission network planning problem is a non-linear integer mixed programming problem (NLIMP). Most of the algorithms used to solve this problem use a linear programming subroutine (LP) to solve LP problems resulting from planning algorithms. Sometimes the resolution of these LPs represents a major computational effort. The particularity of these LPs in the optimal solution is that only some inequality constraints are binding. This task transforms the LP into an equivalent problem with only one equality constraint (the power flow equation) and many inequality constraints, and uses a dual simplex algorithm and a relaxation strategy to solve the LPs. The optimisation process is started with only one equality constraint and, in each step, the most unfeasible constraint is added. The logic used is similar to a proposal for electric systems operation planning. The results show a higher performance of the algorithm when compared to primal simplex methods.

A mixed-integer linear programming approach for optimal type, size and allocation of distributed generation in radial distribution systems

This paper presents a mixed-integer linear programming approach to solving the problem of optimal type, size and allocation of distributed generators (DGs) in radial distribution systems. In the proposed formulation, (a) the steady-state operation of the radial distribution system, considering different load levels, is modeled through linear expressions; (b) different types of DGs are represented by their capability curves; (c) the short-circuit current capacity of the circuits is modeled through linear expressions; and (d) different topologies of the radial distribution system are considered. The objective function minimizes the annualized investment and operation costs. The use of a mixed-integer linear formulation guarantees convergence to optimality using existing optimization software. The results of one test system are presented in order to show the accuracy as well as the efficiency of the proposed solution technique.© 2012 Elsevier B.V. All rights reserved.

Bilevel approach for optimal location and contract pricing of distributed generation in radial distribution systems using mixed-integer linear programming

In this study, a novel approach for the optimal location and contract pricing of distributed generation (DG) is presented. Such an approach is designed for a market environment in which the distribution company (DisCo) can buy energy either from the wholesale energy market or from the DG units within its network. The location and contract pricing of DG is determined by the interaction between the DisCo and the owner of the distributed generators. The DisCo intends to minimise the payments incurred in meeting the expected demand, whereas the owner of the DG intends to maximise the profits obtained from the energy sold to the DisCo. This two-agent relationship is modelled in a bilevel scheme. The upper-level optimisation is for determining the allocation and contract prices of the DG units, whereas the lower-level optimisation is for modelling the reaction of the DisCo. The bilevel programming problem is turned into an equivalent single-level mixed-integer linear optimisation problem using duality properties, which is then solved using commercially available software. Results show the robustness and efficiency of the proposed model compared with other existing models. As regards to contract pricing, the proposed approach allowed to find better solutions than those reported in previous works. © The Institution of Engineering and Technology 2013.

Short-term expansion planning of radial electrical distribution systems using mixed-integer linear programming

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Applications of Linear Programming to Coding Theory

Maximum-likelihood decoding is often the optimal decoding rule one can use, but it is very costly to implement in a general setting. Much effort has therefore been dedicated to find efficient decoding algorithms that either achieve or approximate the error-correcting performance of the maximum-likelihood decoder. This dissertation examines two approaches to this problem. In 2003 Feldman and his collaborators defined the linear programming decoder, which operates by solving a linear programming relaxation of the maximum-likelihood decoding problem. As with many modern decoding algorithms, is possible for the linear programming decoder to output vectors that do not correspond to codewords; such vectors are known as pseudocodewords. In this work, we completely classify the set of linear programming pseudocodewords for the family of cycle codes. For the case of the binary symmetric channel, another approximation of maximum-likelihood decoding was introduced by Omura in 1972. This decoder employs an iterative algorithm whose behavior closely mimics that of the simplex algorithm. We generalize Omura's decoder to operate on any binary-input memoryless channel, thus obtaining a soft-decision decoding algorithm. Further, we prove that the probability of the generalized algorithm returning the maximum-likelihood codeword approaches 1 as the number of iterations goes to infinity.

A stepwise fuzzy linear programming model with possibility and necessity relations

Linear programming (LP) is the most widely used optimization technique for solving real-life problems because of its simplicity and efficiency. Although conventional LP models require precise data, managers and decision makers dealing with real-world optimization problems often do not have access to exact values. Fuzzy sets have been used in the fuzzy LP (FLP) problems to deal with the imprecise data in the decision variables, objective function and/or the constraints. The imprecisions in the FLP problems could be related to (1) the decision variables; (2) the coefficients of the decision variables in the objective function; (3) the coefficients of the decision variables in the constraints; (4) the right-hand-side of the constraints; or (5) all of these parameters. In this paper, we develop a new stepwise FLP model where fuzzy numbers are considered for the coefficients of the decision variables in the objective function, the coefficients of the decision variables in the constraints and the right-hand-side of the constraints. In the first step, we use the possibility and necessity relations for fuzzy constraints without considering the fuzzy objective function. In the subsequent step, we extend our method to the fuzzy objective function. We use two numerical examples from the FLP literature for comparison purposes and to demonstrate the applicability of the proposed method and the computational efficiency of the procedures and algorithms. © 2013-IOS Press and the authors. All rights reserved.

ECONOMICAL OCCUPATION OF AGRICULTURAL AREA OF PIRACICABA (SAO PAULO STATE, BRAZIL), INCLUDING RISK THROUGH LINEAR PROGRAMMING

The economic occupation of an area of 500 ha for Piracicaba was studied with the irrigated cultures of maize, tomato, sugarcane and beans, having used models of deterministic linear programming and linear programming including risk for the Target-Motad model, where two situations had been analyzed. In the deterministic model the area was the restrictive factor and the water was not restrictive for none of the tested situations. For the first situation the gotten maximum income was of R$ 1,883,372.87 and for the second situation it was of R$ 1,821,772.40. In the model including risk a producer that accepts risk can in the first situation get the maximum income of R$ 1,883,372. 87 with a minimum risk of R$ 350 year(-1), and in the second situation R$ 1,821,772.40 with a minimum risk of R$ 40 year(-1). Already a producer averse to the risk can get in the first situation a maximum income of R$ 1,775,974.81 with null risk and for the second situation R$ 1.707.706, 26 with null risk, both without water restriction. These results stand out the importance of the inclusion of the risk in supplying alternative occupations to the producer, allowing to a producer taking of decision considered the risk aversion and the pretension of income.

Optimal scheduling of a renewable micro-grid in an isolated load area using mixed-integer linear programming

In the energy management of the isolated operation of small power system, the economic scheduling of the generation units is a crucial problem. Applying right timing can maximize the performance of the supply. The optimal operation of a wind turbine, a solar unit, a fuel cell and a storage battery is searched by a mixed-integer linear programming implemented in General Algebraic Modeling Systems (GAMS). A Virtual Power Producer (VPP) can optimal operate the generation units, assured the good functioning of equipment, including the maintenance, operation cost and the generation measurement and control. A central control at system allows a VPP to manage the optimal generation and their load control. The application of methodology to a real case study in Budapest Tech, demonstrates the effectiveness of this method to solve the optimal isolated dispatch of the DC micro-grid renewable energy park. The problem has been converged in 0.09 s and 30 iterations.