The focus of this dissertation is the advancement of theory and computation related to exact precision mathematical programming. Optimization software based on floating-point arithmetic can return suboptimal or incorrect resulting because of round-off errors or the use of numerical tolerances. Exact or correct results are necessary for some applications. Implementing software entirely in rational arithmetic can be prohibitively slow. A viable alternative is the use of hybrid methods that use fast numerical computation to obtain approximate results that are then verified or corrected with safe or exact computation. We study fast methods for sparse exact rational linear algebra, which arises as a bottleneck when solving linear programming problems exactly. Output sensitive methods for exact linear algebra are studied. Finally, a new method for computing valid linear programming bounds is introduced and proven effective as a subroutine for solving mixed-integer linear programming problems exactly. Extensive computational results are presented for each topic.

Practically all everyday life tasks from economic transactions to entertainment depend on the availability of electricity. Some customers have come to expect a higher level of power quality and availability from their electric utility. Federal and state standards are now mandated for power service quality and utilities may be penalized if the number of interruptions exceeds the mandated standards. In order to meet the requirement for safety, reliability and quality of supply in distribution system, adaptive relaying and optimal network reconfiguration are proposed. By optimizing the system to be better prepared to handle a fault, the end result will be that in the event of a fault, the minimum number of customers will be affected. Thus reliability will increase. The main function of power system protection is to detect and remove the faulted parts as fast and as selectively as possible. The problem of coordinating protective relays in electric power systems consists of selecting suitable settings such that their fundamental protective function is met under the requirements of sensitivity, selectivity, reliability, and speed. In the proposed adaptive relaying approach, weather data will be incorporated as follows. By using real-time weather information, the potential area that might be affected by the severe weather will be determined. An algorithm is proposed for adaptive optimal relay setting (relays will optimally react to a potential fault). Different types of relays (and relay functions) and fuses will be considered in this optimization problem as well as their coordination with others. The proposed optimization method is based on mixed integer programming that will provide the optimal relay settings including pickup current, time dial setting, and different relay functions and so on. The main function of optimal network reconfiguration is to maximize the power supply using existing breakers and switches in the system. The ability to quickly and flexibly reconfigure the power system of an interconnected network of feeders is a key component of Smart Grid. New technologies are being injected into the distribution systems such as advanced metering, distribution automation, distribution generation and distributed storage. With these new technologies, the optimal network reconfiguration becomes more complicated. The proposed algorithms will be implemented and demonstrated on a realistic test system. The end result will be improved reliability. The improvements will be quantified with reliability indexes such as SAIDI.

Integer Programming (IP) is a powerful and widely-used formulation for combinatorial problems. The study of IP over the past several decades has led to fascinating theoretical developments, and has improved our ability to solve discrete optimization problems arising in practice. This thesis makes progress on algorithmic solutions for IP by building on combinatorial, geometric and Linear Programming (LP) approaches. We use a combinatorial approach to give an approximation algorithm for the feedback vertex set problem (FVS) in a recently developed Implicit Hitting Set framework. Our algorithm is a simple online algorithm which finds a nearly optimal FVS in random graphs. We also propose a planted model for FVS and show that an optimal hitting set for a polynomial number of subsets is sufficient to recover the planted subset. Next, we present an unexplored geometric connection between integer feasibility and the classical notion of discrepancy of matrices. We exploit this connection to show a phase transition from infeasibility to feasibility in random IP instances. A recent algorithm for small discrepancy solutions leads to an efficient algorithm to find an integer point for random IP instances that are feasible with high probability. Finally, we give a provably efficient implementation of a cutting-plane algorithm for perfect matchings. In our algorithm, cuts separating the current optimum are easy to derive while a small LP is solved to identify the cuts that are to be retained for later iterations. Our result gives a rigorous theoretical explanation for the practical efficiency of the cutting plane approach for perfect matching evident from implementations. In summary, this thesis contributes to new models and connections, new algorithms and rigorous analysis of well-known approaches for IP.

Major challenges in the management of blood supply chain are related to the shortage and wastage of the blood products. Given the perishability characteristics of blood which can be stored up to a limited number of days, if hospitals and blood centers keep an excessive number of blood units on inventory, wastages may occur. On the other hand, if sufficient number of blood units are not stored on inventory, shortages of this resource may cause the cancellations of important activities and increase the fatality rates at hospitals. Three mathematical models have been developed with the goal to improve the efficiency of blood related activities at blood centers and hospitals. The first model uses an integer programming (IP) approach to identify the optimal order levels that minimizes the total cost, shortage and wastage levels of blood products at a hospital within a specified planning horizon. The IP model explicitly considers the age of blood inventory, uncertain demand, the demand for two types of patients and crossmatch-to-transfusion ratio. The second model formulates the different shortage and inventory distribution strategies of a blood center supplying blood products to multiple hospitals. The third model develops a vehicle routing problem for blood centers to minimize the daily distance travelled by bloodmobiles during the blood collection process. Optimal routing for each bloodmobiles is identified using CPLEX solver, branch \& bound and column generation algorithms and their solution times are compared.

