Well-publicized lost opportunities for U.S. and coalition air forces to strike enemy leadership targets in Afghanistan and Iraq demonstrate the importance of Time Sensitive Targeting. How do we "pair" the weapon and weapons delivery platform with their target? The available platforms (aircraft, manned or unmanned) may be on the ground in an alert status, loitering airborne, or on their way to attack other targets. The problem is compounded by the facts that we actually wish to (a) create multiple strike packages simultaneously, (b) recompose existing strike packages that are disrupted by the new plans, (c) minimize such disruptions, (d) satisfy minimum kill probabilities, and (e) avoid the attrition of tasked assets. This thesis develops an automated, optimizing, heuristic decision aid, "RAPT-OR", that rapidly revises a current Air Taking Order (ATO) to meet the requirements above. Using a set-packing model, RAPT-OR, an ATO near optimally, on a desktop PC, in less than two seconds, for a typical scenario with 40 aircraft, four new targets and hundreds of potential strike packages. RAPT-OR allows decision makers the ability of adjusting risk acceptance in the formulation of possible courses of action by manipulating friendly attrition importance in formulating a solution.

The Marine infantryman is carrying too much weight in combat. This thesis analyzes the trade-offs between individual load weights and the value that a Distributed Operations squad receives from the equipment its members carry. We use multiple objective decision analysis principles to help determine the coefficients for an integer linear programming model. The optimization model prescribes equipment assignment to individual positions that maximizes squad mission success while meeting target weights for the individual Marine. Our findings indicate that significant improvements can be made to the Marine's combat load weight and equipment composition. The optimization model provides the squad with a more efficient combination of equipment while reducing the average weight of the combat load by more than 19 percent for both the assault load and the approach march load. Also, by balancing the loads across the members of the squad, the model reduces the variation of weight across the squad positions from as much as 38 percent to less than 2 percent for all loads. By examining the trade space between equipment weight and equipment value, we assist in the creation of future Marine Corps doctrine by providing senior Marine leaders a starting point analysis for addressing this difficult problem.

Integer Programming problems are difficult to solve. The goal is to find an optimal solution that minimizes cost. With the help of Groebner based algorithms the optimal solution can be found if it exists. The application of the Groebner based algorithm and how it works is the topic of research. The Algorithms are The Conti-Traverso Algorithm and the Original Conti-Traverso Algorithm. Examples are given as well as proofs that correspond to the algorithms. The latter algorithm is more efficient as well as user friendly. The algorithms are not necessarily the best way to solve and integer programming problem, but they do find the optimal solution if it exists.

Virginia’s Department of Conservation and Recreation (DCR) assigns all of Virginia localities to Regional Offices to help conserve the natural resources in a certain region. In this paper, we present a mathematical model for optimizing such assignments by minimizing the travel time and cost of these assignments. With the growing increase in fuel costs and tighter budgets, our solution finds alternate assignments that will help cut costs by 14% annually. We have used integer programming techniques to find optimal assignments which satisfy requirements, respect limitations and minimize cost. Several plans are suggested, some keeping soil and water conservation districts together and some without.

