Reduced Sample Complexity in Scenario-Based Control System Design via Constraint Scaling

  • Jaeseok Choi
  • Constantino Lagoa
  • Anirudh Subramanyam
    • Categories Control Applications, Convex Optimization, Stochastic Programming Tags , ,

    The scenario approach is widely used in robust control system design and chance-constrained optimization, maintaining convexity without requiring assumptions about the probability distribution of uncertain parameters. However, the approach can demand large sample sizes, making it intractable for safety-critical applications that require very low levels of constraint violation. To address this challenge, we propose a … Read more

    An Efficient Algorithm to the Integrated Shift and Task Scheduling Problem

  • G S R Murthy
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Scheduling Tags , , , , ,

    Abstract   This paper deals with operational models for integrated shift and task scheduling problem. Staff scheduling problem is a special case of this with staff requirements as given input to the problem. Both problems become hard to solve when the problems are considered with flexible shifts. Current literature on these problems leaves good scope … Read more

    When Does Primal Interior Point Method Beat Primal-dual in Linear Optimization?

  • Wenzhi Gao
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , ,

    The primal-dual interior point method (IPM) is widely regarded as the most efficient IPM variant for linear optimization. In this paper, we demonstrate that the improved stability of the pure primal IPM can allow speedups relative to a primal-dual solver, particularly as the IPM approaches convergence.  The stability of the primal scaling matrix makes it … Read more

    Approximating the Gomory Mixed-Integer Cut Closure Using Historical Data

  • Berkay Becu
  • Santanu S. Dey
  • Feng Qiu
  • Alinson S. Xavier
    • Categories (Mixed) Integer Linear Programming

    Many operations related optimization problems involve repeatedly solving similar mixed integer linear programming (MILP) instances with the same constraint matrix but differing objective coefficients and right-hand-side values. The goal of this paper is to generate good cutting-planes for such instances using historical data. Gomory mixed integer cuts (GMIC) for a general MILP can be parameterized … Read more

    Closest Assignment Constraints for Hub Disruption Problems

  • Saikat Mukherjee
  • Prasanna Ramamoorthy
    • Categories Integer Programming Tags , , ,

    Supply chains and logistics can be well represented with hub networks. Operations of these hubs can be disrupted due to unanticipated occurrences or attacks. This study includes Closest assignment Constraints related to hub disruption problems, which can be used in single-level reformulation of the bilevel model. In this study, We propose new sets of constraints … Read more

    The Proximal Bundle Algorithm Under a Frank-Wolfe Perspective: an Improved Complexity Analysis

  • David Fersztand
  • Xu Andy Sun
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , ,

    The proximal bundle algorithm (PBA) is a fundamental and computationally effective algorithm for solving optimization problems with nonsmooth components. We investigate its convergence rate, focusing on composite settings where one function is smooth and the other is piecewise linear. We interpret a sequence of null steps of the PBA as a Frank-Wolfe algorithm on the … Read more

    Jordan and isometric cone automorphisms in Euclidean Jordan algebras

  • Michael Orlitzky
    • Categories Cone Programming, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    Every symmetric cone K arises as the cone of squares in a Euclidean Jordan algebra V. As V is a real inner-product space, we may denote by Isom(V) its group of isometries. The groups JAut(V) of its Jordan-algebra automorphisms and Aut(K) of the linear cone automorphisms are then related. For certain inner products, JAut(V) = … Read more

    Sparse Polynomial Matrix Optimization

  • Jie Wang
  • Feng Guo
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , , ,

    A polynomial matrix inequality is a statement that a symmetric polynomial matrix is positive semidefinite over a given constraint set. Polynomial matrix optimization concerns minimizing the smallest eigenvalue of a symmetric polynomial matrix subject to a tuple of polynomial matrix inequalities. This work explores the use of sparsity methods in reducing the complexity of sum-of-squares … Read more

    Guaranteed bounds for optimal stopping problems using kernel-based non-asymptotic uniform confidence bands

  • Martin Glanzer
  • Sebastian Maier
  • Georg Ch. Pflug
    • Categories Dynamic Programming, Optimization in Data Science, Stochastic Programming Tags , , , ,

    In this paper, we introduce an approach for obtaining probabilistically guaranteed upper and lower bounds on the true optimal value of stopping problems. Bounds of existing simulation-and-regression approaches, such as those based on least squares Monte Carlo and information relaxation, are stochastic in nature and therefore do not come with a finite sample guarantee. Our … Read more

    Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms

  • Victor Bucarey
  • Sophia Calderón
  • Gonzalo Muñoz
  • Frédéric Semet
    • Categories Constrained Nonlinear Optimization, Data Science Applications, Other Topics

    Dealing with uncertainty in optimization parameters is an important and longstanding challenge. Typically, uncertain parameters are predicted accurately, and then a deterministic optimization problem is solved. However, the decisions produced by this so-called predict-then-optimize procedure can be highly sensitive to uncertain parameters. In this work, we contribute to recent efforts in producing decision-focused predictions, i.e., to … Read more