Kibaek Kim

Dual Decomposition of Two-Stage Distributionally Robust Mixed-Integer Programming under the Wasserstein Ambiguity Set

  • Kibaek Kim
    • Categories (Mixed) Integer Linear Programming, Robust Optimization, Stochastic Programming Tags , ,

    We develop a dual decomposition of two-stage distributionally robust mixed-integer programming (DRMIP) under the Wasserstein ambiguity set. The dual decomposition is based on the Lagrangian dual of DRMIP, which results from the Lagrangian relaxation of the nonanticipativity constraints and min-max inequality. We present two Lagrangian dual problem formulations, each of which is based on different principle. We show … Read more

    Data-Driven Two-Stage Conic Optimization with Zero-One Uncertainties

  • Mohamed El Tonbari
  • Kibaek Kim
  • Anirudh Subramanyam
    • Categories Robust Optimization, Stochastic Programming Tags , , ,

    We address high-dimensional zero-one random parameters in two-stage convex conic optimization problems. Such parameters typically represent failures of network elements and constitute rare, high-impact random events in several applications. Given a sparse training dataset of the parameters, we motivate and study a distributionally robust formulation of the problem using a Wasserstein ambiguity set centered at … Read more

    A Bilevel Approach for Identifying the Worst Contingencies for Nonconvex Alternating Current Power Systems

  • Brian Dandurand
  • Kibaek Kim
  • Sven Leyffer
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Robust Optimization Tags , , ,

    We address the bilevel optimization problem of identifying the most critical attacks to an alternating current (AC) power flow network. The upper-level binary maximization problem consists in choosing an attack that is treated as a parameter in the lower-level defender minimization problem. Instances of the lower-level global minimization problem by themselves are NP-hard due to … Read more

    Scalable Branching on Dual Decomposition of Stochastic Mixed-Integer Programming Problems

  • Brian Dandurand
  • Kibaek Kim
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms, Stochastic Programming

    We present a scalable branching method for the dual decomposition of stochastic mixed-integer programming. Our new branching method is based on the branching method proposed by Caro e and Schultz that creates branching disjunctions on first-stage variables only. We propose improvements to the process for creating branching disjunctions, including 1) branching on the optimal solutions … Read more

    A Stochastic Electricity Market Clearing Formulation with Consistent Pricing Properties

  • Mihai Anitescu
  • John Birge
  • Kibaek Kim
  • Victor M. Zavala
    • Categories Applications - OR and Management Sciences, Convex and Nonsmooth Optimization, Stochastic Programming

    We argue that deterministic market clearing formulations introduce arbitrary distortions between day-ahead and expected real-time prices that bias economic incentives and block diversi cation. We extend and analyze the stochastic clearing formulation proposed by Pritchard et al. (2010) in which the social surplus function induces penalties between day-ahead and real-time quantities. We prove that the formulation … Read more

    Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs

  • Kibaek Kim
  • Victor M. Zavala
    • Categories Optimization Software and Modeling Systems, Parallel Algorithms, Stochastic Programming

    We develop algorithmic innovations for the dual decomposition method to address two-stage stochastic programs with mixed-integer recourse and provide a parallel software implementation that we call DSP. Our innovations include the derivation of valid inequalities that tighten Lagrangian subproblems and that allow the guaranteed recovery of feasible solutions for problems without (relative) complete recourse. We … Read more

    A Two-Stage Stochastic Integer Programming Approach to Integrated Staffing and Scheduling with Application to Nurse Management

  • Kibaek Kim
  • Sanjay Mehrotra
    • Categories (Mixed) Integer Nonlinear Programming, Scheduling, Stochastic Programming Tags , , , , ,

    We study the problem of integrated staffing and scheduling under demand uncertainty. The problem is formulated as a two-stage stochastic integer program with mixed-integer recourse. The here-and-now decision is to find initial staffing levels and schedules, well ahead in time. The wait-and-see decision is to adjust these schedules at a time epoch closer to the … Read more