Mixed-integer programming provides a natural framework for modeling optimization problems which require discrete decisions. Valid inequalities, used as cutting-planes and cuttingsurfaces in integer programming solvers, are an essential part of today’s integer programming technology. They enable the solution of mixed-integer programs of greater scale and complexity by providing tighter mathematical descriptions of the feasible solution set. This dissertation presents new structural results on general-purpose valid inequalities for mixedinteger linear and mixed-integer conic programs. Cut-generating functions are a priori formulas for generating a cutting-plane from the data of a mixed-integer linear program. This concept has its roots in the work of Balas, Gomory, and Johnson from the 1970s. It has received renewed attention in the past few years. Gomory and Johnson studied cut-generating functions for the corner relaxation of a mixedinteger linear program, which ignores the nonnegativity constraints on the basic variables in a tableau formulation. We consider models where these constraints are not ignored. In our first contribution, we generalize a classical result of Gomory and Johnson characterizing minimal cut-generating functions in terms of subadditivity, symmetry, and periodicity. Our analysis also exposes shortcomings in the usual definition of minimality in our general setting. To remedy this, we consider stronger notions of minimality and show that these impose additional structure on cut-generating functions. A stronger notion than the minimality of a cut-generating function is its extremality. While extreme cut-generating functions produce powerful cutting-planes, their structure can be very complicated. For the corner relaxation of a one-row integer linear program, Gomory and Johnson identified continuous, piecewise linear, minimal cut-generating functions with only two distinct slope values as a “simple” class of extreme cut-generating functions. In our second contribution, we establish a similar result for a one-row problem which takes the nonnegativity constraint on the basic variable into account. In our third contribution, we consider a multi-row model where only continuous nonbasic variables are present. Conforti, Cornuéjols, Daniilidis, Lemaréchal, and Malick recently showed that not all cutting-planes can be obtained from cut-generating functions in this framework. They also conjectured a natural condition under which cut-generating functions might be sufficient. In our third contribution, we prove that this conjecture is true. This justifies the recent research interest in cut-generating functions for this model. Despite the power of mixed-integer linear programming, many optimization problems of practical and theoretical interest cannot be modeled using a linear objective function and constraints alone. Next, we turn to a natural generalization of mixed-integer linear programming which allows nonlinear convex constraints: mixed-integer conic programming. Disjunctive inequalities, introduced by Balas in the context of mixed-integer linear programming in the 1970s, have been a principal ingredient in the practical success of mixed-integer programming in the last two decades. In order to extend our understanding of disjunctive inequalities to mixed-integer conic programming, we pursue a principled study of two-term disjunctions on conic sets. In our fourth contribution, we consider two-term disjunctions on a general regular cone. A result of Kılınç-Karzan indicates that conic minimal valid linear inequalities are all that is needed for a closed convex hull description of such sets. First we characterize the structure of conic minimal and tight valid linear inequalities for the disjunction. Then we develop structured nonlinear valid inequalities for the disjunction by grouping subsets of valid linear inequalities. We analyze the structure of these inequalities and identify conditions which guarantee that a single such inequality characterizes the closed convex hull of the disjunction. In our fifth and sixth contributions, we extend our earlier results to the cases where the regular cone under consideration is a direct product of second order cones and nonnegative rays and where it is the positive semidefinite cone. Disjunctions on these cones deserve special attention because they provide fundamental relaxations for mixed-integer second-order cone and mixed-integer semidefinite programs. We identify conditions under which our valid convex inequalities can be expressed in computationally tractable forms and present techniques to generate low-complexity relaxations when these conditions are not satisfied. In our final contribution, we provide closed convex hull descriptions for homogeneous two-term disjunctions on the second-order cone and general two-term disjunctions on affine cross-sections of the second-order cone. Our results yield strong convex disjunctive inequalities which can be used as cutting-surfaces in generic mixed-integer conic programming solvers.

Finding integer solutions to linear equations has various real world applications. In the thesis, we investigate its application to the reachability analysis of Petri nets. Introduced by Petri in 1962, Petri net has been a powerful mathematical formalism for modeling, analyzing and designing discrete event systems. In the research community of Petri nets, finding a feasible path from the initial state to the target state in Petri net, known as reachability analysis, is probably one of the most important and challenging subjects. The reachability algebraic analysis is equivalent to finding the nonnegative integer solutions to a fundamental equation constructed from the Petri net. We apply our algorithm in this thesis to reachability analysis of Petri net by finding the nonnegative integer solutions to the fundamental equation. / Finding the optimal binary solution to a quadratic object function is known as the Binary Quadratic Programming problem (BQP), which has been studied extensively in the last three decades. In this thesis, by investigating geometric features of the ellipse contour of a concave quadratic function, we derive new upper and lower bounding methods for BQP. Integrating these new bounding schemes into a proposed solution algorithm of a branch-and-bound type, we propose an exact solution method in solving general BQP with promising preliminary computational results. Meanwhile, by investigating some special structures of the second order matrix and linear term in BQP, several polynomial time algorithms are discussed to solve some special cases of BQP. / In the realm of integer programming, finding integer solutions to linear equations is another important research direction. The problem is proved to be NP-Complete, and several algorithms have been proposed such as the algorithm based on linear Diophantine equations as well as the method based on Groebner bases. Unlike the traditional algorithms, the new efficient method we propose in this thesis is based on our results on zero duality gap and the cell enumeration of an arrangement of hyperplanes in discrete geometry. / Integer programming plays an important role in operations research and has a wide range of applications in various fields. There are a lot of research directions in the area of integer programming. In this thesis, two main topics will be investigated in details. One is to find the optimal binary solution to a quadratic object function, and the other is to find integer solutions to linear equations. / Gu, Shenshen. / Adviser: Wang Jun. / Source: Dissertation Abstracts International, Volume: 73-01, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 98-103). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

