Detecting embedded pure network structures in LP problems

Recently, linear programming problems with special structures have assumed growing importance in mathematical programming. It is well known that exploiting network structures within linear programs can lead to considerable improvement of the computational solution of large-scale linear programming problems. A linear program is said to contain an embedded network structure provided that some subset of its constraints can be interpreted as specifying conservation of flow. If a column of the constraint matrix has at most two non-zeros, then it leads to embedded generalized network structure and if these non-zeros are unit elements and of opposite signs, then it leads to embedded pure network structure. In this paper, we are concerned with algorithms for detecting embedded pure network structures within linear programs. The network extraction methods are presented in two groups. The first group covers deletion and addition based algorithms and the second group covers GUB based algorithms. We have extended the GUB based algorithm appearing in the second group by introducing Markowitz merit count approach for exploiting matrix non zeros. A set of well known test problems has been used to carry out computational experiments which show that our extensions to the GUB based algorithms give better results than the algorithms reported earlier.     

Parallel search paths for the simplex algorithm

It is well known that the simplex method is inherently a sequential algorithm with little scope for parallelization. Even so, during the last decades several attempts were made to parallelize it since it is one of the most important algorithms for solving linear optimization problems. Such parallelization ideas mostly rely on iteration parallelism and overlapping. Since the simplex method goes through a series of basic solutions until it finds an optimal solution, each of them must be available before performing the next basis change. This phenomenon imposes a limit on the performance of the parallelized version of the simplex method which uses overlapping iterations. Another approach can be considered if we think about alternative paths on the n-dimensional simplex polyhedron. As the simplex method goes through the edges of this polyhedron it is generally true that the speed of convergence of the algorithm is not smooth. It depends on the actual part of the surface. If a parallel version of the simplex algorithm simultaneously goes on different paths on this surface a highly reliable algorithm can be constructed. There is no known dominating strategy for pivot selection. Therefore, one can try different pivot selection methods in parallel in order to guide the algorithm on different pathways. This approach can be used effectively with periodic synchronization on shared memory multi-core computing environments to speed up the solution algorithm and get around numerically and/or algorithmically difficult situations throughout the computations.     

A numerically exact implementation of the simplex method

The numerical performance of the state-of-the-art simplex based optimizers is good. At the same time, a newly arising LP problem can cause troubles still. This is exactly what happened in the Summer of 1992. The appearance of a hard LP problem motivated the development of the idea of a numerically exact implementation of the simplex method. It is based on a super register (SR) capable of accumulating inner products with arbitrary accuracy. The necessary operations of SR that require assembly level programming are introduced. Vectors of super registers would require prohibitively much memory. Therefore, a single-SR technique is proposed that entails the reorganization of parts of the simplex method. The ideas have been implemented in the MILP LP optimizer. Experiences show that solution speed decreases by 30–50 percent but robustness increases which may be important in case of critical problems. A framework is outlined for a system where the advantages of the traditional and the SR technique can co-operate efficiently.This research was partly supported by Hungarian Research Fund OTKA 2587.     

Computational study of the GDPO dual phase-1 algorithm

The GDPO algorithm for phase-1 of the dual simplex method developed by Maros possesses some interesting theoretical features that have potentially huge computational advantages. This paper gives account of a computational analysis of GDPO that has investigated how these features work in practice by exploring the internal operation of the algorithm. Experience of a systematic study involving 48 problems gives an insight how the predicted performance advantages materialize that ultimately make GDPO an indispensable tool for dual phase-1.     

Charge specific protein placement at submicrometer and nanometer scale by direct modification of surface potential by electron beam

The understanding and the precise control of protein adsorption is extremely important for the development and optimization of biomaterials. The challenge resides in controlling the different surface properties, such as surface chemistry, roughness, wettability, or surface charge, independently, as modification of one property generally affects the other. We demonstrate the creation of electrically modified patterns on hydroxyapatite by using scanning electron beam to tailor the spatial regulation of protein adsorption via electrostatic interactions without affecting other surface properties of the material. We show that domains, presenting modulated surface potential, can be created to precisely promote or reduce protein adsorption.     

