The problem of finding a shortest TDMA is formally described as anInteger Program (IP). A brief user manual explains how the attached implementation can be used to find an optimal size TDMA for any givenWSN and routing table, fulfilling the validity criteria.

Various kinds of optimization problems involve nonlinear functions of binary variables that exhibit a property of diminishing marginal returns. Such a property is known as submodularity. Vast amount of work has been devoted to the problem of submodular optimization. In this thesis, we exploit structural information for several classes of submodular optimization problems. We strive for polynomial time algorithms with improved approximation ratio and strong mixed-integer linear formulations of mixed-integer non-linear programs where the epigraph and hypograph of submodular functions of a specific form appear as a substructure together with other side constraints. In Chapter 2, we develop approximation algorithms for the expected utility knapsack problem. We use the sample average approximation framework to approximate the stochastic problem as a deterministic knapsack-constrained submodular maximization problem, and then use an approximation algorithm to solve the deterministic counterpart. We show that a polynomial number of samples are enough for a deterministic approximation that is close in relative error. Then, exploiting the strict monotonicity of typical utility functions, we present an algorithm that maximizes an increasing submodular function over a knapsack constraint with approximation ratio better than the classical $(1-1/e)$ ratio. In Chapter 3, we present polyhedral results for the expected utility knapsack problem. We study a mixed-integer nonlinear set that is the hypograph of $f(a'x)$ together together with a knapsack constraint. We propose a family of inequalities for the convex hull of the nonlinear set by exploiting both the structure of the submodular function $f(a'x)$ and the knapsack constraint. Effectiveness of the proposed inequalities is shown by computational experiments on expected utility maximization problem with budget constraint using a branch-and-cut framework. In Chapter 4, we study a mixed-integer nonlinear set that is the epigraph of $f(a'x)$ together with a cardinality constraint. This mixed-integer nonlinear set arises as a substructure in various constrained submodular minimization problems. We develop a strong linear formulation of the convex hull of the nonlinear set by exploiting both the submodularity of $f(a'x)$ and the cardinality constraint. We provide a full description of the convex hull of the nonlinear set when the vector a has identical components. We also develop a family of facet-defining inequalities when the vector a has nonidentical components. We demonstrate the effectiveness of the proposed inequalities by solving mean-risk knapsack problems using a branch-and-cut framework.

Mine-mill production faces several operational difficulties, such as fluctuations in ore delivery from mines, random failure of machines, usage of stockpiles and storage bins, and changeover time when switching products. This study was initiated at a particular Canadian mining company. However, changes in the economic condition in the mining industry during 2008 have meant that circumstances have changed to the extent that this work should be seen as an illustration of methods rather than a study of the specific situation at the mining company. This mining company will remain unnamed throughout this thesis. The purpose of this research is to develop a series of production campaigns, each of which uses a specific draw scheme to coordinate the receiving of ore, maintenance planning and product scheduling. The approach includes a combination of mathematical programming model and a simulation model. The solution from the integer programming model is a set of campaigns that minimize the inventory levels of unprocessed ore, the number of days on shutdown, and the number of active piles required at any point in time. The simulation model uses this solution as its production scheduling input with integrated stochastic elements to evaluate mill system performance. In this thesis, the formulation of the mathematical programming model and construction of the simulation model, as well as the maintenance data analysis used as stochastic element of the model is discussed.

No description available.

No description available.

No description available.

No description available.

No description available.

No description available.

No description available.