We study a generic minimization problem with separable non-convex piecewise linear costs, showing that the linear programming (LP) relaxation of three textbook mixed integer programming formulations each approximates the cost function by its lower convex envelope. We also show a relationship between this result and classical Lagrangian duality theory.

The United State’s renewable portfolio standards call for a large increase of renewable energy and improved conservation efforts over today’s current system. Wind will play a ma jor role in meeting the renewable portfolio standards. As a result, the amount of wind capacity and generation has been growing exponentially over the past 10 to 15 years. The proposed unit commitment method integrates wind energy into a scheduable resource while keeping the formulation simple using mixed integer programming. A reserve constraint is developed and added to unit commitment giving the forecasted wind energy an effective cost. The reserve constraint can be scaled based on the needs of the system: cost, reliability, or the penetration of wind energy. The results show that approximately 24% of the load can be met in the given test system, while keeping a constant reliability before and after wind is introduced. This amount of wind will alone meet many of the renewable portfolio standards in the United States.

Thesis (Ph. D.)--University of Chicago Graduate School of Business, December 1997. / Includes bibliographical references.

The segmentation problem arises in the elaboration of a radiation therapy plan. After the cancer has been diagnosed and the radiation therapy sessions have been prescribed, the physician has to locate the tumor as well as the organs situated in the radiation field, called the organs at risk. The physician also has to determine the different dosage he wants to deliver in each of them and has to define a lower bound on the dosage for the tumor (which represents the minimum amount of radiation that is needed to have a sufficient control of the tumor) and an upper bound for each organ at risk (which represents the maximum amount of radiation that an organ can receive without damaging). Designing a radiation therapy plan that respects these different bounds of dosage is a complex optimization problem that is usually tackled in three steps. The segmentation problem is one of them. Mathematically, the segmentation problem amounts to decomposing a given nonnegative integer matrix A into a nonnegative integer linear combination of some binary matrices. These matrices have to respect the consecutive ones property. In clinical applications several constraints may arise that reduce the set of binary matrices which respect the consecutive ones property that we can use. We study some of them, as the interleaf distance constraint, the interleaf motion constraint, the tongue-and-groove constraint and the minimum separation constraint. We consider here different versions of the segmentation problem with different objective functions. Hence we deal with the beam-on time problem in order to minimize the total time during which the patient is irradiated. We study this problem under the interleaf distance and the interleaf motion constraints. We consider as well this last problem under the tongue-and-groove constraint in the binary case. We also take into account the cardinality and the lex-min problem. Finally, we present some results for the approximation problem. /Le problème de segmentation intervient lors de l'élaboration d'un plan de radiothérapie. Après que le médecin ait localisé la tumeur ainsi que les organes se situant à proximité de celle-ci, il doit aussi déterminer les différents dosages qui devront être délivrés. Il détermine alors une borne inférieure sur le dosage que doit recevoir la tumeur afin d'en avoir un contrôle satisfaisant, et des bornes supérieures sur les dosages des différents organes situés dans le champ. Afin de respecter au mieux ces bornes, le plan de radiothérapie doit être préparé de manière minutieuse. Nous nous intéressons à l'une des étapes à réaliser lors de la détermination de ce plan: l'étape de segmentation. Mathématiquement, cette étape consiste à décomposer une matrice entière et positive donnée en une combinaison positive entière linéaire de certaines matrices binaires. Ces matrices binaires doivent satisfaire la contrainte des uns consécutifs (cette contrainte impose que les uns de ces matrices soient regroupés en un seul bloc sur chaque ligne). Dans les applications cliniques, certaines contraintes supplémentaires peuvent restreindre l'ensemble des matrices binaires ayant les uns consécutifs (matrices 1C) que l'on peut utiliser. Nous en avons étudié certaines d'entre elles comme celle de la contrainte de chariots, la contrainte d'interdiciton de chevauchements, la contrainte tongue-and-groove et la contrainte de séparation minimum. Le premier problème auquel nous nous intéressons est de trouver une décomposition de la matrice donnée qui minimise la somme des coefficients des matrices binaires. Nous avons développé des algorithmes polynomiaux qui résolvent ce problème sous la contrainte de chariots et/ou la contrainte d'interdiction de chevauchements. De plus, nous avons pu déterminer que, si la matrice donnée est une matrice binaire, on peut trouver en temps polynomial une telle décomposition sous la contrainte tongue-and-groove. Afin de diminuer le temps de la séance de radiothérapie, il peut être désirable de minimiser le nombre de matrices 1C utilisées dans la décomposition (en ayant pris soin de préalablement minimiser la somme des coefficients ou non). Nous faisons une étude de ce problème dans différents cas particuliers (la matrice donnée n'est constituée que d'une colonne, ou d'une ligne, ou la plus grande entrée de celle-ci est bornée par une constante). Nous présentons de nouvelles bornes inférieures sur le nombre de matrices 1C ainsi que de nouvelles heuristiques. Finalement, nous terminons par étudier le cas où l'ensemble des matrices 1C ne nous permet pas de décomposer exactement la matrice donnée. Le but est alors de touver une matrice décomposable qui soit aussi proche que possible de la matrice donnée. Après avoir examiné certains cas polynomiaux nous prouvons que le cas général est difficile à approximer avec une erreur additive de O(mn) où m et n représentent les dimensions de la matrice donnée.

The mobility allowance shuttle transit (MAST) system is a hybrid transit system in which vehicles are allowed to deviate from a fixed route to serve flexible demand. A mixed integer programming (MIP) formulation for the static scheduling problem of a multi-vehicle Mobility Allowance Shuttle Transit (MAST) system is proposed in this thesis. Based on the MIP formulation, we analyze the impacts of time headways between consecutive transit vehicles on the performance of a two-vehicle MAST system. An analytical framework is then developed to model the performance of both one-vehicle and two-vehicle MAST systems, which is used to identify the critical demand level at which an increase of the fleet size from one to two vehicles would be appropriate. Finally, a sensitivity analysis is conducted to find out the impact of a key modeling parameter, w1, the weight of operations cost on the critical demand. In this paper, we develop an insertion heuristic for a multi-vehicle MAST system, which has never been addressed in the literature. The proposed heuristic is validated and evaluated by a set of simulations performed at different demand levels and with different control parameters. By comparing its performance versus the optimal solutions, the effectiveness of the heuristic is confirmed. Compared to its single-vehicle counterpart, the multiple-vehicle MAST prevails in terms of rejection rate, passenger waiting time and overall objective function, among other performance indices.

The Discrete Wavelet Transform (DWT) is a popular tool in the field of image and video compression applications. Because of its multi-resolution representation capability, the DWT has been used effectively in applications such as transient signal analysis, computer vision, texture analysis, cell detection, and image compression. Daubechies wavelets are one of the popular transforms in the wavelet family. Daubechies filters provide excellent spatial and spectral locality-properties which make them useful in image compression.<p> In this thesis, we present an efficient implementation of a shared hardware core to compute two 8-point Daubechies wavelet transforms. The architecture is based on a new two-level folded mapping technique, an improved version of the Algebraic Integer Quantization (AIQ). The scheme is developed on the factorization and decomposition of the transform coefficients that exploits the symmetrical and wrapping structure of the matrices. The proposed architecture is parallel, pipelined, and multiplexed. Compared to existing designs, the proposed scheme reduces significantly the hardware cost, critical path delay and power consumption with a higher throughput rate.<p> Later, we have briefly presented a new mapping scheme to error-freely compute the Daubechies-8 tap wavelet transform, which is the next transform of Daubechies-6 in the Daubechies wavelet series. The multidimensional technique maps the irrational transformation basis coefficients with integers and results in considerable reduction in hardware and power consumption, and significant improvement in image reconstruction quality.

This study addresses the problem of designing a new natural gas transmission network or expanding an existing network while minimizing the total investment and operating costs. A substantial reduction in costs can be obtained by effectively designing and operating the network. A well-designed network helps natural gas companies minimize the costs while increasing the customer service level. The aim of the study is to determine the optimum installation scheduling and locations of new pipelines and compressor stations. On an existing network, the model also optimizes the total flow through pipelines that satisfy demand to determine the best purchase amount of gas. A mixed integer nonlinear programming model for steady-state natural gas transmission problem on tree-structured network is introduced. The problem is a multi-period model, so changes in the network over a planning horizon can be observed and decisions can be made accordingly in advance. The problem is modeled and solved with easily accessible modeling and solving tools in order to help decision makers to make appropriate decisions in a short time. Various test instances are generated, including problems with different sizes, period lengths and cost parameters, to evaluate the performance and reliability of the model. Test results revealed that the proposed model helps to determine the optimum number of periods in a planning horizon and the crucial cost parameters that affect the network structure the most.

No description available.

No description available.

No description available.