Thesis (M.S. in Systems Engineering Management)--Naval Postgraduate School, Sept. 2004. / Thesis Advisor(s): Robert F. Dell. Includes bibliographical references (p. 33-34). Also available online.

Thesis (M. S.)--Industrial and Systems Engineering, Georgia Institute of Technology, 2009. / Committee Co-Chair: George L. Nemhauser; Committee Co-Chair: Shabbir Ahmed; Committee Member: Martin W. P. Savelsbergh; Committee Member: R. Gary Parker; Committee Member: Zonghao Gu.

- / -

No description available.

No description available.

Single-row mixed-integer programming (MIP) problems have been studied thoroughly under many different perspectives over the years. While not many practical applications can be modeled as a single-row MIP, their importance lies in the fact that they are simple, natural and very useful relaxations of generic MIPs. This thesis will focus on such MIPs and present theoretical and computational advances in their study. Chapter 1 presents an introduction to single-row MIPs, a historical overview of results and a motivation of why we will be studying them. It will also contain a brief review of the topics studied in this thesis as well as our contribution to them. In Chapter 2, we introduce a generalization of a very important structured single-row MIP: Gomory's master cyclic group polyhedron (MCGP). We will show a structural result for the generalization, characterizing all facet-defining inequalities for it. This structural result allows us to develop relationships with MCGP, extend it to the mixed-integer case and show how it can be used to generate new valid inequalities for MIPs. Chapter 3 presents research on an algorithmic view on how to maximally lift continuous and integer variables. Connections to tilting and fractional programming will also be presented. Even though lifting is not particular to single-row MIPs, we envision that the general use of the techniques presented should be on easily solvable MIP relaxations such as single-row MIPs. In fact, Chapter 4 uses the lifting algorithm presented. Chapter 4 presents an extension to the work of Goycoolea (2006) which attempts to evaluate the effectiveness of Mixed Integer Rounding (MIR) and Gomory mixed-integer (GMI) inequalities. By extending his work, natural benchmarks arise, against which any class of cuts derived from single-row MIPs can be compared. Finally, Chapter 5 is dedicated to dealing with an important computational problem when developing any computer code for solving MIPs, namely the problem of numerical accuracy. This problem arises due to the intrinsic arithmetic errors in computer floating-point arithmetic. We propose a simple approach to deal with this issue in the context of generating MIR/GMI inequalities.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Baseball is an incredibly complex game where the managers of the baseball teams have numerous decisions to make. The managers are in control of the offense and defense of a team. Some managers have ruined their teams’ chances of a victory by removing their star pitcher too soon in a game or leaving them in too long; managers also choose to pinch hit for batters or pinch run for base runners in order to set up a “favorable match-up” such as a left handed pitcher versus a right handed batter. This research’s goal is to aid managers by providing an optimal positioning of defensive players on the field for a particular batter. In baseball, every ball that is hit onto the field of play can be an out if the fielders are positioned correctly. By positioning the fielders in an optimal manner a team will directly reduce the number of runs that it gives up, which increases the chances of a win. This research describes an integer program that can determine the optimal location of defensive players. This integer program is based off of a random set of hits that the player has produced in the past. The integer program attempts to minimize the expected costs associated with each hit where the cost is defined by a penalty (single, double or triple) or benefit (out) of the person’s hit. By solving this integer program in Opl Studio 4.2, a commercial integer programming software, an optimal defensive positioning is derived for use against this batter. To test this defense against other standard defenses that teams in the MLB currently use, a simulation was created. This simulation uses Derek Jeter’s actual statistics; including his 2009 regular season hit chart. The simulation selects a hit at random according to his hit chart and determines the outcome of the hit (single, double, out, double play, etc.). Once this simulation is complete a printout shows the batter’s statistics; including his average and slugging percentage. VI By comparing the optimized defensive alignment with some commonly used major league alignments, it can be shown that this optimal alignment would decrease Jeter’s average by nearly 13% and decrease his slugging by 35%. It is my opinion that managers should use this tool to help them win more games. These defenses can be seamlessly implemented by any coach or team.

No description available.

We generalise the study of cyclotomic matrices - those with all eigenvalues in the interval [-2; 2] - from symmetric rational integer matrices to Hermitian matrices with entries from rings of integers of imaginary quadratic fields. As in the rational integer case, a corresponding graph-like structure is defined. We introduce the notion of `4-cyclotomic' matrices and graphs, prove that they are necessarily maximal cyclotomic, and classify all such objects up to equivalence. Six rings OQ( p d) for d = -1;-2;-3;-7;-11;-15 give rise to examples not found in the rational-integer case; in four (d = -1;-2;-3;-7) we recover infinite families as well as sporadic cases. For d = -15;-11;-7;-2, we demonstrate that a maximal cyclotomic graph is necessarily 4- cyclotomic and thus the presented classification determines all cyclotomic matrices/graphs for those fields. For the same values of d we then identify the minimal noncyclotomic graphs and determine their Mahler measures; no such graph has Mahler measure less than 1.35 unless it admits a rational-integer representative.

Approved for public release; distribution is unlimited / This thesis explores Benders decomposition for solving interdiction problems on electric power grids, with applications to analyzing the vulnerability of such grids to terrorist attacks. We refine and extend some existing optimization models and algorithms and demonstrate the value of our techniques using standard reliability test networks from IEEE. Our implementation of Benders decomposition optimally solves any problem instance, in theory. However, run times increase as Benders' cuts are added to the master problem, and this has prompted additional research to increase the decomposition's efficiency. We demonstrate empirical speed ups by dropping slack cuts, solving a relaxed master problem in some iterations, and using integer but not necessarily optimal master-problem solutions. These mixed strategies drastically reduce computation times. For example, in one test case, we reduce the optimality gap, and the time that it takes to achieve this gap, from 16% in 75 hours to 5% in 16 minutes. / FUNDED BY: 2002-GT-R-057 / Lieutenant Commander, United States Navy