by Lui Oi Lun Irene. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 128-132). / Abstracts in English and Chinese. / List of Figures --- p.vii / List of Tables --- p.viii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Satisfiability Problem --- p.1 / Chapter 1.2 --- Motivation of the Research --- p.1 / Chapter 1.3 --- Overview of the Thesis --- p.2 / Chapter 2 --- Constraint Satisfaction Problem and Satisfiability Problem --- p.4 / Chapter 2.1 --- Constraint Programming --- p.4 / Chapter 2.2 --- Satisfiability Problem --- p.6 / Chapter 2.3 --- Methods in Solving SAT problem --- p.7 / Chapter 2.3.1 --- Davis-Putnam-Loveland Procedure --- p.7 / Chapter 2.3.2 --- SATZ by Chu-Min Li --- p.8 / Chapter 2.3.3 --- Local Search for SAT --- p.11 / Chapter 2.3.4 --- Integer Linear Programming Method for SAT --- p.12 / Chapter 2.3.5 --- Semidefinite Programming Method --- p.13 / Chapter 2.4 --- Softwares for SAT --- p.15 / Chapter 2.4.1 --- SAT01 --- p.15 / Chapter 2.4.2 --- "SATZ and SATZ213, contributed by Chu-Min Li" --- p.15 / Chapter 2.4.3 --- Others --- p.15 / Chapter 3 --- Integer Programming --- p.17 / Chapter 3.1 --- Introduction --- p.17 / Chapter 3.1.1 --- Formulation of IPs and BIPs --- p.18 / Chapter 3.1.2 --- Binary Search Tree --- p.19 / Chapter 3.2 --- Methods in Solving IP problem --- p.19 / Chapter 3.2.1 --- Branch-and-Bound Method --- p.20 / Chapter 3.2.2 --- Cutting-Plane Method --- p.23 / Chapter 3.2.3 --- Duality in Integer Programming --- p.26 / Chapter 3.2.4 --- Heuristic Algorithm --- p.28 / Chapter 3.3 --- Zero-one Optimization and Continuous Relaxation --- p.29 / Chapter 3.3.1 --- Introduction --- p.29 / Chapter 3.3.2 --- The Roof Dual expressed in terms of Lagrangian Relaxation --- p.30 / Chapter 3.3.3 --- Determining the Existence of a Duality Gap --- p.31 / Chapter 3.4 --- Software for solving Integer Programs --- p.33 / Chapter 4 --- Integer Programming Formulation for SAT Problem --- p.35 / Chapter 4.1 --- From 3-CNF SAT Clauses to Zero-One IP Constraints --- p.35 / Chapter 4.2 --- From m-Constrained IP Problem to Singly-Constrained IP Problem --- p.38 / Chapter 4.2.1 --- Example --- p.39 / Chapter 5 --- A Basic Branch-and-Bound Algorithm for the Zero-One Polynomial Maximization Problem --- p.42 / Chapter 5.1 --- Reason for choosing Branch-and-Bound Method --- p.42 / Chapter 5.2 --- Searching Algorithm --- p.43 / Chapter 5.2.1 --- Branch Rule --- p.44 / Chapter 5.2.2 --- Bounding Rule --- p.46 / Chapter 5.2.3 --- Fathoming Test --- p.46 / Chapter 5.2.4 --- Example --- p.47 / Chapter 6 --- Revised Bound Rule for Branch-and-Bound Algorithm --- p.55 / Chapter 6.1 --- Revised Bound Rule --- p.55 / Chapter 6.1.1 --- CPLEX --- p.57 / Chapter 6.2 --- Example --- p.57 / Chapter 6.3 --- Conclusion --- p.65 / Chapter 7 --- Revised Branch Rule for Branch-and-Bound Algorithm --- p.67 / Chapter 7.1 --- Revised Branch Rule --- p.67 / Chapter 7.2 --- Comparison between Branch Rule and Revised Branch Rule --- p.69 / Chapter 7.3 --- Example --- p.72 / Chapter 7.4 --- Conclusion --- p.73 / Chapter 8 --- Experimental Results and Analysis --- p.80 / Chapter 8.1 --- Experimental Results --- p.80 / Chapter 8.2 --- Statistical Analysis --- p.33 / Chapter 8.2.1 --- Analysis of Search Techniques --- p.83 / Chapter 8.2.2 --- Discussion of the Performance of SATZ --- p.85 / Chapter 9 --- Concluding Remarks --- p.87 / Chapter 9.1 --- Conclusion --- p.87 / Chapter 9.2 --- Suggestions for Future Research --- p.88 / Chapter A --- Searching Procedures for Solving Constraint Satisfaction Problem (CSP) --- p.91 / Chapter A.1 --- Notation --- p.91 / Chapter A.2 --- Procedures for Solving CSP --- p.92 / Chapter A.2.1 --- Generate and Test --- p.92 / Chapter A.2.2 --- Standard Backtracking --- p.93 / Chapter A.2.3 --- Forward Checking --- p.94 / Chapter A.2.4 --- Looking Ahead --- p.95 / Chapter B --- Complete Results for Experiments --- p.96 / Chapter B.1 --- Complete Result for SATZ --- p.96 / Chapter B.1.1 --- n =5 --- p.95 / Chapter B.1.2 --- n = 10 --- p.98 / Chapter B.1.3 --- n = 30 --- p.99 / Chapter B.2 --- Complete Result for Basic Branch-and-Bound Algorithm --- p.101 / Chapter B.2.1 --- n二5 --- p.101 / Chapter B.2.2 --- n = 10 --- p.104 / Chapter B.2.3 --- n = 30 --- p.107 / Chapter B.3 --- Complete Result for Revised Bound Rule --- p.109 / Chapter B.3.1 --- n = 5 --- p.109 / Chapter B.3.2 --- n = 10 --- p.112 / Chapter B.3.3 --- n = 30 --- p.115 / Chapter B.4 --- Complete Result for Revised Branch-and-Bound Algorithm --- p.118 / Chapter B.4.1 --- n = 5 --- p.118 / Chapter B.4.2 --- n = 10 --- p.121 / Chapter B.4.3 --- n = 30 --- p.124 / Bibliography --- p.128

