Robust combinatorial optimization problems under locally budgeted interdiction uncertainty against the objective function and covering constraints

  • Alejandro Crema
    • Categories Combinatorial Optimization, Robust Optimization Tags ,

    Recently robust combinatorial optimization problems with budgeted interdiction uncertainty affecting cardinality-based constraints or objective were considered by presenting, comparing and experimenting with compact formulations. In this paper we present a compact formulation for the case in which locally budgeted interdiction uncertainty affects the objective function and covering constraints simultaneously. ArticleDownload View PDF

    The SCIP Optimization Suite 10.0

  • Christopher Hojny
  • Mathieu Besançon
  • Ksenia Bestuzheva
  • Sander Borst
  • Antonia Chmiela
  • João Dionísio
  • Leon Eifler
  • Mohammed Ghannam
  • Ambros Gleixner
  • Adrian Göß
  • Alexander Hoen
  • Rolf van der Hulst
  • Dominik Kamp
  • Thorsten Koch
  • Kevin Kofler
  • Jurgen Lentz
  • Stephen J. Maher
  • Gioni Mexi
  • Erik Mühmer
  • Marc E. Pfetsch
  • Sebastian Pokutta
  • Felipe Serrano
  • Yuji Shinano
  • Mark Turner
  • Stefan Vigerske
  • Matthias Walter
  • Dieter Weninger
  • Liding Xu
    • Categories Integer Programming, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , , , , , , ,

    The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming (CIP) framework SCIP. This report discusses the enhancements and extensions included in SCIP Optimization Suite 10.0. The updates in SCIP 10.0 include a new solving mode for exactly solving rational mixed-integer linear programs, a new presolver … Read more

    On Solving Chance-Constrained Models with Gaussian Mixture Distribution

  • Shibshankar Dey
  • Sanjay Mehrotra
  • Anirudh Subramanyam
    • Categories Nonlinear Optimization, Stochastic Programming, Yield Management Tags , , , , , ,

    We study linear chance-constrained problems where the coefficients follow a Gaussian mixture distribution. We provide mixed-binary quadratic programs that give inner and outer approximations of the chance constraint based on piecewise linear approximations of the standard normal cumulative density function. We show that $O\left(\sqrt{\ln(1/\tau)/\tau} \right)$ pieces are sufficient to attain $\tau$-accuracy in the chance constraint. … Read more

    On the Convergence of Constrained Gradient Method

  • Danqing Zhou
  • Hongmei Chen
  • Shiqian Ma
  • Junfeng Yang
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags ,

    The constrained gradient method (CGM) has recently been proposed to solve convex optimization and monotone variational inequality (VI) problems with general functional constraints. While existing literature has established convergence results for CGM, the assumptions employed therein are quite restrictive; in some cases, certain assumptions are mutually inconsistent, leading to gaps in the underlying analysis. This … Read more

    Supermodularity, Curvature, and Convex Relaxations in a Class of Quadratic Binary Optimization Problems

  • Bismark Singh
    • Categories Combinatorial Optimization, Convex and Nonsmooth Optimization Tags , , ,

    We study the combinatorial structure of a quadratic set function $F(S)$ arising from a class of binary optimization models within the family of undesirable facility location problems. Despite strong empirical evidence of nested optimal solutions in previously studied real-world instances, we show that $F(S)$ is, in general, neither submodular nor supermodular. To quantify deviation from … Read more

    Stochastic Mixed-Integer Programming: A Survey

  • Ward Romeijnders
  • Yihang Zhang
  • Suvrajeet Sen
    • Categories Stochastic Programming Tags ,

    The goal of this survey is to provide a road-map for exploring the growing area of stochastic mixed-integer programming (SMIP) models and algorithms. We provide a comprehensive overview of existing decomposition algorithms for two-stage SMIPs, including Dantzig-Wolfe decomposition, dual decomposition, Lagrangian cuts, and decomposition approaches using parametric cutting planes and scaled cuts. Moreover, we explicitly … Read more

    Structure-Preserving Symmetry Presolving for Mixed-Binary Linear Problems

  • Annika Jaeger
  • Marc E. Pfetsch
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming Tags , ,

    This paper investigates a presolving method for handling symmetries in mixed-binary programs, based on inequalities computed from so-called Schreier-Sims tables. We show that an iterative application of this method together with merging variables will produce an instance for which the symmetry group is trivial. We then prove that the problem structure can be preserved for … Read more

    An alternating optimization approach for robust optimal control in chromatography

  • Dominik H. Cebulla
  • Andrea Gilch
  • Jan Hendrik Rolfes
  • Christian Kirches
  • Frauke Liers
    • Categories Optimization of Systems modeled by PDEs, Robust Optimization Tags , ,

    Chromatographic separation plays a vital role in various areas, as this technique can deliver high-quality products both in lab- and industrial-scale processes. Economical and also ecological benefits can be expected when optimizing such processes with mathematical methods. However, even small perturbations in the operating conditions can result in significantly altered results, which may lead to … Read more