- / -

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.

Observers are used in the monitoring and control of dynamical systems to deduce the values of unmeasured states. Designing an observer requires having an accurate model of the plant — if the model parameters are characterized imprecisely, the observer may not provide reliable estimates. An interval observer, which comprises an upper and lower observer, bounds the plant's states from above and below, given the range of values of the imprecisely characterized parameters, i.e., it defines an interval in which the plant's states must lie at any given instant. We propose a linear programming-based method of interval observer design for two cases: 1) only the initial conditions of the plant are uncertain; 2) the dynamical parameters are also uncertain. In the former, we optimize the transient performance of the interval observers, in the sense that the volume enclosed by the interval is minimized. In the latter, we optimize the steady state performance of the interval observers, in the sense that the norm of the width of the interval is minimized at steady state. Interval observers are typically designed to characterize the widest interval that bounds the states. This thesis proposes an interval observer design method that utilizes additional, but still-incomplete information, that enables the designer to identify tighter bounds on the uncertain parameters under certain operating conditions. The number of bounds that can be refined defines a class of systems. The definition of this class is independent of the specific parameters whose bounds are refined. Applying robust optimization techniques, under a cardinality constrained model of uncertainty, we design a single observer for an entire class of systems. These observers guarantee a minimum level of performance with respect to the aforementioned metrics, as we optimize the worst-case performance over a given class of systems. The robust formulation allows the designer to tune the level of uncertainty in the model. If many of the uncertain parameter bounds can be refined, the nominal performance of the observer can be improved, however, if few or none of the parameter bounds can be refined, the nominal performance of the observer can be designed to be more conservative.

Knapsack problem has been widely studied in computer science for years. There exist several variants of the problem, with zero-one maximum knapsack in one dimension being the simplest one. In this thesis we study several existing approximation algorithms for the minimization version of the problem and propose a scaling based fully polynomial time approximation scheme for the minimum knapsack problem. We compare the performance of this algorithm with existing algorithms. Our experiments show that, the proposed algorithm runs fast and has a good performance ratio in practice. We also conduct extensive experiments on the data provided by Canadian Pacific Logistics Solutions during the MITACS internship program. We propose a scaling based e-approximation scheme for the multidimensional (d-dimensional) minimum knapsack problem and compare its performance with a generalization of a greedy algorithm for minimum knapsack in d dimensions. Our experiments show that the e- approximation scheme exhibits good performance ratio in practice. / x, 85 leaves ; 29 cm

No description available.

Membrane technology can help alleviate problems of matching supply and demand associated with upgrading on a small-scale level through its flexibility in operation. This paper provides a techno-economic assessment of the use of membrane technology via a quantitative and partial qualitative analysis at farm-based level. The purpose of the analysis is to investigate how the economic and environmental utility of the membranes can be maximised, along with outlining the possible reasons to its lack of diffusion. It combines an applied system research method by way of linear programming with interviews and the use of the innovation-decision process theory. A framework was set out to deliver hard and soft data that could also provide contextual in-depth analysis and discussion. It was found that membranes could provide good compatibility with farm based upgrading systems with desirable outcomes for both an economic and environmental viewpoint. More specifically, upgrading to 80 percent (which is below natural gas standards of 96 percent), was found to be more favourable than to upgrade to 96 percent. However, in addition to much further research and deliberation needed before 80 percent biogas can be used commercially in tractors, the study also outlined priority that needs to be given to the local market demand as well as for the need to introduce closer, more personal engagement with the farmers and make trialing and observing membrane technology better facilitated and funded so as to increase its adoption.

Good quality management decisions often rely on the evaluation and interpretation of data. One of the most popular ways to investigate possible relationships in a given data set is to follow a process of fitting models to the data. Regression models are often employed to assist with decision making. In addition to decision making, regression models can also be used for the optimization and prediction of data. The success of a regression model, however, relies heavily on assumptions made by the model builder. In addition, the model may also be influenced by the presence of outliers; a more robust model, which is not as easily affected by outliers, is necessary in making more accurate interpretations about the data. In this research study robust techniques for regression models with minimal assumptions are explored. Mathematical programming techniques such as linear programming, mixed integer linear programming, and piecewise linear regression are used to formulate a nonlinear regression model. Outlier detection and smoothing techniques are included to address the robustness of the model and to improve predictive accuracy. The performance of the model is tested by applying it to a variety of data sets and comparing the results to those of other models. The results of the empirical experiments are also presented in this study. / Thesis (M.Sc. (Computer Science))--North-West University, Potchefstroom Campus, 2011.