Modern problems arising in many domains are driving a need for more capable, state-of-the-art optimization tools. A sharp focus on performance and accuracy has appeared, for example, in science and engineering applications. In particular, we have seen a growth in studies related to Polynomial Optimization: a field with beautiful and deep theory, offering flexibility for modeling and high impact in diverse areas. The understanding of structural aspects of the feasible sets in Polynomial Optimization, mainly studied in Real Algebraic Geometry, has a long tradition in Mathematics and it has recently acquired increased computational maturity, opening the gate for new Optimization methodologies to be developed. The celebrated hierarchies due to Lasserre, for example, emerged as good algorithmic templates. They allow the representation of semi-algebraic sets, possibly non-convex, through convex sets in lifted spaces, thus enabling the use of long-studied Convex Optimization methods. Nonetheless, there are some computational drawbacks for these approaches: they often rely on possibly large semidefinite programs, and due to scalability and numerical issues associated with SDPs, alternatives and complements are arising. In this dissertation, we will explore theoretical and practical Integer-Programming-based techniques for Polynomial Optimization problems. We first present a Linear Programming relaxation for the AC-OPF problem in Power Systems, a non-convex quadratic problem, and show how such relaxation can be used to develop a tractable MIP-based algorithm for the AC Transmission Switching problem. From a more theoretical perspective, and motivated by the AC-OPF problem, we study how sparsity can be exploited as a tool for analysis of the fundamental complexity of a Polynomial Optimization problem, by showing LP formulations that can efficiently approximate sparse polynomial problems. Finally, we show a computationally practical approach for constructing strong LP approximations on-the-fly, using cutting plane approaches. We will show two different frameworks that can generate cutting planes, which are based on classical methods used in Mixed-Integer Programming. Our methods mainly rely on the maturity of current MIP technology; we believe these contributions are important for the development of manageable approaches to general Polynomial Optimization problems.

