Parallel algorithm for solving integer linear programs

Linear programs, or LPs, are often used in optimization problems, such as improving manufacturing efficiency of maximizing the yield from limited resources. The most common method for solving LPs is the Simplex Method, which will yield a solution, if one exists, but over the real numbers. From a purely numerical standpoint, it will be an optimal solution, but quite often we desire an optimal integer solution. A linear program in which the variables are also constrained to be integers is called an integer linear program or ILP. It is the focus of this report to present a parallel algorithm for solving ILPs. We discuss a serial algorithm using a breadth-first branch-and-bound search to check the feasible solution space, and then extend it into a parallel algorithm using a client-server model. In the parallel mode, the search may not be truly breadth-first, depending on the solution time for each node in the solution tree. Our search takes advantage of pruning, often resulting in super-linear improvements in solution time. Finally, we present results from sample ILPs, describe a few modifications to enhance the algorithm and improve solution time, and offer suggestions for future work.

Optimization of ethanol production by yeasts from lignocellulosic feedstocks

Ethanol from lignocellulosic feedstocks is not currently competitive with corn-based ethanol in terms of yields and commercial feasibility. Through optimization of the pretreatment and fermentation steps this could change. The overall goal of this study was to evaluate, characterize, and optimize ethanol production from lignocellulosic feedstocks by the yeasts Saccharomyces cerevisiae (strain Ethanol Red, ER) and Pichia stipitis CBS 6054. Through a series of fermentations and growth studies, P. stipitis CBS 6054 and S. cerevisiae (ER) were evaluated on their ability to produce ethanol from both single substrate (xylose and glucose) and mixed substrate (five sugars present in hemicellulose) fermentations. The yeasts were also evaluated on their ability to produce ethanol from dilute acid pretreated hydrolysate and enzymatic hydrolysate. Hardwood (aspen), softwood (balsam), and herbaceous (switchgrass) hydrolysates were also tested to determine the effect of the source of the feedstock. P. stipitis produced ethanol from 66-98% of the theoretical yield throughout the fermentation studies completed over the course of this work. S. cerevisiae (ER) was determined to not be ideal for dilute acid pretreated lignocellulose because it was not able to utilize all the sugars found in hemicellulose. S. cerevisiae (ER) was instead used to optimize enzymatic pretreated lignocellulose that contained only glucose monomers. It was able to produce ethanol from enzymatically pretreated hydrolysate but the sugar level was so low (>3 g/L) that it would not be commercially feasible. Two lignocellulosic degradation products, furfural and acetic acid, were evaluated for whether or not they had an inhibitory effect on biomass production, substrate utilization, and ethanol production by P. stipitis and S. cerevisiae (ER). It was determined that inhibition is directly related to the concentration of the inhibitor and the organism. The final phase for this thesis focused on adapting P. stipitis CBS 6054 to toxic compounds present in dilute acid pretreated hydrolysate through directed evolution. Cultures were transferred to increasing concentrations of dilute acid pretreated hydrolysate in the fermentation media. The adapted strains’ fermentation capabilities were tested against the unadapted parent strain at each hydrolysate concentration. The fermentation capabilities of the adapted strain were significantly improved over the unadapted parentstrain. On media containing 60% hydrolysate the adapted strain yielded 0.30 g_ethanol/g_sugar ± 0.033 (g/g) and the unadapted parent strain yielded 0.11 g/g ±0.028. The culture has been successfully adapted to growth on media containing 65%, 70%, 75%, and 80% hydrolysate but with below optimal ethanol yields (0.14-0.19 g/g). Cell recycle could be a viable option for improving ethanol yields in these cases. A study was conducted to determine the optimal media for production of ethanol from xylose and mixed substrate fermentations by P. stipitis. Growth, substrate utilization, and ethanol production were the three factors used to evaluate the media. The three media tested were Yeast Peptone (YP), Yeast Nitrogen Base (YNB), and Corn Steep Liquor (CSL). The ethanol yields (g/g) for each medium are as follows: YP - 0.40-0.42, YNB -0.28-.030, and CSL - 0.44-.051. The results show that media containing CSL result in slightly higher ethanol yields then other fermentation media. P. stipitis was successfully adapted to dilute acid pretreated aspen hydrolysate in increasing concentrations in order to produce higher ethanol yields compared to the unadapted parent strain. S. cerevisiae (ER) produced ethanol from enzymatic pretreated cellulose containing low concentrations of glucose (1-3g/L). These results show that fermentations of lignocellulosic feedstocks can be optimized based on the substrate and organism for increased ethanol yields.

Dynamic modeling of active regeneration in catalyzed and non-catalyzed diesel particulate filters

