This thesis discusses how to use topology and shape optimization, specifically the level set method, for innovative design. The level set method is a numerical algorithm that simulates the expansion of dynamic implicit surfaces. In this research, the equations for manufacturability are generated and solved through use of the level set method joined with the COMSOL multi-physics package. Specific constraints are added to make the optimization practical for engineering design. The resulting method was applied to design the best underlying support structure, conforming to both curvature and manufacturability constraints, for the longerons used with the International Space Station solar panels.

The problem of pricing a product line to maximize profits is an important challenge faced by many companies. To address this problem, we discuss four different probabilistic choice models that are based on reservation prices: the Uniform Distribution Model, the Weighted Uniform Model, the Share-of-Surplus Model, and the Price Sensitive Model. They are formulated as convex mixed-integer mathematical programs. We explore the properties and additional valid inequalities of these formulations. We also compare their optimal solutions on a set of inputs. In general, the Uniform Distribution, Weighted Uniform, and Price Sensitive Models have the same optimal solution while the Share-of-Surplus Model gives a different solution in many cases. We develop a few heuristics for finding good feasible solutions. These simple and efficient heuristics perform well and help to improve the solution time. Computational results of solving problem instances of various sizes are shown.

This thesis focuses on convex sets and convex cones defined using hyperbolic polynomials. We first review some of the theory of convex sets in $\R^d$ in general. We then review some classical algebraic theorems concerning polynomials in a single variable, as well as presenting a few more modern results about them. We then discuss the theory of hyperbolic polynomials in several variables and their associated hyperbolicity cones. We survey various ways to build and decompose hyperbolic cones and we prove that every nontrivial hyperbolic cone is the intersection of its derivative cones. We conclude with a brief discussion of the set of extreme rays of a hyperbolic cone.

Zip.ca is an online DVD rental company that faces two major operational problems: calculation of the assignment of DVDs to customers every thirty minutes throughout the day and purchasing of new inventory in regular intervals. In this thesis, we model these two problems and develop algorithms to solve them. In doing so, we encounter many theoretical problems that are both applicable to Zip’s operations and intrinsically interesting problems independent of the application. First, we note that the assignment problem facing Zip is inherently in an online setting. With returns of DVDs being processed throughout the day, the dataset is constantly changing. Although the ideal solution would be to wait until the end of the day to make decisions, physical work load capacities prevent this. For this reason we discuss two online problems, online 0-1 budgeted matching and the budgeted Adwords auction. We present a 1/(2 w_max/w_min)-competitive algorithm for the online 0-1 budgeted matching problem, and prove that this is the best possible competitive ratio possible for a wide class of algorithms. We also give a (1− (S+1)/(S+e) )-competitive algorithm for the budgeted Adwords auction as the size of the bids and cost get small compared to the budgets, where S is the ratio of the highest and lowest ratios of bids to costs. We suggest a linear programming approach to solve Zip’s assignment problem. We develop an integer program that models the B-matching instance with additional constraints of concern to Zip, and prove that this integer program belongs to a larger class of integer programs that has totally unimodular constraint matrices. Thus, the assignment problem can be solved to optimality every thirty minutes. We additionally create a test environment to check daily performance, and provide real-time implementation results, showing a marked improvement over Zip’s old algorithm. We show that Zip’s purchasing problem can be modeled by the matching augmentation problem defined as follows. Given a graph with vertex capacities and costs, edge weights, and budget C, find a purchasing of additional node capacity of cost at most C that admits a B-matching of maximum weight. We give a PTAS for this problem, and then present a special case that is polynomial time solvable that still models Zip’s purchasing problem, under the assumption of uniform costs. We then extend the augmentation idea to matroids and present matroid augmentation, matroid knapsack, and matroid intersection knapsack, three NP-hard problems. We give an FPTAS for matroid knapsack by dynamic programming, PTASes for the other two, and demonstrate applications of these problems.

