mixed-integer programming

Quasi-Monte Carlo methods for two-stage stochastic mixed-integer programs

  • Hernan Leoevey
  • Werner Romisch
    • Categories Stochastic Programming Tags , , , ,

    We consider randomized QMC methods for approximating the expected recourse in two-stage stochastic optimization problems containing mixed-integer decisions in the second stage. It is known that the second-stage optimal value function is piecewise linear-quadratic with possible kinks and discontinuities at the boundaries of certain convex polyhedral sets. This structure is exploited to provide conditions implying … Read more

    On sample average approximation for two-stage stochastic programs without relatively complete recourse

  • Rui Chen
  • James R. Luedtke
    • Categories Stochastic Programming Tags , , ,

    We investigate sample average approximation (SAA) for two-stage stochastic programs without relatively complete recourse, i.e., for problems in which there are first-stage feasible solutions that are not guaranteed to have a feasible recourse action. As a feasibility measure of the SAA solution, we consider the “recourse likelihood”, which is the probability that the solution has … Read more

    Computational Aspects of Infeasibility Analysis in Mixed Integer Programming

  • Timo Berthold
  • Stefan Heinz
  • Jakob Witzig
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    The analysis of infeasible subproblems plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications, obtained by domain propagation, that led to infeasibility. The … Read more

    Rational Polyhedral Outer-Approximations of the Second-Order Cone

  • Burak Kocuk
    • Categories Integer Programming, Linear, Cone and Semidefinite Programming Tags , ,

    It is well-known that the second-order cone can be outer-approximated to an arbitrary accuracy by a polyhedral cone of compact size defined by irrational data. In this paper, we propose two rational polyhedral outer-approximations of compact size retaining the same guaranteed accuracy. The first outer-approximation has the same size as the optimal but irrational outer-approximation … Read more

    Outlier detection in time series via mixed-integer conic quadratic optimization

  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Statistics Tags , , , , ,

    We consider the problem of estimating the true values of a Wiener process given noisy observations corrupted by outliers. The problem considered is closely related to the Trimmed Least Squares estimation problem, a robust estimation procedure well-studied from a statistical standpoint but poorly understood from an optimization perspective. In this paper we show how to … Read more

    Optimization and Validation of Pumping System Design and Operation for Water Supply in High-Rise Buildings

  • Lena C. Altherr
  • Peter F. Pelz
  • Philipp Leise
  • Imke-Sophie Lorenz
  • Tim M. Müller
    • Categories Global Optimization Applications, Mechanical Engineering Tags , , , , ,

    The application of mathematical optimization methods provides the capacity to increase the energy efficiency and to lower the investment costs of technical systems, considerably. We present a system approach for the optimization of the design and operation of pumping systems and exemplify it by applying it to the water supply of high-rise buildings. The underlying … Read more

    Stochastic Optimization Models of Insurance Mathematics

  • Yuri M. Ermoliev
  • Bogdan V. Norkin
  • Vladimir I. Norkin
    • Categories Finance and Economics, Multi-Criteria Optimization, Stochastic Programming Tags , , , , , , , , ,

    The paper overviews stochastic optimization models of insurance mathematics and methods for their solution from the point of view of stochastic programming and stochastic optimal control methodology, with vector optimality criteria. The evolution of an insurance company’s capital is considered in discrete time. The main random variables, which influence this evolution, are levels of payments, … Read more

    New MINLP Formulations for the Unit Commitment Problems with Ramping Constraints

  • Tiziano Bacci
  • Antonio Frangioni
  • Claudio Gentile
  • Kostas Tavlaridis-Gyparakis
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences Tags , , , ,

    The Unit Commitment (UC) problem in electrical power production requires to optimally operate a set of power generation units over a short time horizon (one day to a week). Operational constraints of each unit depend on its type (e.g., thermal, hydro, nuclear, …), and can be rather complex. For thermal units, typical ones concern minimum … Read more

    A geometric way to build strong mixed-integer programming formulations

  • Joey Huchette
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Linear Programming Tags

    We give an explicit geometric way to build mixed-integer programming (MIP) formulations for unions of polyhedra. The construction is simply described in terms of spanning hyperplanes in an r-dimensional linear space. The resulting MIP formulation is ideal, and uses exactly r integer variables and 2 x (# of spanning hyperplanes) general inequality constraints. We use … Read more

    Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework

  • Stephen J. Maher
    • Categories Integer Programming, Optimization Software and Modeling Systems Tags , , , ,

    Benders’ decomposition is a popular mathematical and constraint programming algorithm that is widely applied to exploit problem structure arising from real-world applications. While useful for exploiting structure in mathematical and constraint programs, the use of Benders’ decomposition typically requires significant implementation effort to achieve an effective solution algorithm. Traditionally, Benders’ decomposition has been viewed as … Read more