A wireless sensor network consists of a number of sensor devices and coordinator(s) or sink(s). A coordinator collects the sensed data from the sensor devices for further processing. In such networks, sensor devices are generally powered by batteries. Since wireless transmission of packets consumes significant amount of energy, it is important for a network to adopt a medium access control (MAC) technology which is energy efficient and satisfies the communication performance requirements. Carrier sense multiple access with collision avoidance (CSMA/CA), which is a popular access technique because of its simplicity, flexibility and robustness, suffers poor throughput and energy inefficiency performance in wireless sensor networks. On the other hand, time division multiple access (TDMA) is a collision free and delay bounded access technique but suffers from the scalability problem. For this reason, this thesis focuses on design and analysis of hybrid channel access schemes which combine the strengths of both the CSMA/CA and TDMA schemes. In a hybrid CSMA/CA-TDMA scheme, the use of the CSMA/CA period and the TDMA period can be optimized to enhance the communication performance in the network. If such a hybrid channel access scheme is not designed properly, high congestion during the CSMA/CA period and wastage of bandwidth during the TDMA period result in poor communication performance in terms of throughput and energy efficiency. To address this issue, distributed and centralized channel access schemes are proposed to regulate the activities (such as transmitting, receiving, idling and going into low power mode) of the sensor devices. This regulation during the CSMA/CA period and allocation of TDMA slots reduce traffic congestion and thus improve the network performance. In this thesis work, time slot allocation methods in hybrid CSMA/CA-TDMA schemes are also proposed and analyzed to improve the network performance. Finally, such hybrid CSMA/CA-TDMA schemes are used in a cellular layout model for the multihop wireless sensor network to mitigate the hidden terminal collision problem.

abstract: Mobile healthy food retailers are a novel alleviation technique to address disparities in access to urban produce stores in food desert communities. Such retailers, which tend to exclusively stock produce items, have become significantly more popular in the past decade, but many are unable to achieve economic sustainability. Therefore, when local and federal grants and scholarships are no longer available for a mobile food retailer, they must stop operating which poses serious health risks to consumers who rely on their services. To address these issues, a framework was established in this dissertation to aid mobile food retailers with reaching economic sustainability by addressing two key operational decisions. The first decision was the stocked product mix of the mobile retailer. In this problem, it was assumed that mobile retailers want to balance the health, consumer cost, and retailer profitability of their product mix. The second investigated decision was the scheduling and routing plan of the mobile retailer. In this problem, it was assumed that mobile retailers operate similarly to traditional distribution vehicles with the exception that their customers are willing to travel between service locations so long as they are in close proximity. For each of these problems, multiple formulations were developed which address many of the nuances for most existing mobile food retailers. For each problem, a combination of exact and heuristic solution procedures were developed with many utilizing software independent methodologies as it was assumed that mobile retailers would not have access to advanced computational software. Extensive computational tests were performed on these algorithm with the findings demonstrating the advantages of the developed procedures over other algorithms and commercial software. The applicability of these techniques to mobile food retailers was demonstrated through a case study on a local Phoenix, AZ mobile retailer. Both the product mix and routing of the retailer were evaluated using the developed tools under a variety of conditions and assumptions. The results from this study clearly demonstrate that improved decision making can result in improved profits and longitudinal sustainability for the Phoenix mobile food retailer and similar entities. / Dissertation/Thesis / Doctoral Dissertation Industrial Engineering 2016