Particulate matter (PM) emissions standards set by the US Environmental Protection Agency (EPA) have become increasingly stringent over the years. The EPA regulation for PM in heavy duty diesel engines has been reduced to 0.01 g/bhp-hr for the year 2010. Heavy duty diesel engines make use of an aftertreatment filtration device, the Diesel Particulate Filter (DPF). DPFs are highly efficient in filtering PM (known as soot) and are an integral part of 2010 heavy duty diesel aftertreatment system. PM is accumulated in the DPF as the exhaust gas flows through it. This PM needs to be removed by oxidation periodically for the efficient functioning of the filter. This oxidation process is also known as regeneration. There are 2 types of regeneration processes, namely active regeneration (oxidation of PM by external means) and passive oxidation (oxidation of PM by internal means). Active regeneration occurs typically in high temperature regions, about 500 - 600 °C, which is much higher than normal diesel exhaust temperatures. Thus, the exhaust temperature has to be raised with the help of external devices like a Diesel Oxidation Catalyst (DOC) or a fuel burner. The O2 oxidizes PM producing CO2 as oxidation product. In passive oxidation, one way of regeneration is by the use of NO2. NO2 oxidizes the PM producing NO and CO2 as oxidation products. The passive oxidation process occurs at lower temperatures (200 - 400 °C) in comparison to the active regeneration temperatures. Generally, DPF substrate walls are washcoated with catalyst material to speed up the rate of PM oxidation. The catalyst washcoat is observed to increase the rate of PM oxidation. The goal of this research is to develop a simple mathematical model to simulate the PM depletion during the active regeneration process in a DPF (catalyzed and non-catalyzed). A simple, zero-dimensional kinetic model was developed in MATLAB. Experimental data required for calibration was obtained by active regeneration experiments performed on PM loaded mini DPFs in an automated flow reactor. The DPFs were loaded with PM from the exhaust of a commercial heavy duty diesel engine. The model was calibrated to the data obtained from active regeneration experiments. Numerical gradient based optimization techniques were used to estimate the kinetic parameters of the model.

DEVELOPMENT OF AN OPTIMIZATION MODEL FOR BIOFUEL FACILITY SIZE AND LOCATION AND A SIMULATION MODEL FOR DESIGN OF A BIOFUEL SUPPLY CHAIN

A range of societal issues have been caused by fossil fuel consumption in the transportation sector in the United States (U.S.), including health related air pollution, climate change, the dependence on imported oil, and other oil related national security concerns. Biofuels production from various lignocellulosic biomass types such as wood, forest residues, and agriculture residues have the potential to replace a substantial portion of the total fossil fuel consumption. This research focuses on locating biofuel facilities and designing the biofuel supply chain to minimize the overall cost. For this purpose an integrated methodology was proposed by combining the GIS technology with simulation and optimization modeling methods. The GIS based methodology was used as a precursor for selecting biofuel facility locations by employing a series of decision factors. The resulted candidate sites for biofuel production served as inputs for simulation and optimization modeling. As a precursor to simulation or optimization modeling, the GIS-based methodology was used to preselect potential biofuel facility locations for biofuel production from forest biomass. Candidate locations were selected based on a set of evaluation criteria, including: county boundaries, a railroad transportation network, a state/federal road transportation network, water body (rivers, lakes, etc.) dispersion, city and village dispersion, a population census, biomass production, and no co-location with co-fired power plants. The simulation and optimization models were built around key supply activities including biomass harvesting/forwarding, transportation and storage. The built onsite storage served for spring breakup period where road restrictions were in place and truck transportation on certain roads was limited. Both models were evaluated using multiple performance indicators, including cost (consisting of the delivered feedstock cost, and inventory holding cost), energy consumption, and GHG emissions. The impact of energy consumption and GHG emissions were expressed in monetary terms to keep consistent with cost. Compared with the optimization model, the simulation model represents a more dynamic look at a 20-year operation by considering the impacts associated with building inventory at the biorefinery to address the limited availability of biomass feedstock during the spring breakup period. The number of trucks required per day was estimated and the inventory level all year around was tracked. Through the exchange of information across different procedures (harvesting, transportation, and biomass feedstock processing procedures), a smooth flow of biomass from harvesting areas to a biofuel facility was implemented. The optimization model was developed to address issues related to locating multiple biofuel facilities simultaneously. The size of the potential biofuel facility is set up with an upper bound of 50 MGY and a lower bound of 30 MGY. The optimization model is a static, Mathematical Programming Language (MPL)-based application which allows for sensitivity analysis by changing inputs to evaluate different scenarios. It was found that annual biofuel demand and biomass availability impacts the optimal results of biofuel facility locations and sizes.

Space trajectories optimization using variable-chromosome-length genetic algorithms

The problem of optimal design of a multi-gravity-assist space trajectories, with free number of deep space maneuvers (MGADSM) poses multi-modal cost functions. In the general form of the problem, the number of design variables is solution dependent. To handle global optimization problems where the number of design variables varies from one solution to another, two novel genetic-based techniques are introduced: hidden genes genetic algorithm (HGGA) and dynamic-size multiple population genetic algorithm (DSMPGA). In HGGA, a fixed length for the design variables is assigned for all solutions. Independent variables of each solution are divided into effective and ineffective (hidden) genes. Hidden genes are excluded in cost function evaluations. Full-length solutions undergo standard genetic operations. In DSMPGA, sub-populations of fixed size design spaces are randomly initialized. Standard genetic operations are carried out for a stage of generations. A new population is then created by reproduction from all members based on their relative fitness. The resulting sub-populations have different sizes from their initial sizes. The process repeats, leading to increasing the size of sub-populations of more fit solutions. Both techniques are applied to several MGADSM problems. They have the capability to determine the number of swing-bys, the planets to swing by, launch and arrival dates, and the number of deep space maneuvers as well as their locations, magnitudes, and directions in an optimal sense. The results show that solutions obtained using the developed tools match known solutions for complex case studies. The HGGA is also used to obtain the asteroids sequence and the mission structure in the global trajectory optimization competition (GTOC) problem. As an application of GA optimization to Earth orbits, the problem of visiting a set of ground sites within a constrained time frame is solved. The J2 perturbation and zonal coverage are considered to design repeated Sun-synchronous orbits. Finally, a new set of orbits, the repeated shadow track orbits (RSTO), is introduced. The orbit parameters are optimized such that the shadow of a spacecraft on the Earth visits the same locations periodically every desired number of days.