James R. Luedtke

A Branch-and-Cut Decomposition Algorithm for Solving Chance-Constrained Mathematical Programs with Finite Support

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

    We present a new approach for exactly solving chance-constrained mathematical programs having discrete distributions with nite support and random polyhedral constraints. Such problems have been notoriously difficult to solve due to nonconvexity of the feasible region, and most available methods are only able to nd provably good solutions in certain very special cases. Our approach … Read more

    Effective Separation of Disjunctive Cuts for Convex Mixed Integer Nonlinear Programs

  • Mustafa Kılınç
  • Jeff Linderoth
  • James R. Luedtke
    • Categories (Mixed) Integer Nonlinear Programming Tags ,

    We describe a computationally effective method for generating disjunctive inequalities for convex mixed-integer nonlinear programs (MINLPs). The method relies on solving a sequence of cut-generating linear programs, and in the limit will generate an inequality as strong as can be produced by the cut-generating nonlinear program suggested by Stubbs and Mehrotra. Using this procedure, we … Read more

    Some Results on the Strength of Relaxations of Multilinear Functions

  • Jeff Linderoth
  • James R. Luedtke
  • Mahdi Namazifar
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , ,

    We study approaches for obtaining convex relaxations of global optimization problems containing multilinear functions. Specifically, we compare the concave and convex envelopes of these functions with the relaxations that are obtained with a standard relaxation approach, due to McCormick. The standard approach reformulates the problem to contain only bilinear terms and then relaxes each term … 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

    New Formulations for Optimization Under Stochastic Dominance Constraints

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

    Stochastic dominance constraints allow a decision-maker to manage risk in an optimization setting by requiring their decision to yield a random outcome which stochastically dominates a reference random outcome. We present new integer and linear programming formulations for optimization under first and second-order stochastic dominance constraints, respectively. These formulations are more compact than existing formulations, … Read more

    A Sample Approximation Approach for Optimization with Probabilistic Constraints

  • Shabbir Ahmed
  • James R. Luedtke
    • Categories Stochastic Programming Tags , , , ,

    We study approximations of optimization problems with probabilistic constraints in which the original distribution of the underlying random vector is replaced with an empirical distribution obtained from a random sample. We show that such a sample approximation problem with risk level larger than the required risk level will yield a lower bound to the true … Read more

    An integer programming approach for linear programs with probabilistic constraints

  • Shabbir Ahmed
  • James R. Luedtke
  • George L. Nemhauser
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

    Linear programs with joint probabilistic constraints (PCLP) are difficult to solve because the feasible region is not convex. We consider a special case of PCLP in which only the right-hand side is random and this random vector has a finite distribution. We give a mixed-integer programming formulation for this special case and study the relaxation … Read more