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.

Numerical solutions of elliptic inverse problems via the equation error method

To estimate a parameter in an elliptic boundary value problem, the method of equation error chooses the value that minimizes the error in the PDE and boundary condition (the solution of the BVP having been replaced by a measurement). The estimated parameter converges to the exact value as the measured data converge to the exact value, provided Tikhonov regularization is used to control the instability inherent in the problem. The error in the estimated solution can be bounded in an appropriate quotient norm; estimates can be derived for both the underlying (infinite-dimensional) problem and a finite-element discretization that can be implemented in a practical algorithm. Numerical experiments demonstrate the efficacy and limitations of the method.

Numerical study on the curling and warping of hardened rigid pavement slabs

In-service hardened concrete pavement suffers from environmental loadings caused by curling and warping of the slab. Traditionally, these loadings are computed on the basis of treating the slab as an elastic material, and of evaluating separately the curling and warping components. This dissertation simulates temperature distribution and moisture distribution through the slabs by use of a developed numerical model that couples the heat transfer and moisture transport. The computation of environmental loadings treats the slab as an elastic-viscous material, which considers the relaxation behavior and Pickett effect of the concrete. The heat transfer model considers the impacts of solar radiation, wind speed, air temperature, pavement slab albedo, etc. on the pavement temperature distribution. This dissertation assesses the difference between documented models that aim to predict pavement temperature, highlighting their pros and cons. The moisture transport model is unique for the documented models; it mimics the wetting and drying events occurring at the slab surface. These events are estimated by a proposed statistical algorithm, which is verified by field rainfall data. Analysis of the predicted results examines on the roles of the local air RH (relative humidity), wind speed, rainy pattern in the moisture distribution through the slab. The findings reveal that seasonal air RH plays a decisive role on the slab‘s moisture distribution; but wind speed and its daily variation, daily RH variation, and seasonal rainfall pattern plays only a secondary role. This dissertation sheds light on the computation of environmental loadings that in-service pavement slabs suffer from. Analysis of the computed stresses centers on the stress relaxation near the surface, stress evolution after the curing ends, and the impact of construction season on the stress‘s magnitude. An unexpected finding is that the total environmental loadings at the cyclically-stable state divert from the thermal stresses. At such a state, the total stress at the daytime is roughly equal to the thermal stress; whereas the total stress during the nighttime is far greater than the thermal stress. An explanation for this phenomenon is that during the night hours, the decline of the slab‘s near-surface temperature leads to a drop of the near-surface RH. This RH drop results in contraction therein and develops additional tensile stresses. The dissertation thus argues that estimating the environmental loadings by solely computing the thermally-induced stresses may reach delusive results. It recommends that the total environmental loadings of in-service slabs should be estimated by a sophisticated model coupling both moisture component and temperature component.