Stochastic Decomposition for Two-stage Stochastic Linear Programs with Random Cost Coefficients

  • Harsha Gangammanavar
  • Yifan Liu
  • Suvrajeet Sen
    • Categories Stochastic Programming Tags , , , ,

    Stochastic decomposition (SD) has been a computationally effective approach to solve large-scale stochastic programming (SP) problems arising in practical applications. By using incremental sampling, this approach is designed to discover an appropriate sample size for a given SP instance, thus precluding the need for either scenario reduction or arbitrary sample sizes to create sample average … Read more

    Tight-and-cheap conic relaxation for the optimal reactive power dispatch problem

  • Miguel F. Anjos
  • Christian Bingane
  • Sébastien Le Digabel
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    The optimal reactive power dispatch (ORPD) problem is an alternating current optimal power flow (ACOPF) problem where discrete control devices for regulating the reactive power, such as shunt elements and tap changers, are considered. The ORPD problem is modelled as a mixed-integer nonlinear optimization problem and its complexity is increased compared to the ACOPF problem, … Read more

    Two-stage stochastic days-off scheduling of multi-skilled analysts with training options

  • Douglas S. Altner
  • Erica Mason
  • Leslie D. Servi
    • Categories Applications - OR and Management Sciences, Stochastic Programming Tags , , , , ,

    Motivated by a cybersecurity application, this paper studies a two-stage, stochastic days-off scheduling problem with 1) many types of jobs that require specialized training, 2) many multi-skilled analysts, 3) the ability to shape analyst skill sets through training decisions, and 4) a large number of possible future demand scenarios. We provide a integer linear program … Read more

    Subset selection in sparse matrices

  • Alberto Del Pia
  • Santanu S. Dey
  • Robert Weismantel
    • Categories Global Optimization Theory, Nonlinear Systems and Least-Squares Tags , , ,

    In subset selection we search for the best linear predictor that involves a small subset of variables. From a computational complexity viewpoint, subset selection is NP-hard and few classes are known to be solvable in polynomial time. Using mainly tools from discrete geometry, we show that some sparsity conditions on the original data matrix allow … Read more

    Mathematical models for stable matching problems with ties and incomplete lists

  • Maxence Delorme
  • Jacek Gondzio
  • William Pettersson
  • Sergio García
  • Joerg Kalcsics
  • David Manlove
    • Categories Combinatorial Optimization, Integer Programming Tags , , , ,

    We present new integer linear programming (ILP) models for NP-hard optimisation problems in instances of the Stable Marriage problem with Ties and Incomplete lists (SMTI) and its many-to-one generalisation, the Hospitals / Residents problem with Ties (HRT). These models can be used to efficiently solve these optimisation problems when applied to (i) instances derived from … Read more

    Low-M-Rank Tensor Completion and Robust Tensor PCA

  • Bo Jiang
  • Shiqian Ma
  • Shuzhong Zhang
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization, Nonlinear Optimization

    In this paper, we propose a new approach to solve low-rank tensor completion and robust tensor PCA. Our approach is based on some novel notion of (even-order) tensor ranks, to be called the M-rank, the symmetric M-rank, and the strongly symmetric M-rank. We discuss the connections between these new tensor ranks and the CP-rank and … Read more

    Global Solutions of Nonconvex Standard Quadratic Programs via Mixed Integer Linear Programming Reformulations

  • Jacek Gondzio
  • E. Alper Yildirim
    • Categories (Mixed) Integer Linear Programming, Quadratic Programming Tags , , ,

    A standard quadratic program is an optimization problem that consists of minimizing a (nonconvex) quadratic form over the unit simplex. We focus on reformulating a standard quadratic program as a mixed integer linear programming problem. We propose two alternative mixed integer linear programming formulations. Our first formulation is based on casting a standard quadratic program … Read more

    Optimal Transport Based Distributionally Robust Optimization: Structural Properties and Iterative Schemes

  • Jose Blanchet
  • Karthyek Murthy
  • Fan Zhang
    • Categories Robust Optimization, Stochastic Programming Tags , , , , , , ,

    We consider optimal transport based distributionally robust optimization (DRO) problems with locally strongly convex transport cost functions and affine decision rules. Under conventional convexity assumptions on the underlying loss function, we obtain structural results about the value function, the optimal policy, and the worst-case optimal transport adversarial model. These results expose a rich structure embedded … Read more

    Decision Diagram Decomposition for Quadratically Constrained Binary Optimization

  • David Bergman
  • Leonardo Lozano
    • Categories Constrained Nonlinear Optimization, Integer Programming, Quadratic Programming

    In recent years the use of decision diagrams within the context of discrete optimization has proliferated. This paper continues this expansion by proposing the use of decision diagrams for modeling and solving binary optimization problems with quadratic constraints. The model proposes the use of multiple decision diagrams to decompose a quadratic matrix so that each … Read more

    Integer Models for the Asymmetric Traveling Salesman Problem with Pickup and Delivery

  • Karla Hoffman
  • Ryan J. O'Neil
    • Categories Transportation

    We propose a new Mixed Integer Programming formulation for the Asymmetric Traveling Salesman Problem with Pickup and Delivery, along with valid inequalities for the Sarin-Sherali-Bhootra formulation. We study these models in their complete forms, relax complicating constraints of these models, and compare their performance. Finally, we present computational results showing the promise of these formulations … Read more