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.

Quantification of relativistic perturbation forces on spacecraft trajectories

The intent of the work presented in this thesis is to show that relativistic perturbations should be considered in the same manner as well known perturbations currently taken into account in planet-satellite systems. It is also the aim of this research to show that relativistic perturbations are comparable to standard perturbations in speciffc force magnitude and effects. This work would have been regarded as little more then a curiosity to most engineers until recent advancements in space propulsion methods { e.g. the creation of a artiffcial neutron stars, light sails, and continuous propulsion techniques. These cutting-edge technologies have the potential to thrust the human race into interstellar, and hopefully intergalactic, travel in the not so distant future. The relativistic perturbations were simulated on two orbit cases: (1) a general orbit and (2) a Molniya type orbit. The simulations were completed using Matlab's ODE45 integration scheme. The methods used to organize, execute, and analyze these simulations are explained in detail. The results of the simulations are presented in graphical and statistical form. The simulation data reveals that the speciffc forces that arise from the relativistic perturbations do manifest as variations in the classical orbital elements. It is also apparent from the simulated data that the speciffc forces do exhibit similar magnitudes and effects that materialize from commonly considered perturbations that are used in trajectory design, optimization, and maintenance. Due to the similarities in behavior of relativistic versus non-relativistic perturbations, a case is made for the development of a fully relativistic formulation for the trajectory design and trajectory optimization problems. This new framework would afford the possibility of illuminating new more optimal solutions to the aforementioned problems that do not arise in current formulations. This type of reformulation has already showed promise when the previously unknown Space Superhighways arose as a optimal solution when classical astrodynamics was reformulated using geometric mechanics.

Optimal current control for sub-unity power factor correction

Switching mode power supplies (SMPS) are subject to low power factor and high harmonic distortions. Active power-factor correction (APFC) is a technique to improve the power factor and to reduce the harmonic distortion of SMPSs. However, this technique results in double frequency output voltage variation which can be reduced by using a large output capacitance. Using large capacitors increases the cost and size of the converter. Furthermore, the capacitors are subject to frequent failures mainly caused by evaporation of the electrolytic solution which reduce the converter reliability. This thesis presents an optimal control method for the input current of a boost converter to reduce the size of the output capacitor. The optimum current waveform as a function of weighing factor is found by using the Euler Lagrange equation. A set of simulations are performed to determine the ideal weighing which gives the lowest possible output voltage variation as the converter still meets the IEC-61000-3-2 class-A harmonics requirements with a power factor of 0.8 or higher. The proposed method is verified by the experimental work. A boost converter is designed and it is run for different power levels, 100 W, 200 W and 400 W. The desired output voltage ripple is 10 V peak to peak for the output voltage of 200 Vdc. This ripple value corresponds to a ± 2.5% output voltage ripple. The experimental and the simulation results are found to be quite matching. A significant reduction in capacitor size, as high as 50%, is accomplished by using the proposed method.

DOUBLE VAULT COMPOSTING LATRINES IN RURAL PARAGUAY : FEASIBLE CONSTRUCTION AND OPTIMAL USE

Water resource depletion and sanitation are growing problems around the world. A solution to both of these problems is the use of composting latrines, as it requires no water and has been recommended by the World Health Organization as an improved sanitation technology. However, little analysis has been done on the decomposition process occurring inside the latrine, including what temperatures are reached and what variables most affect the composting process. Having better knowledge of how outside variables affect composting latrines can aid development workers on the choice of implementing such technology, and to better educate the users on the appropriate methods of maintenance. This report presents a full, detailed construction manual and temperature data analysis of a double vault composting latrine. During the author’s two year Peace Corps service in rural Paraguay he was involved with building twenty one composting latrines, and took detailed temperature readings and visual observations of his personal latrine for ten months. The author also took limited temperature readings of fourteen community member’s latrines over a three month period. These data points were analyzed to find correlations between compost temperatures and several variables. The two main variables found to affect the compost temperatures were the seasonal trends of the outside temperatures, and the mixing and addition of moisture to the compost. Outside seasonal temperature changes were compared to those of the compost and a linear regression was performed resulting in a R2-value of 0.89. Mixing the compost and adding water, or a water/urine mixture, resulted in temperature increases of the compost 100% of the time, with seasonal temperatures determining the rate and duration of the temperature increases. The temperature readings were also used to find events when certain temperatures were held for sufficient amounts of time to reach total pathogen destruction in the compost. Four different events were recorded when a temperature of 122°F (50°C) was held for at least 24 hours, ensuring total pathogen destruction in that area of the compost. One event of 114.8°F (46°C) held for one week was also recorded, again ensuring total pathogen destruction. Through the analysis of the temperature data, however, it was found that the compost only reached total pathogen destruction levels during ten percent of the data points. Because of this the storage time recommendation outlined by the World Health Organization should be complied with. The WHO recommends storing compost for 1.5-2 years in climates with ambient temperatures of 2-20°C (35-68°F), and for at least 1 year with ambient temperatures of 20-35°C (68-95°F). If these storage durations are obtainable the use of the double vault composting latrine is an economical and achievable solution to sanitation while conserving water resources.

REALIZATION OF A DC MICROGRID USING A HAMILTONIAN BASED CONTROLS SOLUTION

Future power grids are envisioned to be serviced by heterogeneous arrangements of renewable energy sources. Due to their stochastic nature, energy storage distribution and management are pivotal in realizing microgrids serviced heavily by renewable energy assets. Identifying the required response characteristics to meet the operational requirements of a power grid are of great importance and must be illuminated in order to discern optimal hardware topologies. Hamiltonian Surface Shaping and Power Flow Control (HSSPFC) presents the tools to identify such characteristics. By using energy storage as actuation within the closed loop controller, the response requirements may be identified while providing a decoupled controller solution. A DC microgrid servicing a fixed RC load through source and bus level storage managed by HSSPFC was realized in hardware. A procedure was developed to calibrate the DC microgrid architecture of this work to the reduced order model used by the HSSPFC law. Storage requirements were examined through simulation and experimental testing. Bandwidth contributions between feed forward and PI components of the HSSPFC law are illuminated and suggest the need for well-known system losses to prevent the need for additional overhead in storage allocations. The following work outlines the steps taken in realizing a DC microgrid and presents design considerations for system calibration and storage requirements per the closed loop controls for future DC microgrids.