In this thesis we develop integer programming approaches for solving network flow problems with equal-split restrictions. Such problems arise in traffic engineering of internet protocol networks. Equal-split structure is used in protocols like OSPF and IS-IS that allow flow to be split among the multiple shortest paths. Equal-split assumptions also arise in peer-to-peer networks and road optimization problems. All the previous work on this problem has been focused on developing heuristic methods for the specific applications. We are the first ones to study the problem as a general network flow problem and provide a polyhedral study. First we consider a general multi-commodity network flow problem with equal split restrictions. This problem is NP-hard in general. We perform a polyhedral study on mixed integer linear programming formulation for this problem. Valid inequalities are obtained, and are incorporated within a branch-and-cut framework to solve the problem. We provide fast separation schemes for most of the families of valid inequalities. Computational results are presented to show the effectiveness of cutting plane families. Next, we consider the OSPF weight setting problem. We propose an integer programming formulation for this problem. A decomposition based approach to solve the problem is presented next. Valid inequalities, exploiting the structure, are obtained for this problem. We also propose heuristic methods to get good starting solutions for the problem. The proposed cutting planes and heuristic methods are integrated within a branch-and-cut framework to solve the problem. We present computational experiments that demonstrate the effectiveness of our approach to obtain solutions with tight optimality gaps as compared with default CPLEX. Finally, we consider an equal split flow problem on bipartite graphs. We present an integer programming formulation for this problem that models the equal-split in a different way than the multi-commodity network flow problem discussed before. Valid inequalities and heuristic methods for this problem are proposed, and are integrated within the branch-and-cut framework. We present computational experiments demonstrating the effectiveness of our solution strategy. We present an alternate formulation for the problem with some favorable polyhedral properties. Lastly, a computational comparison between the two formulations is presented.

We investigate chaotic ionization of highly excited hydrogen atom in crossed electric and magnetic fields (Rydberg atom) and intra-molecular relaxation in planar carbonyl sulfide (OCS) molecule. The underlying theoretical framework of our studies is dynamical systems theory and periodic orbit theory. These theories offer formulae to compute expectation values of observables in chaotic systems with best accuracy available in given circumstances, however they require to have a good control and reliable numerical tools to compute unstable periodic orbits. We have developed such methods of computation and partitioning of the phase space of hydrogen atom in crossed at right angles electric and magnetic fields, represented by a two degree of freedom (dof) Hamiltonian system. We discuss extensions to a 3-dof setting by developing the methodology to compute unstable invariant tori, and applying it to the planar OCS, represented by a 3-dof Hamiltonian. We find such tori important in explaining anomalous relaxation rates in chemical reactions. Their potential application in Transition State Theory is discussed.

In this thesis, we consider multiobjective combinatorial optimization problems. We address two main topics. We first address the polynomially solvable cases of the Traveling Salesperson Problem and the Bottleneck Traveling Salesperson Problem. We consider multiobjective versions of these problems with different combinations of objective functions, analyze their computational complexities and develop exact algorithms where possible. We next consider generating extreme supported nondominated points of multiobjective integer programming problems for any number of objective functions. We develop two algorithms for this purpose. The first one is an exact algorithm and finds all such points. The second algorithm finds only a subset of extreme supported nondominated points providing a worst case approximation for the remaining points.

A combinatorial study was carried out for hydrogen storage alloys which involve processes similar to those normally used in their fabrication. The study utilized a single sample of combined elemental (or compound) powders which were milled and consolidated into a bulk form and subsequently deformed to heavy strains. Material library was obtained in a post annealing treatment carried out at elevated temperatures which brings about solid state reactions between the powders yielding equilibrium phases in the respective alloy system. A sample comprising the material library was then pulverized and screened for hydrogen storage composition. X-ray diffraction was used as a screening tool, the sample having been examined both in as-processed and hydrogenated state. The method was successfully applied to Mg-Ni, and Mg-Ni-Ti yielding the well known Mg2Ni as the storage composition. It is concluded that partitioning of the alloy system into regions of similar solidus temperature would be required to enrich the material library.