Sugar mills represent significant capital investments. To maintain appropriate returns on their investment, sugar companies seek to run the mills at capacity over the sugarcane harvest season. Because the sugar content of cane degrades considerably once it is cut, maintaining inventories of cut cane is undesirable. Instead, mills want to coordinate the arrival of cut cane with production. We present exact solution approaches exploiting special structure of the sugarcane harvest logistics problem in Brazil and the United States.

This work extends recent research in the development of a number of direct search methods in nonlinear integer programming. The various algorithms use an extension of the well-known FORTRAN MINOS code of Murtagh and Saunders as a starting point. MINOS is capable of solving quite large problems in which the objective function is nonlinear and the constraints linear. The original MINOS code has been extended in various ways by Murtagh, Saunders and co-workers since the original 1978 landmark paper. Extensions have dealt with methods to handle both nonlinear constraints, most notably MINOS/AUGMENTED and integer requirements on a subset of the variables(MINTO). The starting point for the present thesis is the MINTO code of Murtagh. MINTO is a direct descendant of MINOS in that it extends the capabilities to general nonlinear constraints and integer restrictions. The overriding goal for the work described in this thesis is to obtain a good integer-feasible or near-integer-feasible solution to the general NLIP problem while trying to avoid or at least minimize the use of the ubiquitous branch-and-bound techniques. In general, we assume a small number of nonlinearities and a small number of integer variables.Some initial ideas motivating the present work are summarised in an invited paper presented by Murtagh at the 1989 CTAC (Computational Techniques and Applications) conference in Brisbane, Australia. The approach discussed there was to start a direct search procedure at the solution of the continuous relaxation of a nonlinear mixed-integer problem by first removing integer variables from the simplex basis, then adjusting integer-infeasible superbasic variables, and finally checking for local optimality by trial unit steps in the integers. This may be followed by a reoptimization with the latest point as the starting point, but integer variables held fixed. We describe ideas for the further development of Murtagh’s direct search method. Both the old and new approaches aim to attain an integer-feasible solution from an initially relaxed (continuous) solution. Techniques such as branch-and-bound or Scarf’s neighbourhood search [84] may then be used to obtain a locally optimal solution. The present range of direct search methods differs significantly to that described by Murtagh, both in heuristics used and major and minor steps of the procedures. Chapter 5 summarizes Murtagh’s original approach while Chapter 6 describes the new methods in detail.Afeature of the new approach is that some degree of user-interaction (MINTO/INTERACTIVE) has been provided, so that a skilled user can "drive" the solution towards optimality if this is desired. Alternatively the code can still be run in "automatic" mode, where one of five available direct search methods may be specified in the customary SPECS file. A selection of nonlinear integer programming problems taken from the literature has been solved and the results are presented here in the latter chapters. Further, anewcommunications network topology and allocation model devised by Berry and Sugden has been successfully solved by the direct search methods presented herein. The results are discussed in Chapter 14, where the approach is compared with the branch-and-bound heuristic.