MRI is a very useful imaging modality in medical imaging for both diagnostic as well as functional studies. It provides excellent soft tissue contrast in several diagnostic studies. It is widely used to study the functional aspects of brain and to study the diffusion of water molecules across tissues. Image acquisition in MR is slow due to longer data acquisition time, gradient ramp-up and stabilization delays. Repetitive scans are also needed to overcome any artefacts due to patient motion, field inhomogeneity and to improve signal to noise ratio (SNR). Scanning becomes di cult in case of claustrophobic patients, and in younger/older patients who are unable to cooperate and prone to uncontrollable motions inside the scanner. New MR procedures, advanced research in neuro and functional imaging are demanding better resolutions and scan speeds which implies there is need to acquire more data in a shorter time frame. The hardware approach to faster k-space scanning methods involves efficient pulse sequence and gradient waveform design methods. Such methods have reached a physical and physiological limit. Alternately, methods have been proposed to reduce the scan time by under sampling the k-space data. Since the advent of Compressive Sensing (CS), there has been a tremendous interest in developing under sampling matrices for MRI. Mathematical assumptions on the probability distribution function (pdf) of k-space have led researchers to come up with efficient under sampling matrices for sampling MR k-space data. The recent approaches adaptively sample the k-space, based on the k-space of reference image as the probability distribution instead of a mathematical distribution, to come with an efficient under sampling scheme. In general, the methods use a deterministic central circular/square region and probabilistic sampling of the rest of the k-space. In these methods, the sampling distribution may not follow the selected pdf and viii Adaptive Sampling Pattern Design Methods for MR Images the selection of deterministic and probabilistic sampling distribution parameters are heuristic in nature. Two novel adaptive Variable Density Sampling (VDS) methods are proposed to address the heuristic nature of the sampling k-space such that the selected pdf matches the k-space energy distribution of a given fully sampled reference k-space or the MR image. The proposed methods use a novel approach of binning the pdf derived from the fully sampled k-space energy distribution of a reference image. The normalized k-space magnitude spectrum of the reference image is taken as a 2D probability distribution function which is divided in to number of exponentially weighted magnitude bins obtained from the corresponding histogram of the k-space magnitude spectrum. In the first method, the normalized k-space histogram is binned exponentially, and the resulting exponentially binned 2D pdf is used with a suitable control parameter to obtain a sampling pattern of desired under sampling ratio. The resulting sampling pattern is an adaptive VDS pattern mimicking the energy distribution of the original k-space. In the second method, the binning of the magnitude spectrum of k-space is followed by ranking of the bins by its spectral energy content. A cost function is de ned to evaluate the k-space energy being captured by the bin. The samples are selected from the energy rank ordered bins using a Knapsack constraint. The energy ranking and the Knapsack criterion result in the selection of sampling points from the highly relevant bins and gives a very robust sampling grid with well defined sparsity level. Finally, the feasibility of developing a single adaptive VDS sampling pattern for a organ specific or multi-slice MR imaging, using the concept of binning of magnitude spectrum of the k-space, is investigated. Based on the premise that k-space of different organs have a different energy distribution structure to one another, the MR images of organs can be classified based on their spectral content and develop a single adaptive VDS sampling pattern for imaging an organ or multiple slices of the same. The classification is done using the k-space bin histogram as feature vectors and k-means clustering. Based on the nearest distance to the centroid of the organ cluster, a template image is selected to generate the sampling grid for the organ under consideration. Using the state of the art MR reconstruction algorithms, the performance of the proposed novel adaptive Variable Density Sampling (VDS) methods using image quality measures is evaluated and compared with other VDS methods. The reconstructions show significant improvement in image quality parameters quantitatively and visual reduction in artefacts at 20% 15%, 10% and 5% under sampling

Thesis is based on original self-made application programmed at VBA in MS Excel 2007. The reason to build this application was integration of simulation Monte Carlo and chosen optimization methods. The application allows do simulation of the knapsack problem and of the assignment problem with uncertainty. The parameters of these models are possible to set up as changing values in dependence of chosen probability distribution. Output of the simulation is a probability recommendation which objects should be used. Choose of objects depend on optimized models. Results of both models are represented by statistical indexes, tables of parameters and graph.

背包問題是整數規劃中一個特殊的模式，雖然它可以運用一般整數規劃法則來處理， 但是由於它只含有一個限制，所以發展出更有效的法則也是可能的。在過去十幾年當 中，已發表出很多研究論文，這些研究結果已推動吾人對這問題作更進一步的探討， 並導出更有效的求解法則。 本文分六章共二十節，內容大致如下： （一）緒論。 （二）討論背包問題一些重要的求解法則及其性質與應用。 （三）討論陷縮背包問題（The collapsing knapsack problem ）之應用及求解法則 ，決定元由整數擴大為混合的情形（實數）。 （四）結論與建議。

