The purpose of this study was to determine whether a professional development (PD) for teachers focused on improving teacher pedagogical content knowledge (PCK) related to operations with integers would improve teacher PCK and if there was a relationship between their level of PCK and the change in the understanding of their students as measured by pre- and posttest of teacher and student knowledge. The study was conducted summer 2010 in a large urban school district on two campuses providing a district funded annual summer intervention, called Jumpstart. This program was for grade 8 students who did not pass the state assessment (Texas Assessment of Knowledge and Skills), but would be promoted to high school in the Fall 2010 due to a decision made by the Grade Placement Committee. The Jumpstart program involved 22 teachers and 341 students. For purposes of this study, changes were made to the PD and typical curriculum for a unit on integer operations to promote teacher and student conceptual understanding through a process of mathematical discussion called argumentation. The teachers and students explored a comprehensive representation for integer operations called a vector number line model using the Texas Instruments TI-73 calculator Numln application. During PD, teachers engaged in argumentation to make claims about strategies to use to understand integer operations and to explain their understanding of how different representations are connected. The results showed statistically significant growth in teacher PCK following the professional development and statistically significant growth in student understanding from pre- to posttest compared to the students who participated in the program the previous year. The findings also showed that there was a statistically significant association between teacher posttest PCK and student improvement in understanding even when controlling for years of teaching experience, teacher pretest knowledge, and student pretest score. This adds to the research base additional evidence that professional development focused on teacher pedagogical content knowledge can have a positive effect on student achievement, even with just a short period of PD (6 hours in this case). / text

We consider combinatorial t-design problems as discrete optimization problems. Our motivation is that only a few studies have been done on the use of exact optimization techniques in designs, and that classical methods in design theory have still left many open existence questions. Roughly defined, t-designs are pairs of discrete sets that are related following some strict properties of size, balance, and replication. These highly structured relationships provide optimal solutions to a variety of problems in computer science like error-correcting codes, secure communications, network interconnection, design of hardware; and are applicable to other areas like statistics, scheduling, games, among others. We give a new approach to combinatorial t-designs that is useful in constructing t-designs by polyhedral methods. The first contribution of our work is a new result of equivalence of t-design problems with a graph theory problem. This equivalence leads to a novel integer programming formulation for t-designs, which we call GDP. We analyze the polyhedral properties of GDP and conclude, among other results, the associated polyhedron dimension. We generate new classes of valid inequalities to aim at approximating this integer program by a linear program that has the same optimal solution. Some new classes of valid inequalities are generated as Chv´atal-Gomory cuts, other classes are generated by graph complements and combinatorial arguments, and others are generated by the use of incidence substructures in a t-design. In particular, we found a class of valid inequalities that we call stable-set class that represents an alternative graph equivalence for the problem of finding a t-design. We analyze and give results on the strength of these new classes of valid inequalities. We propose a separation problem and give its integer programming formulation as a maximum (or minimum) edge-weight biclique subgraph problem. We implement a pure cutting-plane algorithm using one of the stronger classes of valid inequalities derived. Several instances of t-designs were solved efficiently by this algorithm at the root node of the search tree. Also, we implement a branch-and-cut algorithm and solve several instances of 2-designs trying different base formulations. Computational results are included.

Many problems that arise in the real world are difficult to solve partly because they present computational challenges. Many of these challenging problems are optimization problems. In the real world we are generally interested not just in solutions but in the cost or benefit of these solutions according to different metrics. Hence, finding optimal solutions is often highly desirable and sometimes even necessary. The most effective computational approach for solving such problems is to first model them in a mathematical or logical language, and then solve them by applying a suitable algorithm. This thesis is concerned with developing practical algorithms to solve optimization problems modeled in a particular logical language, MAXSAT. MAXSAT is a generalization of the famous Satisfiability (SAT) problem, that associates finite costs with falsifying various desired conditions where these conditions are expressed as propositional clauses. Optimization problems expressed in MAXSAT typically have two interacting components: the logical relationships between the variables expressed by the clauses, and the optimization component involving minimizing the falsified clauses. The interaction between these components greatly contributes to the difficulty of solving MAXSAT. The main contribution of the thesis is a new hybrid approach, MaxHS, for solving MAXSAT. Our hybrid approach attempts to decouple these two components so that each can be solved with a different technology. In particular, we develop a hybrid solver that exploits two sophisticated technologies with divergent strengths: SAT for solving the logical component, and Integer Programming (IP) solvers for solving the optimization component. MaxHS automatically and incrementally splits the MAXSAT problem into two parts that are given to the SAT and IP solvers, which work together in a complementary way to find a MAXSAT solution. The thesis investigates several improvements to the MaxHS approach and provides empirical analysis of its behaviour in practise. The result is a new solver, MaxHS, that is shown to be the most robust existing solver for MAXSAT.

