Month: April 2020

Mining for diamonds – matrix generation algorithms for binary quadratically constrained quadratic problems

  • Enrico Bettiol
  • Immanuel M. Bomze
  • Lucas Létocart
  • Francesco Rinaldi
  • Emiliano Traversi
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper, we consider binary quadratically constrained quadratic problems and propose a new approach to generate stronger bounds than the ones obtained using the Semidefinite Programming relaxation. The new relaxation is based on the Boolean Quadric Polytope and is solved via a Dantzig-Wolfe Reformulation in matrix space. For block-decomposable problems, we extend the relaxation … Read more

    Enhancements to the DIDO© Optimal Control Toolbox

  • Isaac Ross
    • Categories Applications - Science and Engineering, Optimization Software and Modeling Systems, Optimization Software Design Principles Tags , , , ,

    In 2020, DIDO© turned 20! The software package emerged in 2001 as a basic, user-friendly MATLAB teaching tool to illustrate the various nuances of Pontryagin’s Principle but quickly rose to prominence in 2007 after NASA announced it had executed a globally optimal maneuver using DIDO. Since then, the toolbox has grown in applications well beyond … Read more

    Epi-convergence of Sample Averages of a Random Lower Semi-continuous Functional Generated by a Markov Chain and Application to Stochastic Optimization

  • John Birge
  • Arnab Sur
    • Categories Stochastic Programming Tags , , , , , ,

    The purpose of this article is to establish epigraphical convergence of the sample averages of a random lower semi-continuous functional associated with a Harris recurrent Markov chain with stationary distribution $\pi$. Sample averages associated with an ergodic Markov chain with stationary probability distribution will epigraphically converge from $\pi$-almost all starting points. The property of Harris … Read more

    Combinatorial Acyclicity Models for Potential-based Flows

  • Oliver Habeck
  • Marc E. Pfetsch
    • Categories (Mixed) Integer Nonlinear Programming, Network Optimization Tags , , ,

    Potential-based flows constitute a basic model to represent physical behavior in networks. Under natural assumptions, the flow in such networks must be acyclic. The goal of this paper is to exploit this property for the solution of corresponding optimization problems. To this end, we introduce several combinatorial models for acyclic flows, based on binary variables … Read more

    K-Adaptability in stochastic optimization

  • Enrico Malaguti
  • Michele Monaci
  • Jonas Prünte
    • Categories Branch and Cut Algorithms, Stochastic Approaches, Stochastic Programming

    We consider stochastic problems in which both the objective function and the feasible set are affected by uncertainty. We address these problems using a K-adaptability approach, in which K solutions for the underlying problem are computed before the uncertainty dissolves and afterwards the best of them can be chosen for the realised scenario. This paradigm … Read more

    An Image-based Approach to Detecting Structural Similarity Among Mixed Integer Programs

  • Mark Karwan
  • Marco E. Lübbecke
  • Chase Murray
  • Zachary Steever
  • Junsong Yuan
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    Operations researchers have long drawn insight from the structure of constraint coefficient matrices (CCMs) for mixed integer programs (MIPs). We propose a new question: Can pictorial representations of CCM structure be used to identify similar MIP models and instances? In this paper, CCM structure is visualized using digital images, and computer vision techniques are employed … Read more

    Optimality Conditions for Constrained Minimax Optimization

  • Yu-Hong Dai
  • Liwei Zhang
    • Categories Constrained Nonlinear Optimization Tags , , , , ,

    Minimax optimization problems arises from both modern machine learning including generative adversarial networks, adversarial training and multi-agent reinforcement learning, as well as from tradition research areas such as saddle point problems, numerical partial differential equations and optimality conditions of equality constrained optimization. For the unconstrained continuous nonconvex-nonconcave situation, Jin, Netrapalli and Jordan (2019) carefully considered … Read more

    Regret in the Newsvendor Model with Demand and Yield Randomness

  • Zhi Chen
  • Weijun Xie
    • Categories Robust Optimization Tags , , , , ,

    We study the fundamental stochastic newsvendor model that considers both demand and yield randomness. It is usually difficult in practice to describe precisely the joint demand and yield distribution, although partial statistical information and empirical data about this ambiguous distribution are often accessible. We combat the issue of distributional ambiguity by taking a data-driven distributionally … Read more

    An algorithm for assortment optimization under parametric discrete choice models

  • Andrea Lodi
  • Tien Mai
    • Categories 0-1 Programming, Applications - OR and Management Sciences Tags , , ,

    This work concerns the assortment optimization problem that refers to selecting a subset of items that maximizes the expected revenue in the presence of the substitution behavior of consumers specified by a parametric choice model. The key challenge lies in the computational difficulty of finding the best subset solution, which often requires exhaustive search. The … Read more

    A Framework for Generalized Benders’ Decomposition and Its Application to Multilevel Optimization

  • Suresh Bolusani
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Game Theory, Stochastic Programming Tags , , ,

    We describe an algorithmic framework generalizing the well-known framework originally introduced by Benders. We apply this framework to several classes of optimization problems that fall under the broad umbrella of multilevel/multistage mixed integer linear optimization problems. The development of the abstract framework and its application to this broad class of problems provides new insights and … Read more