The topic of this thesis is a cryptosystem, precisely a public key encryption scheme, that is based on the knapsack problem. At first we formulate terms like \mathcal{NP} -complete problem, one-way function, hard-core predicate, public key encryption scheme and semantic security which we connect in this thesis. After that we present the knapsack problem. Then we prove that the knapsack problem with appropriate parameters has a property that leads to semantic security of the encryption scheme which we present afterwards. This public key encryption scheme is based on the scheme proposed by Vadim Lyubashevsky, Adriana Palacio and Gil Segev. Powered by TCPDF (www.tcpdf.org)

Nesta tese é abordado o problema da mochila compartimentada e o problema de corte de estoque unidimensional acoplado ao problema dimensionamento de lotes. Para o problema da mochila compartimentada é apresentada a versão unidimensional e proposta a versão bidimensional, denominados como problema da mochila compartimentada unidimensional e problema da mochila compartimentada bidimensional, respectivamente. Para o problema de corte de estoque acoplado ao dimensionamento de lotes são apresentadas três variações: uma máquina para produzir um tipo de objeto; uma máquina para produzir vários tipos de objetos; múltiplas máquinas para produzir vários tipos de objetos. Algumas formulações matemáticas de programação inteira e inteira-mista, decomposições dos problemas em problema mestre e subproblemas e heurísticas baseadas no método geração de colunas são propostas para os problemas da mochila compartimenta e o problema acoplado. Em específico, para o problema acoplado são aplicadas decomposições Dantzig-Wolfe, que podem ser por período, por máquina ou por período e máquina. Além disso, uma heurística baseada em grafo E/OU é proposta para o problema da mochila compartimentada bidimensional / In this thesis we present the constrained compartmentalized knapsack problem and the one dimensional cutting stock problem integrated with the capacitated lot sizing problem. For the constrained compartmentalized knapsack problem, the one dimensional version is presented and the two dimensional version is proposed, called one-dimensional compartmentalized knapsack problem and two-dimensional compartmentalized knapsack problem, respectively. For the cutting stock problem integrated with the capacitated lot sizing problem three variations are considered: one machine to produce one type of object; one machine to produce multiple types of objects; multiple machines to produce multiple types of objects. Some integer and mixed programming formulations, decompositions of the problems in master problem and subproblems and heuristics based on column generation method are proposed for the compartmentalized knapsack problem and the cutting stock problem integrated with the capacitated lot sizing problem. In particular, the period, the machine, and the period and machine Dantzig- Wolfe decompositions are applied for the integrated problem. Moreover, a heuristic based on the graph AND/OR is proposed for the two-dimensional compartmentalized knapsack problem. Computational results show that these mathematical formulations and methods provide good solutions

Neste trabalho apresentamos dois modelos de otimização e um método heurístico de solução para tratar um problema de comprovação fiscal em exportações de commodities no Brasil. Dos modelos de otimização, um foi desenvolvido baseado no Problema de Dimensionamento de Lotes e outro no Problema da Mochila. O governo brasileiro estimula as exportações no país através de alguns benefícios fiscais, alguns desses, sendo possíveis através da comprovação fiscal das exportações de mercadorias acompanhadas de notas fiscais de tipo de operação de fim específico para a exportação. Os benefícios deixam de ser concedidos a partir da perda do prazo da comprovação fiscal da nota fiscal, que é realizado utilizando a Declaração Única de Exportação (DU-E). Cada nota fiscal possui uma data de emissão, dias de isenção fiscal, o percentual da alíquota de ICMS cobrado dependendo do estado emissor, os itens e suas quantidades. As decisões visam estabelecer as combinações de quais notas fiscais devem ser comprovadas em cada embarque de produtos para o mercado exterior, obedecendo às suas datas de isenção de modo a minimizar os impostos pagos devido aos vencimentos dos prazos de despachos das notas. Os resultados obtidos por meio do modelo matemático mostram que a política otimizada de embarque dos produtos das notas fiscais apresenta uma redução dos custos em aproximadamente 39% em determinadas situações. / In this paper we present two optimization models and a heuristic method to deal with a problem of export tax on Brazilian commodities. Regarding the optimization models, one was developed based on the lot-sizing problem and an other on the knapsack problem. The Brazilian government encourages local exportation through tax benefits, some of them being possible by the taxation of exported goods being accompanied by invoices of an operation type that is specific for the purpose of the export. These benefits cease to be granted as a result of exceeding the tax invoice verification period, which is granted using the Single Export Declaration (DU-E). Each invoice has a date issue, days of tax exemption, the percentage of the ICMS tax rate charged depending on the issuing state, the items and their quantities. The decisions aim to establish the combinations of which invoices must be presented for each shipment of products to the foreign market, obeying their exemption dates in order to minimize the taxes paid due the maturity of the delivery times on the documents. The results obtained using the mathematical model show that the optimized shipping policy for invoiced products presents a 39% reduction in costs in certain situations.

