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.

Dynamics of settling charged particles in turbulence : theory and experiments

It has been proposed that inertial clustering may lead to an increased collision rate of water droplets in clouds. Atmospheric clouds and electrosprays contain electrically charged particles embedded in turbulent flows, often under the influence of an externally imposed, approximately uniform gravitational or electric force. In this thesis, we present the investigation of charged inertial particles embedded in turbulence. We have developed a theoretical description for the dynamics of such systems of charged, sedimenting particles in turbulence, allowing radial distribution functions to be predicted for both monodisperse and bidisperse particle size distributions. The governing parameters are the particle Stokes number (particle inertial time scale relative to turbulence dissipation time scale), the Coulomb-turbulence parameter (ratio of Coulomb ’terminalar speed to turbulence dissipation velocity scale), and the settling parameter (the ratio of the gravitational terminal speed to turbulence dissipation velocity scale). For the monodispersion particles, The peak in the radial distribution function is well predicted by the balance between the particle terminal velocity under Coulomb repulsion and a time-averaged ’drift’ velocity obtained from the nonuniform sampling of fluid strain and rotation due to finite particle inertia. The theory is compared to measured radial distribution functions for water particles in homogeneous, isotropic air turbulence. The radial distribution functions are obtained from particle positions measured in three dimensions using digital holography. The measurements support the general theoretical expression, consisting of a power law increase in particle clustering due to particle response to dissipative turbulent eddies, modulated by an exponential electrostatic interaction term. Both terms are modified as a result of the gravitational diffusion-like term, and the role of ’gravity’ is explored by imposing a macroscopic uniform electric field to create an enhanced, effective gravity. The relation between the radial distribution functions and inward mean radial relative velocity is established for charged particles.

Our Lives, Our Thoughts and Our Allegiance: New Immigrants and American Industry in 1914

Through comparative analysis of the immigrant labor forces at work in iron mining in northern Minnesota, coal mining in Illinois, and steel milling in the Calumet region of Chicago and Gary, this paper addresses the forms of social distance separating and marginalizing new immigrants from American society and trade unionism that existed in 1914, the year that marked the end point of mass immigration from Eastern and Southern Europe. The “new immigration” was a labor migration that congregated its subjects overwhelmingly in what were called "unskilled" or "semi-skilled" forms of labor. Skilled work was largely, with certain variations, the preserve of "American" or old immigrant workers. This labor gulf separating new immigrants and American workers was hardened by a spatial separateness. New immigrants often lived in what have been called industrial villages—the mining town or location, the factory neighborhood— striking in their isolation and insularity from mainstream society. This separateness and insularity became a major preoccupation for corporate managers, Progressive reformers, and for American trade unions as new immigrants began to engage in major labor struggles leading up to 1914. But among the three industries, only the union of coal miners, the United Mine Workers, enjoyed success in organizing the new immigrants. In the steel mills and the iron mines, the unions were either rooted out or failed to gain a foothold at all. The explanation for these differences is to be found in the different forms of industrial development among the industries studied.