Algorithmic Framework for Improving Heuristics in Stochastic, Stage-Wise Optimization Problems Jaein Choi 172 Pages Directed by Dr. Jay H. Lee and Dr. Matthew J. Realff The goal of this thesis is the development of a computationally tractable solution method for stochastic, stage-wise optimization problems. In order to achieve the goal, we have developed a novel algorithmic framework based on Dynamic Programming (DP) for improving heuristics. The propose method represents a systematic way to take a family of solutions and patch them together as an improved solution. However, patching is accomplished in state space, rather than in solution space. Since the proposed approach utilizes simulation with heuristics to circumvent the curse of dimensionality of the DP, it is named as Dynamic Programming in Heuristically Restricted State Space. The proposed algorithmic framework is applied to stochastic Resource Constrained Project Scheduling problems, a real-world optimization problem with a high dimensional state space and significant uncertainty equivalent to billions of scenarios. The real-time decision making policy obtained by the proposed approach outperforms the best heuristic applied in simulation stage to form the policy. The proposed approach is extended with the idea of Q-Learning technique, which enables us to build empirical state transition rules through simulation, for stochastic optimization problems with complicated state transition rules. Furthermore, the proposed framework is applied to a stochastic supply chain management problem, which has high dimensional action space as well as high dimensional state space, with a novel concept of implicit sub-action space that efficiently restricts action space for each state in the restricted state space. The resulting real-time policy responds to the time varying demand for products by stitching together decisions made by the heuristics and improves overall performance of the supply chain. The proposed approach can be applied to any problem formulated as a stochastic DP, provided that there are reasonable heuristics available for simulation.

To date, closed form optimal solutions for stocking levels in arborescent multiechelon inventory systems have not been obtained. These problems exhibit the joint difficulties of requiring an allocation policy as well as a stocking policy, and the multidimensional nature of their state space makes dynamic programming formulations impractical. In this dissertation, we introduce procedures that approximate multiechelon networks with sets of single installation problems. We first use this technique to solve for base-stock levels in a distribution network with asymmetric retailers. Second, we use this technique to analyze delayed differentiation production processes and provide guidance as to when the strategy is most warranted. Third, we modify the technique to account for inventory that exhibits perishability and solve for stocking policies for distribution systems when the inventory has a fixed shelf life.

Objectives. In this thesis I have, together with game developer and publisher Paradox Interactive, designed and implemented a level editor tool for use in their game Magicka 2. With this tool users can create, edit and share custom Challenge levels in the game. I have also done a more in-depth scientific study of usability in such level editor tools, especially pertaining to the disparity between various controller input schemes and platforms. Methods. I have performed a literary study of articles and books relevant to the field of game design, user interface design, general usability, controller input schemes and any other topic I found relevant. I have paired this with a study of similar level editor tools and their user interfaces and features in other console and PC games. This knowledge, together with feedback from both expert and non-expert testing, has then been analyzed and used to design and implement both the user interface and the features of the level editor. Results. Results of the literary study, level editor tool study and testing are presented together with their impact on the design of the user interface and all implemented features. The results of each iteration of the Challenge Creator are presented as well. Lastly, all results are analyzed and a set of design heuristics for creating a similar level editor tool is presented. Conclusions. I conclude that creating a platform independent level editor tool with high usability is very much possible, but that designing such a tool becomes far more difficult with each new platform and controller input scheme supported. I also conclude that additional features and further increase in tool complexity loses significant impact if the core user interface is lacking in usability. I also conclude that more time and testing will be needed to further empirically validate the design heuristics. Lastly, I conclude that additional iterations will be required upon the Challenge Creator to improve its usability in light of already known and established design flaws.

