Skip to main content Skip to footer site map
Mathematics Department

Operations Research and Statistics Seminar

Fall 2021

  • Dec
    08
  • On different formulations of Control Tabular Adjustment Problem
    Dr. Goran Lesaja
    USNA and Georgia Southern University
    Location: CH 320 or virtually at meet.google.com/zqc-svbf-kvb
    Time: 12:00 PM

    View Abstract

    In this talk we consider a Controlled Tabular Adjustment (CTA) model for statistical disclosure limitation (control) of tabular data. The goal of the CTA model is to find the closest safe table to some original tabular data set that contains sensitive information. The closeness of the original and masked table is usually measured using L_1 or L_2 norm; with each measure having its advantages and disadvantages. In the first part of the talk, a Second Order Cone reformulation of the L_1 CTA model is presented as an alternative to the traditional Linear Programming formulation. In the second part of the talk we explore different measures of closeness between the original and masked tables which are based on table statistics. In particular we discuss a CTA model based on minimizing the difference between chi-square statistics of original and masked tables.
  • Dec
    02
  • Global Complexity Bound of a Proximal ADMM for Linearly-Constrained Nonseparable Nonconvex Composite Programming
    Renato Monteiro
    School of Industrial and Systems Engineering (ISyE), Georgia Institute of Technology, USA
    Location: Online via Google Meet link meet.google.com/zqc-svbf-kvb
    Time: 12:00 PM

    View Abstract

    This talk discusses a dampened proximal alternating direction method of multipliers (DP.ADMM) for solving linearly-constrained nonconvex optimization problems where the smooth part of the objective function is nonseparable. Each iteration of DP.ADMM consists of: (ii) a sequence of partial proximal augmented Lagrangian (AL) updates, (ii) an under-relaxed Lagrange multiplier update, and (iii) a novel test to check whether the penalty parameter of the AL function should be updated. Under a basic Slater point condition and some requirements on the dampening factor and under-relaxation parameter, it is shown that DP.ADMM obtains a first-order stationary point of the constrained problem in ${\cal O}(\varepsilon^{-3})$ iterations for a given numerical tolerance $\varepsilon>0$. One of the main novelties of the paper is that convergence of the method is obtained without requiring any rank assumptions on the constraint matrices.
  • Nov
    23
  • Can Autonomous Vehicles Solve the Commuter Parking Problem?
    Neda Mirzaeian
    Operations Management at the Tepper School of Business, Carnegie Mellon University
    Location: Virtually at meet.google.com/zqc-svbf-kvb
    Time: 12:00 PM

    View Abstract

    We investigate how autonomous vehicles (AVs) may change the morning commute travel pattern and improve downtown parking. We develop a continuous-time traffic model that takes into account key economic deterrents to driving, such as parking fee and traffic congestion, and characterize the departure time and parking location (downtown or outside downtown parking area) patterns of commuters in equilibrium. To illustrate our results, our model is calibrated to data from Pittsburgh. For the calibrated model, our analysis shows that all AV commuters choose to park outside downtown, increasing both vehicle hours and vehicle miles traveled as compared to the case with all human-driven vehicles. This change increases the total system cost and suggests a potential downtown land-use change (e.g., repurposing downtown parking spots to commercial and residential areas) in Pittsburgh after mass adoption of AVs. To reduce the total system cost, a social planner may be interested in regulating commuters' decisions by adjusting parking fees and/or imposing congestion tolls as a short-term measure, or adjusting infrastructure, e.g., converting downtown parking spaces to curbside drop-off spots for AVs. Our results indicate that these measures can reduce the total system cost substantially (e.g., up to 70% in our calibrated model).
  • Nov
    15
  • Optimizing Resource Allocation for Military Operations in Maritime Setting
    Robert M Curry
    US Naval Academy Department of Mathematics
    Location: CH 320 or virtually at meet.google.com/zqc-svbf-kvb
    Time: 12:00 PM

    View Abstract

    Territorial claims in contested maritime settings have long been disputed. In recent years, the United States Marine Corps has re-established their intent to move back toward amphibious operations in order to support the United States Navy in these contested waters. To aid in decision-making, we propose two mixed-integer 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 arc-based approach while the latter is a path-based approach. In order to solve the latter model faster, we propose a Branch-and-Price algorithm whose sub-problem can be solved as an instance of a shortest-path 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.
  • Oct
    27
  • Optimization without Using Derivatives for Constrained and Unconstrained Problems
    Florian Jarre
    Department of Mathematics, Heinrich-Heine University, Dusseldorf, Germany
    Location: Virtually at meet.google.com/zqc-svbf-kvb
    Time: 12:00 PM

    View Abstract

    The aim is to introduce an easy-to-use 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 least-squares spline functions, a new finite difference setup, and a variant of the SQP method for constrained minimization.
  • Oct
    06
  • Integer programming for kidney exchange
    Sommer Gentry
    USNA
    Location: CH 320 and meet.google.com/zqc-svbf-kvb
    Time: 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 patient-donor 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 edge-weight matching might not have the maximum cardinality; there is a risk of an unpredictable trade-off 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 exponential-sized and polynomial-sized integer programming formulations proposed for this problem.
  • Sep
    29
  • Predictor-Corrector Interior-Point Algorithms for Sufficient Linear Complementarity Problems
    Tibor Illes
    Corvinus Centre for Operations Research at Corvinus University, Budapest, Hungary
    Location: meet.google.com/zqc-svbf-kvb
    Time: 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 (SU-LCP) can cause difficulties, especially for predictor-corrector (PC) ones. After overcoming these difficulties, we introduce new PC-IPAs for SU-LCPs. Moreover, we present a unified discussion of the effect of different AETs on proposing and analysing new IPAs for SU-LCPs. 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 Eisenberg-Nagy 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 Eisaenber-Nagy (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 well-known, triangular, P-matrix designed by Zs. Csizmadia (2011) with κ = 22n-8 – 0.25, for n ≥4. (The exact κ has been computed by M. Eisenberg-Nagy, 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.
go to Top