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.

Inhibition of L-type amino acid transport with non-physiological amino acids in the Pahenu2 mouse model of phenylketonuria

Phenylketonuria, an autosomal recessive Mendelian disorder, is one of the most common inborn errors of metabolism. Although currently treated by diet, many suboptimal outcomes occur for patients. Neuropathological outcomes include cognitive loss, white matter abnormalities, and hypo- or demyelination, resulting from high concentrations and/or fluctuating levels of phenylalanine. High phenylalanine can also result in competitive exclusion of other large neutral amino acids from the brain, including tyrosine and tryptophan (essential precursors of dopamine and serotonin). This competition occurs at the blood brain barrier, where the L-type amino acid transporter, LAT1, selectively facilitates entry of large neutral amino acids. The hypothesis of these studies is that certain non-physiological amino acids (NPAA; DL-norleucine (NL), 2-aminonorbornane (NB; 2-aminobicyclo-(2,1,1)-heptane-2-carboxylic acid), α-aminoisobutyrate (AIB), and α-methyl-aminoisobutyrate (MAIB)) would competitively inhibit LAT1 transport of phenylalanine (Phe) at the blood-brain barrier interface. To test this hypothesis, Pah-/- mice (n=5, mixed gender; Pah+/-(n=5) as controls) were fed either 5% NL, 0.5% NB, 5% AIB or 3% MAIB (w/w 18% protein mouse chow) for 3 weeks. Outcome measurements included food intake, body weight, brain LNAAs, and brain monoamines measured via LCMS/MS or HPLC. Brain Phe values at sacrifice were significantly reduced for NL, NB, and MAIB, verifying the hypothesis that these NPAAs could inhibit Phe trafficking into the brain. However, concomitant reductions in tyrosine and methionine occurred at the concentrations employed. Blood Phe levels were not altered indicating no effect of NPAA competitors in the gut. Brain NL and NB levels, measured with HPLC, verified both uptake and transport of NPAAs. Although believed predominantly unmetabolized, NL feeding significantly increased blood urea nitrogen. Pah-/-disturbances of monoamine metabolism were exacerbated by NPAA intervention, primarily with NB (the prototypical LAT inhibitor). To achieve the overarching goal of using NPAAs to stabilize Phe transport levels into the brain, a specific Phe-reducing combination and concentration of NPAAs must be found. Our studies represent the first in vivo use of NL, NB and MAIB in Pah-/- mice, and provide proof-of-principle for further characterization of these LAT inhibitors. Our data is the first to document an effect of MAIB, a specific system A transport inhibitor, on large neutral amino acid transport.

A NATURALISTIC COMPUTATIONAL MODEL OF HUMAN BEHAVIOR IN NAVIGATION AND SEARCH TASKS

Planning, navigation, and search are fundamental human cognitive abilities central to spatial problem solving in search and rescue, law enforcement, and military operations. Despite a wealth of literature concerning naturalistic spatial problem solving in animals, literature on naturalistic spatial problem solving in humans is comparatively lacking and generally conducted by separate camps among which there is little crosstalk. Addressing this deficiency will allow us to predict spatial decision making in operational environments, and understand the factors leading to those decisions. The present dissertation is comprised of two related efforts, (1) a set of empirical research studies intended to identify characteristics of planning, execution, and memory in naturalistic spatial problem solving tasks, and (2) a computational modeling effort to develop a model of naturalistic spatial problem solving. The results of the behavioral studies indicate that problem space hierarchical representations are linear in shape, and that human solutions are produced according to multiple optimization criteria. The Mixed Criteria Model presented in this dissertation accounts for global and local human performance in a traditional and naturalistic Traveling Salesman Problem. The results of the empirical and modeling efforts hold implications for basic and applied science in domains such as problem solving, operations research, human-computer interaction, and artificial intelligence.