This dissertation is a collection of previously-published manuscript and conference papers. In this dissertation, we will deal with a stochastic unit commitment problem with cooling systems for gas generators, a robust unit commitment problem with demand response and uncertain wind generation, and a power grid vulnerability analysis with transmission line switching. The latter two problems correspond to our theoretical contributions in two-stage robust optimization, i.e., how to efficiently solve a two-stage robust optimization, and how to deal with mixed-integer recourse in robust optimization. Due to copyright issue, this dissertation does not include any methodology papers written by the author during his PhD study. Readers are referred to the author's website for a complete list of publications.

Home healthcare has been a growing sector of the economy over the last three decades with roughly 23,000 companies now doing business in the U.S. producing over $56 billion in combined annual revenue. As a highly fragmented market, profitability of individual companies depends on effective management and efficient operations. This dissertation aims at reducing costs and improving productivity for home healthcare companies. The first part of the research involves the development of a new formulation for the therapist routing and scheduling problem as a mixed integer program. Given the time horizon, a set of therapists and a group of geographically dispersed patients, the objective of the model is to minimize the total cost of providing service by assigning patients to therapists while satisfying a host of constraints concerning time windows, labor regulations and contractual agreements. This problem is NP-hard and proved to be beyond the capability of commercial solvers like CPLEX. To obtain good solutions quickly, three approaches have been developed that include two heuristics and a decomposition algorithm. The first approach is a parallel GRASP that assigns patients to multiple routes in a series of rounds. During the first round, the procedure optimizes the patient distribution among the available therapists, thus trying to reach a local optimum with respect to the combined cost of the routes. Computational results show that the parallel GRASP can reduce costs by 14.54% on average for real datasets, and works efficiently on randomly generated datasets. The second approach is a sequential GRASP that constructs one route at a time. When building a route, the procedure tracks the amount of time used by the therapists each day, giving it tight control over the treatment time distribution within a route. Computational results show that the sequential GRASP provides a cost savings of 18.09% on average for the same real datasets, but gets much better solutions with significantly less CPU for the same randomly generated datasets. The third approach is a branch and price algorithm, which is designed to find exact optima within an acceptable amount of time. By decomposing the full problem by therapist, we obtain a series of constrained shortest path problems, which, by comparison are relatively easy to solve. Computational results show that, this approach is not efficient here because: 1) convergence of Dantzig-Wolfe decomposition is not fast enough; and 2) subproblem is strongly NP-hard and cannot be solved efficiently. The last part of this research studies a simpler case in which all patients have fixed appointment times. The model takes the form of a large-scale mixed-integer program, and has different computational complexity when different features are considered. With the piece-wise linear cost structure, the problem is strongly NP-hard and not solvable with CPLEX for instances of realistic size. Subsequently, a rolling horizon algorithm, two relaxed mixed-integer models and a branch-and-price algorithm were developed. Computational results show that, both the rolling horizon algorithm and two relaxed mixed-integer models can solve the problem efficiently; the branch-and-price algorithm, however, is not practical again because the convergence of Dantzig-Wolfe decomposition is slow even when stabilization techniques are applied. / text

Amusement parks are a huge business. Guest experiences determine the success or failure for an amusement park. This report suggests an approach to improve guest experience by managing guest flow. The guest happiness optimization problem is formulated into a visitor routing management model. The constraints for this model include attraction attributes and guest behavior. To build the attraction constraints, their information is first gathered from internet, field studies and surveys, and then input into simulation software. Constraints on guest behavior are set up with a literature study and a guest survey. A two phase heuristic is developed to solve this problem with constraints. Candidate routes are generated with a route construction algorithm in the first phase. Visitor distribution and selection on these candidate routes are determined in the second phase using a mixed integer programming solver. Visitor routes are then recommended to the park’s operator side, for them to distribute to guests visiting on their vacations. Data from Disney Epcot are collected and applied in the case study to implement the methodology in this report. Attraction operations capability is maintained at the current level with no additional cost for the project, while guest satisfaction is improved by ensuring the number and type of attractions they visit. In addition, average waiting time for visitors is reduced by at least 70% in the recommended operation strategy. / text