We consider a problem of placing route-based filters in a communication network to limit the number of forged address attacks to a prescribed level. Nodes in the network communicate by exchanging packets along arcs, and the originating node embeds the origin and destination addresses within each packet that it sends. In the absence of a validation mechanism, one node can send packets to another node using a forged origin address to launch an attack against that node. Route-based filters can be established at various nodes on the communication network to protect against these attacks. A route-based filter examines each packet arriving at a node, and determines whether or not the origin address could be legitimate, based on the arc on which the packet arrives, the routing information, and possibly the destination. The problem we consider seeks to find a minimum cardinality subset of nodes to filter so that the prescribed level of security is achieved.The primary contributions of this dissertation are as follows. We formulate and discuss the modeling of this filter placement problem as a mixed-integer program. We then show the sensitivity of the optimal number of deployed filters as the required level of security changes, and demonstrate that current vertex cover-based heuristics are ineffective for problems with relaxed security levels. We identify a set of special network topologies on which the filter placement problem is solvable in polynomial time, focusing our attention on the development of a dynamic programming algorithm for solving this problem on tree networks. These results can then in turn be used to derive valid inequalities for an integer programming model of the filter placement problem. Finally, we present heuristic algorithms based on the insights gained from our overall study for solving the problem, and evaluate their performance against the optimal solution provided by our integer programming model.

In their book, Gigerenzer and Selten (2001) described human being as an organism that adaptively reacts to its environment by selecting ecologically rational heuristics that are contingent on task demands; that is, adaptivity assumption. Empirical evidence of the adaptivity assumption is, however, mixed. In this paper, I review prior experiments related to testing the adaptivity assumption and criticize some of the past findings. From this criticism, the research questions are formed. The research objective of this paper is to test whether or not people choose their decision strategy as a reaction to environmental conditions. In this dissertation, the use of the take-the-best (TTB) heuristic is investigated for different treatments, which are information structure, information cost, and social rationality. Participants go through 180 trials of a pair comparison task. Using the proportion of TTB trials as a dependent variable, three hypotheses regarding the effects of three treatments are tested. The results of the experiments indicate that only the social rationality is a significant factor in promoting the TTB heuristic. Besides the test of the hypothesis, an exploratory analysis of participants’ data is presented.

Pateikti dažniausiai naudojami algoritmai bei pasiūlyti 6 jų pagerinimai. Pasiūlytos euristikos: dviejų stulpelių euristika(2C), vieno stulpelio euristika(1C), rūšiavimas pagal aukštį(SH), rūšiavimas pagal plotį(SW), rūšiavimas pagal plotą(SS) ir rūšiavimas pagal stačiakampių kvadrantingumą(SSN). Eksperimentui buvo pasirinkti septynių skirtingų klasių Hopper and Turton testiniai duomenys (2002). Eksperimento rezultatai įvertinti F-testu, chi-kvadrato testu bei pjaustymo efektyvumu. / During the period of implementation we implemented a number of level heuristics from the literature and proposed possible improvements to some of these algorithms. 6 algorithms were compared in terms of their solution qualities and their ability to obtain the smallest strip height. The results of the analyses of variance indicate that statistically, there is difference between the mean strip heights obtained by the algorithms at a 5% level of significance. The algorithms were also compared in terms of how close the strip heights obtained were to the optimal solution.

Passive optical networks (PONs) are point-to-multipoint networks where a single Central Office (CO) is connected to a number of downstream Optical Network Units (ONUs) via a single optical fiber by splitting the optical signal with passive splitters. Due to technology advances and increasing bandwidth requirements, these networks have moved to last mile deployment, also known as fiber-to-the-home (FTTH). The planning of these PONs are traditionally done by hand, but automated methods can be used to decrease deployment costs and planning time. Even though a number of methods have been proposed to address this problem through the solving of integer linear programming (ILP) models, they suffer from limited availability, inaccuracies and limited scalability due to the problem complexity. This dissertation focusses on improving the accuracy of these models as well as improving scalability to a point where large-scale problems can be solved feasibly. To address this, a basic model is implemented to capture the network structure and verified accordingly. Results show this model can be solved quickly, but has large discrepancies with real-world plans. Refinements in the form of fiber duct sharing, network constraints, multiple splitter types and economies of scale among others are then incorporated into a refined model and solved. Analysis of the experimental results indicates improved accuracy and lower deployment costs, at the expense of increasing computation effort considerably. Heuristic techniques are then examined to improve computational performance, including an elementary heuristic (ELEM), the Branch Contracting Algorithm (BCA) and problem decomposition. It is demonstrated that through the use of k-means clustering, the refined model can be solved in a fraction of the time while keeping deployment costs comparably low. / Thesis (MIng (Computer and Electronic Engineering))--North-West University, Potchefstroom Campus, 2013