Every knapsack problem may be relaxed to a cyclic group problem. In 1969, Gomory found the subadditive characterization of facets of the master cyclic group problem. We simplify the subadditive relations by the substitution of complementarities and discover a minimal representation of the subadditive polytope for the master cyclic group problem. By using the minimal representation, we characterize the vertices of cardinality length 3 and implement the shooting experiment from the natural interior point. The shooting from the natural interior point is a shooting from the inside of the plus level set of the subadditive polytope. It induces the shooting for the knapsack problem. From the shooting experiment for the knapsack problem we conclude that the most hit facet is the knapsack mixed integer cut which is the 2-fold lifting of a mixed integer cut. We develop a cutting plane algorithm augmenting cutting planes generated by shooting, and implement it on Wong-Coppersmith digraphs observing that only small number of cutting planes are enough to produce the optimal solution. We discuss a relaxation of shooting as a clue to quick shooting. A max flow model on covering space is shown to be equivalent to the dual of shooting linear programming problem.

Computational grids are distributed systems composed of heterogeneous computing resources which are distributed geographically and administratively. These highly scalable systems are designed to meet the large computational demands of many users from scientific and business orientations. This dissertation address problems related to the allocation of the computing resources which compose a grid. First, the design of a pan-Canadian grid is presented. The design exploits the maturing stability of grid deployment toolkits, and introduces novel services for efficiently allocating the grids resources. The challenges faced by this grid deployment motivate further exploration in optimizing grid resource allocations. The primary contribution of this dissertation is one such technique for allocating grid resources. By applying a utility model to the grid allocation options, it is possible to quantify the relative merits of the various possible scheduling decisions. Indeed, a number of utility heuristics are derived to provide quality-of-service policies on the grid; these implement scheduling policies which favour efficiency and also allow users to intervene with urgent tasks. Using this model, the allocation problem is then formulated as a knapsack problem. Formulation in this manner allows for rapid solution times and results in nearly optimal allocations. The combined utility/knapsack approach to grid resource allocation is first presented in the allocation of single resource type, processors. By evaluating the approach with novel utility heuristics using both random and real workloads, it is shown to result in efficient schedules which have characteristics that match the intended policies. Additionally, two design and analysis techniques are performed to optimize the design of the utility/knapsack scheduler; these techniques play a significant role in practical adoption of the approach. Next, the utility/knapsack approach is extended to the allocation of multiple resource types. This extension generalizes the grid allocation solution a wider variety of resources, including processors, disk storage, and network bandwidth. The general technique, when combined with new heuristics for the varied resource types, is shown to result in improved performance against reference strategies. This dissertation concludes with a novel application of the utility/knapsack approach to fault-tolerant task scheduling. Computational grids typically feature many techniques for providing fault tolerance to the grid tasks, including retrying failed tasks or replicating running tasks. By applying the utility/knapsack approach, the relative merits of these varied techniques can be quantified, and the overall number of failures can be decreased subject to resource cost considerations.