Many problems that arise in the real world are difficult to solve partly because they present computational challenges. Many of these challenging problems are optimization problems. In the real world we are generally interested not just in solutions but in the cost or benefit of these solutions according to different metrics. Hence, finding optimal solutions is often highly desirable and sometimes even necessary. The most effective computational approach for solving such problems is to first model them in a mathematical or logical language, and then solve them by applying a suitable algorithm. This thesis is concerned with developing practical algorithms to solve optimization problems modeled in a particular logical language, MAXSAT. MAXSAT is a generalization of the famous Satisfiability (SAT) problem, that associates finite costs with falsifying various desired conditions where these conditions are expressed as propositional clauses. Optimization problems expressed in MAXSAT typically have two interacting components: the logical relationships between the variables expressed by the clauses, and the optimization component involving minimizing the falsified clauses. The interaction between these components greatly contributes to the difficulty of solving MAXSAT. The main contribution of the thesis is a new hybrid approach, MaxHS, for solving MAXSAT. Our hybrid approach attempts to decouple these two components so that each can be solved with a different technology. In particular, we develop a hybrid solver that exploits two sophisticated technologies with divergent strengths: SAT for solving the logical component, and Integer Programming (IP) solvers for solving the optimization component. MaxHS automatically and incrementally splits the MAXSAT problem into two parts that are given to the SAT and IP solvers, which work together in a complementary way to find a MAXSAT solution. The thesis investigates several improvements to the MaxHS approach and provides empirical analysis of its behaviour in practise. The result is a new solver, MaxHS, that is shown to be the most robust existing solver for MAXSAT.

Chlamydia Trachomatis and Neisseria Gonorrhoeae rank as the two most commonly reported sexually transmitted diseases (STDs) in the United States. Under limited budget, publicly funded clinics are not able to screen and treat the two diseases for all patients. They have to make a decision as to which group of population shall go through the procedure for screening and treating the two diseases. Therefore, we propose a cubic integer programming model on maximizing the number of units of cured diseases. At the same time, a two-step algorithm is established to solve the cubic integer program. We further develop a web-server, which immediately make recommendation on identifying population groups, screening assays and treatment regimens. Running on the empirical data provided by the Centers for Disease Control and Prevention, our program gives more accurate optimal results comparing to MS Excel solver within a very short time.

An integer-valued polynomial is a polynomial with rational coefficients that takes an integer value when evaluated at an integer. The binomial polynomials form a regular basis for the Z-module of all integer-valued polynomials. Using the idea of a p-ordering and a p-sequence, Bhargava describes a similar characterization for polynomials that are integer-valued on some subset of the integers. This thesis focuses on characterizing the polynomials that are integer-valued on the Fibonacci numbers. For a certain class of primes p, we give a formula for the p-sequence of the Fibonacci numbers and an algorithm for finding a p-ordering using Coelho and Parry’s results on the distribution of the Fibonacci numbers modulo powers of primes. Knowing the p-sequence, we can then find a p-local regular basis for the polynomials that are integer-valued on the Fibonacci numbers using Bhargava’s methods. A regular basis can be constructed from p-local bases for all primes p.

Knapsack problem has been widely studied in computer science for years. There exist several variants of the problem, with zero-one maximum knapsack in one dimension being the simplest one. In this thesis we study several existing approximation algorithms for the minimization version of the problem and propose a scaling based fully polynomial time approximation scheme for the minimum knapsack problem. We compare the performance of this algorithm with existing algorithms. Our experiments show that, the proposed algorithm runs fast and has a good performance ratio in practice. We also conduct extensive experiments on the data provided by Canadian Pacific Logistics Solutions during the MITACS internship program. We propose a scaling based e-approximation scheme for the multidimensional (d-dimensional) minimum knapsack problem and compare its performance with a generalization of a greedy algorithm for minimum knapsack in d dimensions. Our experiments show that the e- approximation scheme exhibits good performance ratio in practice. / x, 85 leaves ; 29 cm