Στην παρούσα Διπλωματική Εργασία, παρουσιάζεται η πολύ γνωστή μέθοδος Simplex. Με τη βοήθεια της μεθόδου Simplex, μπορούμε να επιλύσουμε προβλήματα γραμμικού προγραμματισμού, ακέραιου γραμμικού προγραμματισμού καθώς και διάφορες παραλλαγές των παραπάνω. Ειδικότερα για τον ακέραιο γραμμικό προγραμματισμό, παρουσιάζονται κάποιες από τις πιο γνωστές μεθόδους αναζήτησης, οι οποίες ανήκουν στην οικογένεια μεθόδων “Branch And Bound”. Επίσης κάποιες τεχνικές αναζήτησης των βέλτιστων λύσεων στο δένδρο που δημιουργείται από τις προηγούμενες τεχνικές. Τα παραπάνω υλοποιήθηκαν σε ένα λογισμικό με γραφικό περιβάλλον (GUI), το οποίο είναι συμβατό με τις περισσότερες εκδόσεις του Λειτουργικού Συστήματος, Windows της Microsoft και χωρίς να χρειάζονται κάτι επιπλέον σε έναν Προσωπικό Υπολογιστή. / This thesis presents the well-known method Simplex. With method Simplex, we can solve problems of linear programming, integer linear programming and several variants of the above. Especially for the integer linear programming, presented some of the most known search methods, which belong to the family of methods "Branch And Bound". Also presented some search techniques for optimal solutions in the tree, generated by the same techniques. These were implemented in a software with graphical interface (GUI), which is compatible with most versions of the Microsoft Windows OS, with a simple installation.

This thesis documents the optimized design of a touch screen using infrared technology as a three dimensional problem. The framework is fundamentally built on laser diode technology and introduces mirrors for signal reflection. The rising popularity of touch screens are credited to the naturally intuitive control of display interfaces, extensive data presentation, and the improved manufacturing process of various touch screen implementations. Considering the demands on touch screen technology, the design for a large scaled touch panel is inevitable, and signal reduction techniques become a necessity to facilitate signal processing and accurate touch detection. The developed research model seeks to capture realistic touch screen design limitations to create a deploy-able configuration. The motivation of the problem stems from the significant reduction of representation achieved by combinatorial group theory. The research model is of difficulty NP-complete. Additional exclusive-or functions for uniqueness, strengthening model search space, symmetry eliminating constraints, and implementation constraints are incorporated for enhanced performance. The computational results and analysis of objectives, valuing the emphasis on diodes and layers are evaluated. The evaluation of trade-off between diodes and layers is also investigated.

The focus of this dissertation is solution strategies for stochastic mixed-integer programs with special structures. Motivation for the methods comes from the relatively sparse number of algorithms for solving stochastic mixed-integer programs. Two stage models with finite support are assumed throughout. The first contribution introduces the nodal decision framework under private information restrictions. Each node in the framework has control of an optimization model which may include stochastic parameters, and the nodes must coordinate toward a single objective in which a single optimal or close-to-optimal solution is desired. However, because of competitive issues, confidentiality requirements, incompatible database issues, or other complicating factors, no global view of the system is possible. An iterative methodology called the nodal decomposition-coordination algorithm (NDC) is formally developed in which each entity in the cooperation forms its own nodal deterministic or stochastic program. Lagrangian relaxation and subgradient optimization techniques are used to facilitate negotiation between the nodal decisions in the system without any one entity gaining access to the private information from other nodes. A computational study on NDC using supply chain inventory coordination problem instances demonstrates that the new methodology can obtain good solution values without violating private information restrictions. The results also show that the stochastic solutions outperform the corresponding expected value solutions. The next contribution presents a new algorithm called scenario Fenchel decomposition (SFD) for solving two-stage stochastic mixed 0-1 integer programs with special structure based on scenario decomposition of the problem and Fenchel cutting planes. The algorithm combines progressive hedging to restore nonanticipativity of the first-stage solution, and generates Fenchel cutting planes for the LP relaxations of the subproblems to recover integer solutions. A computational study SFD using instances with multiple knapsack constraint structure is given. Multiple knapsack constrained problems are chosen due to the advantages they provide when generating Fenchel cutting planes. The computational results are promising, and show that SFD is able to find optimal solutions for some problem instances in a short amount of time, and that overall, SFD outperforms the brute force method of solving the DEP.