In this study, weight optimization of two dimensional steel frames is carried out in which the flexibility of beam-to-column connections and the soil-structure interaction are considered. In the analysis and design of steel frames, beam-tocolumn connections are assumed to be either fully rigid or perfectly pinned. However, the real behavior of beam-to-column connections is actually between these extremes. Namely, even the simple connections used in practice possess some stiffness falling between these two cases mentioned above. Moreover, it is found that there exists a nonlinear relationship between the moment and beam-to-column rotation when a moment is applied to a flexible connection. These partially restrained connections influence the drift (P- effect) of whole structure as well as the moment distribution in beams and columns. Use of a direct nonlinear inelastic analysis is one way to account for all these effects in frame design. To be able to implement such analysis, beam-to-column connections should be assumed and modeled as semi-rigid connections. In the present study, beam-to-column connections are modeled as &ldquo / end plate without column stiffeners&rdquo / and &ldquo / top and seat angle with web angles&rdquo / . Soil-structure interaction is also included in the analysis. Frames are assumed to be resting on nonlinear soil, which is represented by a set of axial elements. Particle swarm optimization method is used to develop the optimum design algorithm. The Particle Swarm method is a numerical optimization technique that simulates the social behavior of birds, fishes and bugs. In nature fish school, birds flock and bugs swarm not only for reproduction but for other reasons such as finding food and escaping predators. Similar to birds seek to find food, the optimum design process seeks to find the optimum solution. In the particle swarm optimization each particle in the swarm represents a candidate solution of the optimum design problem. The design algorithm presented selects sections for the members of steel frame from the complete list of sections given in LRFD- AISC (Load and Resistance Factor Design, American Institute of Steel Construction). Besides, the design constraints are implemented from the specifications of the same code which covers serviceability and strength limitations. The optimum design algorithm developed is used to design number of rigid and semi-rigid steel frames.

Steel space frames having irregular shapes when subjected to lateral loads caused by wind or earthquakes undergo twisting as a result of their unsymmetrical topology. As a result, torsional moment comes out which is required to be resisted by the three dimensional frame system. The members of such frame are generally made out of steel I sections which are thin walled open sections. The simple beam theory is not adequate to predict behavior of such thin-walled sections under torsional moments due to the fact that the large warping deformations occur in the cross section of the member. Therefore, it is necessary to consider the effect of warping in the design of the steel space frames having members of thin walled steel sections is significant. In this study the optimum design problem of steel space frames is formulated according to the provisions of LRFD-AISC (Load and Resistance factor design of American Institute of Steel Construction) in which the effect of warping is also taken into account. Ant colony optimization and harmony search techniques two of the recent methods in stochastic search techniques are used to obtain the solution of the design problem. Number of space frame examples is designed by the algorithms developed in order to demonstrate the effect of warping in the optimum design.

In this thesis, the optimum design algorithm is presented for reinforced concrete special moment frames. The objective function is considered as the total cost of reinforced concrete frame which includes the cost of concrete, formwork and reinforcing steel bars. The cost of any component is inclusive of material, fabrication and labor. The design variables in beams are selected as the width and the depth of beams in each span, the diameter and the number of longitudinal reinforcement bars along the span and supports. In columns the width and the depth of the column section, the number and the diameter of bars in x and y directions are selected as design variables. The column section database is prepared which includes the width and height of column section, the diameter and the number of reinforcing bars in the column section is constructed. This database is used by the design algorithm to select appropriate sections for the columns of the frame under consideration. The design constraints are implemented from ACI 318-05 which covers the flexural and shear strength, serviceability, the minimum and maximum steel percentage for flexural and shear reinforcement, the spacing requirements for the reinforcing bars and the upper and lower bound requirements for the concrete sections. The optimum design problem formulated according to ACI 318-05 provisions with the design variables mentioned above turns out to be a combinatorial optimization problem. The solution of the design problem is obtained by using the harmony search algorithm (HS) which is one of the recent additions to meta-heuristic optimization techniques which are widely used in obtaining the solution of combinatorial optimization problems. The HS algorithm is quite simple and has few parameters to initialize and consists of simple steps which make it easy to implement. Number of design examples is presented to demonstrate the efficiency and robustness of the optimum design algorithm developed.

Finding the true nondominated points is typically hard for Multi-objective Combinatorial Optimization (MOCO) problems. Furthermore, it is not practical to generate all of them since the number of nondominated points may grow exponentially as the problem size increases. In this thesis, we develop an exact algorithm to find all nondominated points in a specified region. We combine this exact algorithm with a heuristic algorithm that approximates the possible locations of the nondominated points. Interacting with a decision maker (DM), the heuristic algorithm first approximately identifies the region that is of interest to the DM. Then, the exact algorithm is employed to generate all true nondominated points in this region. We conduct experiments on Multi-objective Assignment Problems (MOAP), Multi-objective Knapsack Problems (MOKP) and Multi-objective Shortest Path (MOSP) Problems / and the algorithms work well. Finding the worst possible value for each criterion among the set of efficient solutions has important uses in multi-criteria problems since the proper scaling of each criterion is required by many approaches. Such points are called nadir points. v It is not straightforward to find the nadir points, especially for large problems with more than two criteria. We develop an exact algorithm to find the nadir values for multi-objective integer programming problems. We also find bounds with performance guarantees. We demonstrate that our algorithms work well in our experiments on MOAP, MOKP and MOSP problems. Assuming that the DM&#039 / s preferences are consistent with a quasiconcave value function, we develop an interactive exact algorithm to solve MIP problems. Based on the convex cones derived from pairwise comparisons of the DM, we generate constraints to prevent points in the implied inferior regions. We guarantee finding the most preferred point and our computational experiments on MOAP, MOKP and MOSP problems show that a reasonable number of pairwise comparisons are required.