Passive optical networks (PONs) are point-to-multipoint networks where a single Central Office (CO) is connected to a number of downstream Optical Network Units (ONUs) via a single optical fiber by splitting the optical signal with passive splitters. Due to technology advances and increasing bandwidth requirements, these networks have moved to last mile deployment, also known as fiber-to-the-home (FTTH). The planning of these PONs are traditionally done by hand, but automated methods can be used to decrease deployment costs and planning time. Even though a number of methods have been proposed to address this problem through the solving of integer linear programming (ILP) models, they suffer from limited availability, inaccuracies and limited scalability due to the problem complexity. This dissertation focusses on improving the accuracy of these models as well as improving scalability to a point where large-scale problems can be solved feasibly. To address this, a basic model is implemented to capture the network structure and verified accordingly. Results show this model can be solved quickly, but has large discrepancies with real-world plans. Refinements in the form of fiber duct sharing, network constraints, multiple splitter types and economies of scale among others are then incorporated into a refined model and solved. Analysis of the experimental results indicates improved accuracy and lower deployment costs, at the expense of increasing computation effort considerably. Heuristic techniques are then examined to improve computational performance, including an elementary heuristic (ELEM), the Branch Contracting Algorithm (BCA) and problem decomposition. It is demonstrated that through the use of k-means clustering, the refined model can be solved in a fraction of the time while keeping deployment costs comparably low. / Thesis (MIng (Computer and Electronic Engineering))--North-West University, Potchefstroom Campus, 2013

In this study, the two-dimensional cutting stock problem (2DCSP) is considered. This is a problem that occurs in the cutting of a number of smaller rectangular pieces or items from a set of large stock rectangles. It is assumed that the set of large objects is sufficient to accommodate all the small items. A heuristic procedure is developed to solve the two-dimensional single stock-size cutting stock problem (2DSSSCSP). This is the special case where the large rectangles are all of the same size. The major objective is to minimize waste and the number of stock sheets utilized. The heuristic procedures developed to solve the 2DSSSCSP are based on the generation of cutting pattern. The Wang algorithm and a specific commercial software package are made use of to generate these patterns. The commercial software was chosen from a set of commercial software packages available in the market. A combinatoric process is applied to generate sets of cutting patterns using the Wang algorithm and the commercial software. The generated cutting patterns are used to formulate an integer linear programming model which is solved using an optimization solver. Empirical experimentation is carried out to test the heuristic procedures using data obtained from both small and real world application problem instances. The results obtained shows that the heuristic procedures developed produce good quality results for both small and real life problem instances. It is quite clear that the heuristic procedure developed to solve the 2DSSSCSP produces cutting patterns which are acceptable in terms of waste generated and may offer useful alternatives to approaches currently available. Broadly stated, this study involves investigating available software (commercial) in order to assess, formulate and investigate methods to attempt to benchmark software systems and algorithms and to employ ways to enhance solutions obtained by using these software systems. / Thesis (M.Sc. (Computer Science))--North-West University, Potchefstroom Campus, 2011.

Individuals utilize heuristics in order to simplify problems, which may lead to biases in decision-making. The research question of this study is: “How does the affect heuristic impact the investment process of private equity decision-makers reviewing proposals?” Through an exploratory multi-case analysis, insight is provided into complex private equity decisions by studying biases in the investment process. This is a study of private equity groups’ (PEG) decision-making process when they consider businesses for investment. Qualitative data was generated from semi-structured interviews with twenty private equity decision-makers. The deliberative heuristics applied in the teaser review are learned from process experience and guide the deliberation on whether to proceed. Simplifying heuristics are applied in the more informal review process. Organizational learning was exhibited as the PEGs have modified their investment structures based on previous experiences. The study indicates that experience and learning lead to the construction of an affect heuristic that subsequently impacts investments. It also confirms the need for strategic decision-makers to recognize their own biases and adjust their processes accordingly. A significant practical implication of this study is the insight provided into the views of the PEG decision-makers as they anticipate the need to supplement the management team is helpful to business owners and their advisors. The study highlights the opportunities for biases in PEG decision-making processes. Accessing decision-makers at larger PEGs and approaching more middle market firms would broaden the results.