A Piecewise Linear Dual Phase-1 Algorithm for the Simplex Method

A dual phase-1 algorithm for the simplex method that handles all types of variables is presented. In each iteration it maximizes a piecewise linear function of dual infeasibilities in order to make the largest possible step towards dual feasibility with a selected outgoing variable. The algorithm can be viewed as a generalization of traditional phase-1 procedures. It is based on the multiple use of the expensively computed pivot row. By small amount of extra work per iteration, the progress it can make is equivalent to many iterations of the traditional method. While this is its most important feature, it possesses some additional favorable properties, namely, it can be efficient in coping with degeneracy and numerical difficulties. Both theoretical and computational issues are addressed. Some computational experience is also reported which shows that the potentials of the method can materialize on real world problems.     

Beiträge zur analytik einiger methansulfonsäurederivate : Jodometrisches verfahren zur bestimmung von novalgin (novamidazophen) und melubrin auch in gegenwart von antipyrin (azophen) und pyramidon (amidazophen*)

An iodometric method is presented for the determination of methanesulphonic acid derivatives that are used in medicine. Here the method was applied to the determination of novalgin and molubrin, alone, or in the presence of antiprine and pyramidone. The method is based on the fact that in moderately alkaline solution some methanesulphonic acid derivatives (novalgin, melubrin) can be split into sulphite and glycolic acid, etc., by potassium cyanide. The sulphite can then be directly titrated with iodine solution, this titration being carried out in sulphuric acid solution of moderate concentration. Under the conditions indicated the titration can be performed in the presence of the degradation products and of excess HCN, as well as in the presence of antipyrine and pyramidone     

Neue Verfahren zur Bestimmung des p-Aminophenols auch in Gegenwart einiger anorganischer reduzierender Stoffe

Zusammenfassung p-Aminophenol läßt sich leicht durch Brom oxydieren bzw. desaminieren. Die Reaktionsprodukte: p-Benzochinon bzw. Ammoniak erlauben eine quantitative Bestimmung des p-Aminophenols auch in Gegenwart einiger anorganischer Reduktionsmittel (Sulfide, Sulfite usw.), wenn man den Bromüberschuß durch Phenol (jodometrische Methode) bzw. Natriumsulfit (alkalimetrische Bestimmung) entfernt. Das alkalimetrische Bestimmungsverfahren wird wegen seiner relativ schwierigen Ausführbarkeit nur im Notfalle verwendet. Das jodometrische Verfahren kann auch zur Bestimmung von Metol (p-Methylaminophenol) herangezogen werden. Die Methoden liefern auch mit 0,01-n Lösungen genaue Resultate.

---

Summary p-Aminophenol is readily oxidized or deaminated by means of bromine. The reaction products:p-benzoquinone and ammonia, respectively, allow a quantitative determination ofp-aminophenol even in the presence of some inorganic reducing materials (sulfides, sulfites, etc.) provided the excess bromine is removed by means of phenol (iodometric method) or sodium sulfite (alkalimetric determination). Because of its relatively difficult practicability, the alkalimetric method of determination is used only in an emergency. The iodometric method procedure may be used also for the determination of metol (p-methylaminophenol). The methods give precise results even when 0,01N solutions are employed.

---

Résumé Lep-aminophénol se laisse facilement oxyder par le brome ou encore désaminer. Les produits de réaction,p-benzoquinone et ammoniac, permettent le dosage dup-aminophénol même en présence d'un agent de réduction minéral (sulfure, sulfite, etc.) si l'on sépare l'excès de brome par le phénol (méthode iodométrique) ou par le sulfite de sodium (dosage alcalimétrique). Le procédé de dosage alcalimétrique n'est utilisé qu'en cas de nécessité, en raison de son exécution relativement difficile. Le procédé iodométrique peut aussi être étendu au dosage du métal (p-méthylaminophénol). En solution 0,01N les méthodes conduisent aussi à des résultats exacts.

---

---

Herrn Prof. Dr.A. A. Benedetti-Pichler zum 70. Geburtstag gewidmet.

---

Die recht befriedigenden Ergebnisse beider Verfahren sind in drei Tabellen zusammengefaßt.