In view of the unfavorable panorama of actual energy supply practices, alternative sustainable energy sources and conversion approaches have acquired noteworthy significance in recent years. Among these, proton exchange membrane fuel cells (PEMFCs) are being considered as a pivotal building block in the transition towards a sustainable energy economy. The proton exchange membrane (PEM) is a vital component, as well as a performance-limiting factor, of the PEMFC. Consequently, the development of high performance PEM materials is of upmost importance for the advance of the PEMFC field. In this work, alternative PEM materials based on semi-interpenetrated networks from blends of poly(vinyledene fluoride) (PVDF) and sulfonated crosslinked acrylic polyelectrolytes (PE), as well as tri-phase PVDF/PE/zirconium-based composites, are studied. To alleviate the burden resulting from the vast number of possible combinations of the different precursors utilized in the preparation of the membranes, custom high throughput screening systems have been developed for their characterization. By coupling the data spaces obtained via these systems with the appropriate statistical and data analysis tools it was found that, despite not being directly involved in the proton transport process, the inert PVDF phase plays a major role on proton conductivity. Particularly, a univocal inverse correlation between the PVDF crystalline characteristics (i.e., crystallinity and crystallite size) and melt viscosity, and membrane proton conductivity was discovered. Membranes based on highly crystalline and viscous PVDF homopolymers exhibited reduced proton conductivity due to precluded segmental motion of the PE chains during crosslinking. In addition, a maximum effective amount of PE (55-60wt%) beneficial for proton conductivity was revealed. In the case of composite membranes, despite the fact that nanoparticle dispersion was thermodynamically limited, a general improvement in proton conductivity was evidenced at low to medium nanoparticle loadings (0.5 to 1wt%) in comparison to non-hybrid PVDF/PE references. This beneficial effect was particularly noticeable in membranes based on PVDF homopolymers (7% to 14.3% increment), where the nanoparticles induced a "healing" effect by providing proton-conducting paths between non-crosslinked PE channels separated by dense PVDF areas resulting from large PVDF crystallites. In general, the results presented herein are promising for the development of new cost-effective alternative PEMs.

The fields of statistical physics, discrete probability, combinatorics, and theoretical computer science have converged around efforts to understand random structures and algorithms. Recent activity in the interface of these fields has enabled tremendous breakthroughs in each domain and has supplied a new set of techniques for researchers approaching related problems. This thesis makes progress on several problems in this interface whose solutions all build on insights from multiple disciplinary perspectives. First, we consider a dynamic growth process arising in the context of DNA-based self-assembly. The assembly process can be modeled as a simple Markov chain. We prove that the chain is rapidly mixing for large enough bias in regions of Z^d. The proof uses a geometric distance function and a variant of path coupling in order to handle distances that can be exponentially large. We also provide the first results in the case of fluctuating bias, where the bias can vary depending on the location of the tile, which arises in the nanotechnology application. Moreover, we use intuition from statistical physics to construct a choice of the biases for which the Markov chain M_mon requires exponential time to converge. Second, we consider a related problem regarding the convergence rate of biased permutations that arises in the context of self-organizing lists. The Markov chain M_nn in this case is a nearest-neighbor chain that allows adjacent transpositions, and the rate of these exchanges is governed by various input parameters. It was conjectured that the chain is always rapidly mixing when the inversion probabilities are positively biased, i.e., we put nearest neighbor pair x<y in order with bias 1/2 <= p_{xy} <= 1 and out of order with bias 1-p_{xy}. The Markov chain M_mon was known to have connections to a simplified version of this biased card-shuffling. We provide new connections between M_nn and M_mon by using simple combinatorial bijections, and we prove that M_nn is always rapidly mixing for two general classes of positively biased {p_{xy}}. More significantly, we also prove that the general conjecture is false by exhibiting values for the p_{xy}, with 1/2 <= p_{xy} <= 1 for all x< y, but for which the transposition chain will require exponential time to converge. Finally, we consider a model of colloids, which are binary mixtures of molecules with one type of molecule suspended in another. It is believed that at low density typical configurations will be well-mixed throughout, while at high density they will separate into clusters. This clustering has proved elusive to verify, since all local sampling algorithms are known to be inefficient at high density, and in fact a new nonlocal algorithm was recently shown to require exponential time in some cases. We characterize the high and low density phases for a general family of discrete {it interfering binary mixtures} by showing that they exhibit a "clustering property' at high density and not at low density. The clustering property states that there will be a region that has very high area, very small perimeter, and high density of one type of molecule. Special cases of interfering binary mixtures include the Ising model at fixed magnetization and independent sets.