Applications of accuracy certificates for problems with convex structure   This dissertation addresses the efficient generation and potential applications of accuracy certificates in the framework of “black-box-represented” convex optimization problems - convex problems where the objective and the constraints are represented by  “black boxes” which, given on input a value x of the argument, somehow (perhaps in a fashion unknown to the user) provide on output the values and the derivatives of the objective and the constraints at x. The main body of the dissertation can be split into three parts.  In the first part, we provide our background --- state of the art of the theory of accuracy certificates for black-box-represented convex optimization. In the second part, we extend the toolbox of black-box-oriented convex optimization algorithms with accuracy certificates by equipping with these certificates a state-of-the-art algorithm for large-scale nonsmooth black-box-represented problems with convex structure, specifically, the Non-Euclidean Restricted Memory Level (NERML) method. In the third part, we present several novel academic applications of accuracy certificates. The dissertation is organized as follows: In Chapter 1, we motivate our research goals and present a detailed summary of our results. In Chapter 2, we outline the relevant background, specifically, describe four generic black-box-represented generic problems with convex structure (Convex Minimization, Convex-Concave Saddle Point, Convex Nash Equilibrium, and Variational Inequality with Monotone Operator), and outline the existing theory of accuracy certificates for these problems. In Chapter 3, we develop techniques for equipping with on-line accuracy certificates the state-of-the-art NERML algorithm for large-scale nonsmooth problems with convex structure, both in the cases when the domain of the problem is a simple solid and in the case when the domain is given by Separation oracle. In Chapter 4, we develop  several novel academic applications of accuracy certificates, primarily to (a) efficient certifying emptiness of the intersection of finitely many solids given by Separation oracles, and (b) building efficient algorithms for convex minimization over solids given by Linear Optimization oracles (both precise and approximate). In Chapter 5, we apply accuracy certificates to efficient decomposition of “well structured” convex-concave saddle point problems, with applications to computationally attractive decomposition of a large-scale LP program with the constraint matrix which becomes block-diagonal after eliminating a relatively small number of possibly dense columns (corresponding to “linking variables”) and possibly dense rows (corresponding to “linking constraints”).

<p>This thesis consists of an introduction and sevenindependent, but closely related, papers which all deal withproblems in structural optimization. In particular, we considermodels and methods for global optimization of problems intopology design of discrete and continuum structures.</p><p>In the first four papers of the thesis the nonconvex problemof minimizing the weight of a truss structure subject to stressconstraints is considered. First itis shown that a certainsubclass of these problems can equivalently be cast as linearprograms and thus efficiently solved to global optimality.Thereafter, the behavior of a certain well-known perturbationtechnique is studied. It is concluded that, in practice, thistechnique can not guarantee that a global minimizer is found.Finally, a convergent continuous branch-and-bound method forglobal optimization of minimum weight problems with stress,displacement, and local buckling constraints is developed.Using this method, several problems taken from the literatureare solved with a proof of global optimality for the firsttime.</p><p>The last three papers of the thesis deal with topologyoptimization of discretized continuum structures. Theseproblems are usually modeled as mixed or pure nonlinear 0-1programs. First, the behavior of certain often usedpenalization methods for minimum compliance problems isstudied. It is concluded that these methods may fail to producea zero-one solution to the considered problem. To remedy this,a material interpolation scheme based on a rational functionsuch that compli- ance becomes a concave function is proposed.Finally, it is shown that a broad range of nonlinear 0-1topology optimization problems, including stress- anddisplacement-constrained minimum weight problems, canequivalently be modeled as linear mixed 0-1 programs. Thisresult implies that any of the standard methods available forgeneral linear integer programming can now be used on topologyoptimization problems.</p><p><b>Keywords:</b>topology optimization, global optimization,stress constraints, linear programming, mixed integerprogramming, branch-and-bound.</p>

This work integrates perennial feedstock yield modeling using climate model data from current and future climate scenarios, land use datasets, transportation network data sets, Geographic Information Systems (GIS) tools, and Mixed integer linear programming (MILP) optimization models to examine biorefinery network designs in the southeastern United States from an overall systems perspective. Both deterministic and stochastic cases are modeled. Findings indicate that the high transportation costs incurred by biorefinery networks resulting from the need to transport harvested biomass from harvest location to processing facilities can be mitigated by performing initial processing steps in small scale mobile units at the cost of increased unit production costs associated with operating at smaller scales. Indeed, it can be financially advantageous to move the processing units instead of the harvested biomass, particularly when considering a 10-year planning period (typical switchgrass stand life). In this case, the mobile processing supply chain configuration provides added flexibility to respond to year-to-year variation in the geographic distribution of switchgrass yields. In order to capture the effects of variation in switchgrass yields and incorporate it in optimization models, yield modeling was conducted for both current and future climate scenarios. (In general profits are lower in future climate scenarios). Thus, both the effects of annual variation in weather patterns and varying climate scenarios on optimization model decisions can be observed.