The problem of pricing a product line to maximize profits is an important challenge faced by many companies. To address this problem, we discuss four different probabilistic choice models that are based on reservation prices: the Uniform Distribution Model, the Weighted Uniform Model, the Share-of-Surplus Model, and the Price Sensitive Model. They are formulated as convex mixed-integer mathematical programs. We explore the properties and additional valid inequalities of these formulations. We also compare their optimal solutions on a set of inputs. In general, the Uniform Distribution, Weighted Uniform, and Price Sensitive Models have the same optimal solution while the Share-of-Surplus Model gives a different solution in many cases. We develop a few heuristics for finding good feasible solutions. These simple and efficient heuristics perform well and help to improve the solution time. Computational results of solving problem instances of various sizes are shown.

This thesis focuses on convex sets and convex cones defined using hyperbolic polynomials. We first review some of the theory of convex sets in $\R^d$ in general. We then review some classical algebraic theorems concerning polynomials in a single variable, as well as presenting a few more modern results about them. We then discuss the theory of hyperbolic polynomials in several variables and their associated hyperbolicity cones. We survey various ways to build and decompose hyperbolic cones and we prove that every nontrivial hyperbolic cone is the intersection of its derivative cones. We conclude with a brief discussion of the set of extreme rays of a hyperbolic cone.

Zip.ca is an online DVD rental company that faces two major operational problems: calculation of the assignment of DVDs to customers every thirty minutes throughout the day and purchasing of new inventory in regular intervals. In this thesis, we model these two problems and develop algorithms to solve them. In doing so, we encounter many theoretical problems that are both applicable to Zip’s operations and intrinsically interesting problems independent of the application. First, we note that the assignment problem facing Zip is inherently in an online setting. With returns of DVDs being processed throughout the day, the dataset is constantly changing. Although the ideal solution would be to wait until the end of the day to make decisions, physical work load capacities prevent this. For this reason we discuss two online problems, online 0-1 budgeted matching and the budgeted Adwords auction. We present a 1/(2 w_max/w_min)-competitive algorithm for the online 0-1 budgeted matching problem, and prove that this is the best possible competitive ratio possible for a wide class of algorithms. We also give a (1− (S+1)/(S+e) )-competitive algorithm for the budgeted Adwords auction as the size of the bids and cost get small compared to the budgets, where S is the ratio of the highest and lowest ratios of bids to costs. We suggest a linear programming approach to solve Zip’s assignment problem. We develop an integer program that models the B-matching instance with additional constraints of concern to Zip, and prove that this integer program belongs to a larger class of integer programs that has totally unimodular constraint matrices. Thus, the assignment problem can be solved to optimality every thirty minutes. We additionally create a test environment to check daily performance, and provide real-time implementation results, showing a marked improvement over Zip’s old algorithm. We show that Zip’s purchasing problem can be modeled by the matching augmentation problem defined as follows. Given a graph with vertex capacities and costs, edge weights, and budget C, find a purchasing of additional node capacity of cost at most C that admits a B-matching of maximum weight. We give a PTAS for this problem, and then present a special case that is polynomial time solvable that still models Zip’s purchasing problem, under the assumption of uniform costs. We then extend the augmentation idea to matroids and present matroid augmentation, matroid knapsack, and matroid intersection knapsack, three NP-hard problems. We give an FPTAS for matroid knapsack by dynamic programming, PTASes for the other two, and demonstrate applications of these problems.

Petroleum refining processes provide the daily requirements of energy for the global market. Each refining process produces wastes that have the capacity to harm the environment if not properly disposed of. The treatment of refinery waste is one of the most complex issues faced by refinery managers. Also, the hazardous nature of these wastes makes them rather costly to dispose of for the refineries. In this thesis, system analysis tools are used to design a program that allows for the selection of the optimal control, minimization and treating options for petroleum refinery waste streams. The performance of the developed model is demonstrated via a case study. Optimal mitigation alternatives to meet the emission reduction targets were studied by evaluating their relative impact on the profitable operation of the given facility. It was found that the optimal mitigation steps was to reduce emission precursors by conducting feed switches at the refinery. In all cases, the optimal solution did not include a capital expansion of the emission control facilities and equipment.

No description available.

No description available.