Linear programming (LP) models that contain a (substantial) network structure frequently arise in many real life applications. In this thesis, we investigate two main questions; i) how an embedded network structure can be detected, ii) how the network structure can be exploited to create improved sparse simplex solution algorithms. In order to extract an embedded pure network structure from a general LP problem we develop two new heuristics. The first heuristic is an alternative multi-stage generalised upper bounds (GUB) based approach which finds as many GUB subsets as possible. In order to identify a GUB subset two different approaches are introduced; the first is based on the notion of Markowitz merit count and the second exploits an independent set in the corresponding graph. The second heuristic is based on the generalised signed graph of the coefficient matrix. This heuristic determines whether the given LP problem is an entirely pure network; this is in contrast to all previously known heuristics. Using generalised signed graphs, we prove that the problem of detecting the maximum size embedded network structure within an LP problem is NP-hard. The two detection algorithms perform very well computationally and make positive contributions to the known body of results for the embedded network detection. For computational solution a decomposition based approach is presented which solves a network problem with side constraints. In this approach, the original coefficient matrix is partitioned into the network and the non-network parts. For the partitioned problem, we investigate two alternative decomposition techniques namely, Lagrangean relaxation and Benders decomposition. Active variables identified by these procedures are then used to create an advanced basis for the original problem. The computational results of applying these techniques to a selection of Netlib models are encouraging. The development and computational investigation of this solution algorithm constitute further contribution made by the research reported in this thesis.

Thesis (Ph. D.)--University of Texas at Austin, 2005. / Vita. Includes bibliographical references.

No description available.

Thesis (Ph. D.)--University of Chicago Graduate School of Business, December 1997. / Includes bibliographical references.

Thesis (Ph. D.)--Industrial and Systems Engineering, Georgia Institute of Technology, 2008. / Nemhauser,George, Committee Member ; Gu, Zonghao, Committee Member ; Ergun, Ozlem, Committee Member ; Sokol, Joel, Committee Co-Chair ; Ahmed, Shabbir, Committee Chair.

Ventilation problems raised with the beginning of underground mining. In underground mining, to provide safe and healthy working conditions, ventilation should be designed properly. Especially in the planning stage of the project, to design ventilation properly is very important. The latest upgrade of the popular ventilation simulation program, known as VnetPC 2000, has been applied for the ventilation design. In this study simulation is conducted to both auxiliary and main ventilation at &Ccedil / ayirhan G Field. Information describing the geometry of a ventilation network, airway characteristics and locations, characteristics of different fans were prepared as an input. The output includes predicted airflows, frictional pressure drops, air power, losses in airway and fan operating points for different trials. After different trials it has been found that for auxiliary ventilation, where minimum required amount of air is 6 m3/s, ENGART, 30A 40SCV/60HR model fan which is the most economical one was selected. For main ventilation system, 5 fans which provide airflow more than minimum requirement were chosen. Among them the most economical one, that is ALPHAIR-5400VAX2100 HB, was selected for the mine.

For ensuring network survivability in case of single component failures many routing protocols provide a primary and a back up routing path for each origin destination pair. We address the problem of selecting these paths such that in the event of multiple failures, occuring with given probabilities, the total loss in routable demand due to both paths being intersected is small with high probability. We present a chance constraint model and solution approaches based on an explicit integer programming formulation, a robust formulation and a cutting plane approach that yield reasonably good solutions assuming that the failures are caused by at most two elementary events, which may each affect several network components.

The master’s thesis focuses on the optimization models in logistics with emphasis on the network interdiction problem. The brief introduction is followed by two overview chapters - graph theory and mathematical programming. Important definitions strongly related to network interdiction problems are introduced in the chapter named Basic concepts of graph theory. Necessary theorems used for solving problems are following the definitions. Next chapter named Introduction to mathematical programming firstly contains concepts from linear programming. Definitions and theorems are chosen with respect to the following maximum flow problem and the derived dual problem. Concepts of stochastic optimization follow. In the fifth chapter, we discuss deterministic models of the network interdiction. Stochastic models of the network interdiction follow in the next chapter. All models are implemented in programmes written in the programming language GAMS, the codes are attached.