According to the Institute of Medicine (IOM), the U.S. health care delivery system does not provide consistent, high-quality medical care to all people all the time. As a significant component of the health care delivery system, the state of Graduate Medical Education in the United States has prompted much analysis in recent years due to the general view that desired and actual outcomes are increasingly at variance with each other. One area of focus has been the implications of change for provider credentialing and funding of graduate medical education. With this research we test the hypothesis that residents perform valuable work in the teaching hospitals where they undergo training, to inform the issue regarding provider credentialing for residents. We developed a framework to compare second-year residents (PGY2), physician assistants with one year of experience, and nurse practitioners with one year of experience to measurably address the interchangeability of providers. Data was collected by obtaining expert opinions on the proficiency of the three provider options (resident, physician assistant, nurse practitioner) in performing a set of tasks/procedures by surveying the program directors of Internal Medicine residency programs in the United States. The other residency programs at the University of South Floridas College of Medicine were also surveyed to obtain measurable performance on the service providers.Statistical tools were used to analyze the survey responses, aggregate patient data and salary data for each provider. The data analysis and summary indicated that residents displayed higher levels of proficiency than physician assistants and nurse practitioners for the tasks investigated.

The average cost of operating a queueing network depends on several factors such as the complexity of the network and the service policy used. Approximate linear programming (ALP) is a method that can be used to compute an accurate lower bound on the optimal average cost as well as generate policies to be used in operating the network. These average cost solutions and policies are dependent on the type of basis function used in the ALP. In this paper, the ALP average cost solutions and policies are analyzed for twelve networks with four different types of basis functions (quadratic, linear, pure exponential, and mixed exponential). An approximate bound on the optimality gap between the ALP average cost solution and the optimal average cost solution is computed for each system, and the size of this bound is determined relative to the ALP average cost solution. Using the same set of networks, the performance of ALP generated policies are compared to the performance of the heuristic policies first-buffer-first-served (FBFS), last-buffer-first-served (LBFS), highest-queue-first-served (HQFS), and random-queue-first-served (RQFS). In general, ALP generated average cost solutions are considerably smaller than the simulated average cost under the corresponding policy, and therefore the approximate bounds on the optimality gaps are quite large. This bound increases with the complexity of the queueing network. Some ALP generated policies are not stabilizing policies for their corresponding networks, especially those produced using pure exponential and mixed exponential basis functions. For almost all systems, at least one of the heuristic policies results in mean average cost less than or nearly equal to the smallest mean average cost of all ALP generated policies in simulation runs. This means that generally there exists a heuristic policy which can perform as well as or better than any ALP generated policy. In conclusion, a useful bound on the optimality gap between the ALP average cost solution and the optimal average cost solution cannot be computed with this method. Further, heuristic policies, which are more computationally tractable than ALP generated policies, can generally match or exceed the performance of ALP generated policies, and thus computing such policies is often unnecessary for realizing cost benefits in queueing networks. / text

- / -

The two-dimension packing problem is concerned with the arrangement of items without overlaps inside a container. In particular we have considered the case when the items are circular objects, some of the general examples that can be found in the industry are related with packing, storing and transportation of circular objects. Although there are several approaches we want to investigate the use of formulation space search. Formulation space search is a fairly recent method that provides an easy way to escape from local optima for non-linear problems allowing to achieve better results. Despite the fact that it has been implemented to solve the packing problem with identical circles, we present an improved implementation of the formulation space search that gives better results for the case of identical and non-identical circles, also considering that they are packed inside different shaped containers, for which we provide the needed modifications for an appropriate implementation. The containers considered are: the unit circle, the unit square, two rectangles with different dimension (length 5, width 1 and length 10 width 1), a right-isosceles triangle, a semicircle and a right-circular quadrant. Results from the tests conducted shown several improvements over the best previously known for the case of identical circles inside three different containers: a right-isosceles triangle, a semicircle and a circular quadrant. In order to extend the scope of the formulation space search approach we used it to solve mixed-integer non-linear problems, in particular those with zero-one variables. Our findings suggest that our implementation provides a competitive way to solve these kind of problems.