The release of flammable and toxic chemicals in petrochemical facilities is a major concern when designing modern process safety systems. While the proper selection of the necessary types of gas detectors needed is important, appropriate placement of these detectors is required in order to have a well-functioning gas detection system. However, the uncertainty in leak locations, gas composition, process and weather conditions, and process geometries must all be considered when attempting to determine the appropriate number and placement of the gas detectors. Because traditional approaches are typically based on heuristics, there exists the need to develop more rigorous optimization based approaches to handling this problem. This work presents several mixed-integer programming formulations to address this need. First, a general mixed-integer linear programming problem is presented. This formulation takes advantage of precomputed computational fluid dynamics (CFD) simulations to determine a gas detector placement that minimizes the expected detection time across all scenarios. An extension to this formulation is added that considers the overall coverage in a facility in order to improve the detector placement when enough scenarios may not be available. Additionally, a formulation considering the Conditional-Value-at-Risk is also presented. This formulation provides some control over the shape of the tail of the distribution, not only minimizing the expected detection time across all scenarios, but also improving the tail behavior. In addition to improved formulations, procedures are introduced to determine confidence in the placement generated and to determine if enough scenarios have been used in determining the gas detector placement. First, a procedure is introduced to analyze the performance of the proposed gas detector placement in the face of “unforeseen” scenarios, or scenarios that were not necessarily included in the original formulation. Additionally, a procedure for determine the confidence interval on the optimality gap between a placement generated with a sample of scenarios and its estimated performance on the entire uncertainty space. Finally, a method for determining if enough scenarios have been used and how much additional benefit is expected by adding more scenarios to the optimization is proposed. Results are presented for each of the formulations and methods presented using three data sets from an actual process facility. The use of an off-the-shelf toolkit for the placement of detectors in municipal water networks from the EPA, known as TEVA-SPOT, is explored. Because this toolkit was not designed for placing gas detectors, some adaptation of the files is necessary, and the procedure for doing so is presented.

This dissertation explores methods for finding irreducible infeasible subsystems (IISs) of systems of inequalities with binary decision variables and for solving probabilistically constrained stochastic integer programs (SIP-C). Finding IISs for binary systems is useful in decomposition methods for SIP-C. SIP-C has many important applications including modeling of strategic decision-making problems in wildfire initial response planning. New theoretical results and two new algorithms to find IISs for systems of inequalities with binary variables are developed. The first algorithm uses the new theory and the method of the alternative polyhedron within a branch-and-bound (BAB) approach. The second algorithm applies the new theory and the method of the alternative polyhedron to a system in which zero/one box constraints are appended. Decomposition schemes using IISs for binary systems can be used to solve SIP-C. SIP-C is challenging to solve due to the generally non-convex feasible region. In addition, very weak lower (upper) bounds on the objective function are obtained from the linear programming (LP) relaxation of the deterministic equivalent problem (DEP) to SIP-C. This work develops a branch-and-cut (BAC) method based on IIS inequalities to solve SIP-C with random technology matrix and random righthand- side vector. Computational results show that the LP relaxation of the DEP to SIP-C can be strengthened by the IIS inequalities. SIP-C modeling can be applied to wildfire initial response planning. A new methodology for wildfire initial response that includes a fire behavior simulation model, a wildfire risk model, and SIP-C is developed and tested. The new method- ology assumes a known standard response needed to contain a fire of given size. Likewise, this methodology is used to evaluate deployment decisions in terms of the number of firefighting resources positioned at each base, the expected number of escaped and contained fires, as well as the wildfire risk associated with fires not receiving a standard response. A study based on the Texas district 12 (TX12) that is one of the Texas A&M Forest Service (TFS) fire planning units in east Texas demonstrates the effectiveness of the new methodology towards making strategic deployment decisions for wildfire initial response planning.

No description available.