On mixed integer reformulations of monotonic probabilistic programming problems with discrete distributions

  • Vladimir I. Norkin
    • Categories (Mixed) Integer Nonlinear Programming, Finance and Economics, Stochastic Programming Tags , , , , ,

    The paper studies large scale mixed integer reformulation approach to stochastic programming problems containing probability and quantile functions, under assumption of discreteness of the probability distribution involved. Jointly with general sample approximation technique and contemporary mixed integer programming solvers the approach gives a regular framework to solution of practical probabilistic programming problems. In the literature … Read more

    Aircraft landing problems with aircraft classes

  • Dirk Briskorn
  • Raik Stolletz
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Transportation Tags , , , ,

    This paper focuses on the aircraft landing problem that is to assign landing times to aircraft approaching the airport under consideration. Each aircraft’s landing time must be in a time interval encompassing a target landing time. If the actual landing time deviates from the target landing time additional costs occur which depend on the amount … Read more

    L1 Minimization via Randomized First Order Algorithms

  • Anatoli Juditsky
  • Fatma Kılınç-Karzan
  • Arkadi Nemirovski
    • Categories Applications - Science and Engineering, Convex Optimization Tags , , ,

    In this paper we propose randomized first-order algorithms for solving bilinear saddle points problems. Our developments are motivated by the need for sublinear time algorithms to solve large-scale parametric bilinear saddle point problems where cheap online assessment of solution quality is crucial. We present the theoretical efficiency estimates of our algorithms and discuss a number … Read more

    The BOBYQA algorithm for bound constrained optimization without derivatives

  • M.J.D. Powell
    • Categories Bound-constrained Optimization

    BOBYQA is an iterative algorithm for finding the minimum of a function F(x) subject to lower and upper bounds on the variables, F(x) being specified by a “black box” that returns the value F(x) for any feasible x. Each iteration employs a quadratic approximation Q to F that satisfies Q(y_j) = F(y_j), j=1,2,…,m, the interpolation … Read more

    Information Geometry and Primal-Dual Interior-point Algorithms

  • Satoshi Kakihara
  • Atsumi Ohara
  • Takashi Tsuchiya
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , , ,

    In this paper, we study polynomial-time interior-point algorithms in view of information geometry. We introduce an information geometric structure for a conic linear program based on a self-concordant barrier function. Riemannian metric is defined with the Hessian of the barrier function. We introduce two connections $\nabla$ and $\nabla^*$ which roughly corresponds to the primal and … Read more

    Truss topology design with integer variables made easy

  • Michal Kočvara
    • Categories (Mixed) Integer Nonlinear Programming, Mechanical Engineering, Semi-definite Programming Tags , ,

    We propose a new look at the problem of truss topology optimization with integer or binary variables. We show that the problem can be equivalently formulated as an integer \emph{linear} semidefinite optimization problem. This makes its numerical solution much easier, compared to existing approaches. We demonstrate that one can use an off-the-shelf solver with default … Read more

    Flows and Decompositions of Games: Harmonic and Potential Games

  • Ozan Candogan
  • Ishai Menache
  • Asuman Ozdaglar
  • Pablo A. Parrilo
    • Categories Game Theory Tags , , ,

    In this paper we introduce a novel flow representation for finite games in strategic form. This representation allows us to develop a canonical direct sum decomposition of an arbitrary game into three components, which we refer to as the potential, harmonic and nonstrategic components. We analyze natural classes of games that are induced by this … Read more

    Combinatorial Integral Approximation

  • Michael N. Jung
  • Christian Kirches
  • Sebastian Sager
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Distributed Control Tags , ,

    We are interested in structures and efficient methods for mixed-integer nonlinear programs (MINLP) that arise from a first discretize, then optimize approach to time-dependent mixed-integer optimal control problems (MIOCPs). In this study we focus on combinatorial constraints, in particular on restrictions on the number of switches on a fixed time grid. We propose a novel … Read more

    Models and Formulations for Multivariate Dominance Constrained Stochastic Programs

  • Benjamin Armbruster
  • James R. Luedtke
    • Categories Stochastic Programming Tags ,

    Dentcheva and Ruszczynski recently proposed using a stochastic dominance constraint to specify risk preferences in a stochastic program. Such a constraint requires the random outcome resulting from one’s decision to stochastically dominate a given random comparator. These ideas have been extended to problems with multiple random outcomes, using the notion of positive linear stochastic dominance. … Read more

    Generic nondegeneracy in convex optimization

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    We show that minimizers of convex functions subject to almost all linear perturbations are nondegenerate. An analogous result holds more generally, for lower-C^2 functions. CitationCornell University, School of Operations Research and Information Engineering, 206 Rhodes Hall Cornell University Ithaca, NY 14853. May 2010. ArticleDownload View PDF