Πολλά είναι τα προβλήματα που καλούμαστε να αντιμετωπίσουμε στην καθημερινότητά μας, και που χρίζουν την ανάγκη προσδιορισμού αυτών, μέσω του Γραμμικού Στοχαστικού Προγραμματισμού. Βασικό εργαλείο των προβλημάτων του Γραμμικού Στοχαστικού Προγραμματισμού που χρησιμοποιείται για την υπολογιστική τους επίλυση είναι οι μέθοδοι του Γραμμικού και του Μη Γραμμικού Προγραμματισμού. Στο 1ο κεφάλαιο της παρούσας Διπλωματικής Εργασίας, υπενθυμίζονται οι βασικές ιδιότητες και μέθοδοι επίλυσης των Γραμμικών και Μη Γραμμικών προβλημάτων, όπως αυτές χρησιμοποιούνται από τον Στοχαστικό Προγραμματισμό. Στο 2ο κεφάλαιο, παρουσιάζεται μια σειρά από Γραμμικά μοντέλα Στοχαστικού Γραμμικού Προγραμματισμού ενός σταδίου συζητώντας τις θεωρητικές τους ιδιότητες, σχετικές με την υπολογιστική τους δυνατότητα, μία από τις οποίες αποτελεί η κυρτότητά τους. Στο 3ο, και τελευταίο κεφάλαιο, ακολουθείται μια αντίστοιχη παρουσίαση των Γραμμικών Στοχαστικών μοντέλων πολλαπλών σταδίων, τονίζοντας τις ιδιότητες αυτές που επιτρέπουν την κατασκευή προσεγγιστικών μεθόδων επίλυσης. / There are various special problem formulations to be dealt with in our daily life, and our conclusion is that a basic toolkit of Linear and Nonlinear Programming methods cannot be waived if we want to deal with the computational solution of Stochastic Linear Programming problems. In chapter 1, basic properties of Linear Problems and Non Linear Problems, as well as their solution methods, are reminded, as they are used in the Stochastic Linear Programming. In chapter 2, various Single-stage Stochastic Linear Programming (SLP) models are presented and their theoretical properties are discussed, which are relevant for their computational tractability, as convexity statements. Conclusions are presented in chapter 3, followed by an analogous discussion of Multi-stage SLP models, focussed, among others, on properties allowing for the construction of particular approximation methods for computing solutions.

In the rapidly changing world of today, people have to make decisions under some degree of uncertainty. At the same time, the development of computing technologies enables people to take uncertain factors into considerations while making their decisions.Stochastic programming techniques have been widely applied in finance engineering, supply chain management, logistics, transportation, etc. Such applications often involve a large, possibly infinite, set of scenarios. Hence the resulting programstend to be large in scale.The need to solve large scale programs calls for a combination of mathematical programming techniques and sample-based approximation. When using sample-based approximations, it is important to determine the extent to which the resulting solutions are dependent on thespecific sample used. This dissertation research focuses on computational evaluation of the solutions from sample-based two-stage/multistage stochastic linear programming algorithms, with a focus on the effectiveness of optimality tests and the quality ofa proposed solution.In the first part of this dissertation, two alternative approaches of optimality tests of sample-based solutions, adaptive and non-adaptive sampling methods, are examined and computationally compared. The results of the computational experiment are in favor of the adaptive methods. In the second part of this dissertation, statistically motivated bound-based solution validation techniques in multistage linear stochastic programs are studied both theoretically and computationally. Different approaches of representations of the nonanticipativity constraints are studied. Bounds are established through manipulations of the nonanticipativity constraints.

Stable matchings were introduced in 1962 by David Gale and Lloyd Shapley to study the college admissions problem. The seminal work of Gale and Shapley has motivated hundreds of research papers and found applications in many areas of mathematics, computer science, economics, and even medicine. This thesis studies stable matchings in graphs and hypergraphs. We begin by introducing the work of Gale and Shapley. Their main contribution was the proof that every bipartite graph has a stable matching. Our discussion revolves around the Gale-Shapley algorithm and highlights some of the interesting properties of stable matchings in bipartite graphs. We then progress to non-bipartite graphs. Contrary to bipartite graphs, we may not be able to find a stable matching in a non-bipartite graph. Some of the work of Irving will be surveyed, including his extension of the Gale-Shapley algorithm. Irving's algorithm shows that many of the properties of bipartite stable matchings remain when the general case is examined. In 1991, Tan showed how to extend the fundamental theorem of Gale and Shapley to non-bipartite graphs. He proved that every graph contains a set of edges that is very similar to a stable matching. In the process, he found a characterization of graphs with stable matchings based on a modification of Irving's algorithm. Aharoni and Fleiner gave a non-constructive proof of Tan's Theorem in 2003. Their proof relies on a powerful topological result, due to Scarf in 1965. In fact, their result extends beyond graphs and shows that every hypergraph has a fractional stable matching. We show how their work provides new and simpler proofs to several of Tan's results. We then consider fractional stable matchings from a linear programming perspective. Vande Vate obtained the first formulation for complete bipartite graphs in 1989. Further, he showed that the extreme points of the solution set exactly correspond to stable matchings. Roth, Rothblum, and Vande Vate extended Vande Vate's work to arbitrary bipartite graphs. Abeledo and Rothblum further noticed that this new formulation can model fractional stable matchings in non-bipartite graphs in 1994. Remarkably, these formulations yield analogous results to those obtained from Gale-Shapley's and Irving's algorithms. Without the presence of an algorithm, the properties are obtained through clever applications of duality and complementary slackness. We will also discuss stable matchings in hypergraphs. However, the desirable properties that are present in graphs no longer hold. To rectify this problem, we introduce a new ``majority" stable matchings for 3-uniform hypergraphs and show that, under this stronger definition, many properties extend beyond graphs. Once again, the linear programming tools of duality and complementary slackness are invaluable to our analysis. We will conclude with a discussion of two open problems relating to stable matchings in 3-uniform hypergraphs.