Operations Research and Statistics Seminar
Fall 2021

Nov15

Optimizing Resource Allocation for Military Operations in Maritime SettingRobert M CurryUS Naval Academy Department of MathematicsLocation: CH 320 or virtually at meet.google.com/zqcsvbfkvbTime: 12:00 PM
View Abstract
Territorial claims in contested maritime settings have long been disputed. In recent years, the United States Marine Corps has reestablished their intent to move back toward amphibious operations in order to support the United States Navy in these contested waters. To aid in decisionmaking, we propose two mixedinteger programming models that determine the route and allocation of resources in order to maximize the total value of the area covered using a chain or area of islands depicted as a network of nodes and arcs. The first model is an arcbased approach while the latter is a pathbased approach. In order to solve the latter model faster, we propose a BranchandPrice algorithm whose subproblem can be solved as an instance of a shortestpath problem. While results are forthcoming, we provide a comparison between our two models. Finally, we discuss other application areas for the problem studied in this talk.

Oct27

Optimization without Using Derivatives for Constrained and Unconstrained ProblemsFlorian JarreDepartment of Mathematics, HeinrichHeine University, Dusseldorf, GermanyLocation: Virtually at meet.google.com/zqcsvbfkvbTime: 12:00 PM
View Abstract
The aim is to introduce an easytouse tool for local optimization with up to a few hundred variables, to motivate some new ideas behind this tool, and to demonstrate its potential with an industrial application and with some examples arising, for example, in the design of algorithms. While automatic differentiation offers an elegant and efficient alternative in many cases, due to its simplicity, the minimization without using derivative information is interesting in applications and induces a slight change in the use of the tools for minimization. In particular, we consider a new line search based on leastsquares spline functions, a new finite difference setup, and a variant of the SQP method for constrained minimization.

Oct06

Integer programming for kidney exchangeSommer GentryUSNALocation: CH 320 and meet.google.com/zqcsvbfkvbTime: 12:00 PM
View Abstract
Kidney paired donation matches one patient and his or her incompatible donor with another pair in the same situation for an exchange. We represent patientdonor pairs as vertices of a directed graph G, with edges connecting pairs if the donor of the source is compatible with the recipient of the sink, and maximize the sum of edge weights on disjoint cycles. Because a maximum edgeweight matching might not have the maximum cardinality; there is a risk of an unpredictable tradeoff between quality and quantity of paired donations. The number of paired donations is within a multiplicative factor of the maximum possible donations, where the factor depends on the edge weighting. We design an edge weighting of G which guarantees that every matching with maximum weight also has maximum cardinality, and also maximizes the number of transplants for an exceptional subset of recipients, while favoring immunologic concordance. We will also survey various exponentialsized and polynomialsized integer programming formulations proposed for this problem.

Sep29

PredictorCorrector InteriorPoint Algorithms for Sufficient Linear Complementarity ProblemsTibor IllesCorvinus Centre for Operations Research at Corvinus University, Budapest, HungaryLocation: meet.google.com/zqcsvbfkvbTime: 12:00 PM
View Abstract
The algebraic equivalent transformation (AET) of the system which defines the central path has been introduced by Darvay (2003) for linear programming problems resulting in new search directions for interior point algorithms (IPA). Generalization of AET for some types of IPAs for sufficient linear complementarity problems (SULCP) can cause difficulties, especially for predictorcorrector (PC) ones. After overcoming these difficulties, we introduce new PCIPAs for SULCPs. Moreover, we present a unified discussion of the effect of different AETs on proposing and analysing new IPAs for SULCPs. These new PC IPAs from complexity analysis point of view possess similar properties like IPAs with the best known complexity, namely have polynomial iteration complexity in κ, the dimension n and the bit length L of the problem. There are several known results (Fukuda and Terlaky, 1992; Hertog et al. 1993; Valiaho, 1996; Fukuda et al. 1998; P. Tseng 2000; de Klerk and EisenbergNagy 2011) that discuss properties of the sufficient matrices and explain why it is difficult to generate, recognize (decide) and use these matrices. Furthermore, some algorithms (Csizmadia and Illés, 2006; Illés et al. 2000, 2007, 2009, 2010; Csizmadia et al. 2013, etc.) have been developed that do not need a priori information about the matrix properties. These algorithms could be applied either to solve the LCPs or its dual efficiently or give a polynomial size certificate that the matrix is not sufficient. Recently, Illés and Morapitiye (2018), and EisaenberNagy (2020) have introduced, some new ways of generating sufficient matrices making possible, for the first time, to test the computational performance of IPAs on sufficient LCPs, with positive κ parameter. Our new PC IPAs have been tested on a wellknown, triangular, Pmatrix designed by Zs. Csizmadia (2011) with κ = 22n8 – 0.25, for n ≥4. (The exact κ has been computed by M. EisenbergNagy, 2019.) Computational performance of a variant of our new PC IPA has not been affected by this fact, namely the number of iterations for this interior point algorithm is not exponential in the dimension n. Some preliminary computational studies related to sufficient LCPs will be presented, as well.