James R. Luedtke

Nonanticipative duality, relaxations, and formulations for chance-constrained stochastic programs

  • Shabbir Ahmed
  • James R. Luedtke
  • Yongjia Song
  • Weijun Xie
    • Categories Stochastic Programming Tags , ,

    We propose two new Lagrangian dual problems for chance-constrained stochastic programs based on relaxing nonanticipativity constraints. We compare the strength of the proposed dual bounds and demonstrate that they are superior to the bound obtained from the continuous relaxation of a standard mixed-integer programming (MIP) formulation. For a given dual solution, the associated Lagrangian relaxation … Read more

    Decomposition Algorithms for Two-Stage Chance-Constrained Programs

  • Simge Küçükyavuz
  • James R. Luedtke
  • Xiao Liu
    • Categories Branch and Cut Algorithms, Integer Programming, Stochastic Programming Tags , , ,

    We study a class of chance-constrained two-stage stochastic optimization problems where second-stage feasible recourse decisions incur additional cost. In addition, we propose a new model, where “recovery” decisions are made for the infeasible scenarios to obtain feasible solutions to a relaxed second-stage problem. We develop decomposition algorithms with specialized optimality and feasibility cuts to solve … Read more

    Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse

  • Merve Bodur
  • Sanjeeb Dash
  • Oktay Gunluk
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Stochastic Programming Tags , ,

    With stochastic integer programming as the motivating application, we investigate techniques to use integrality constraints to obtain improved cuts within a Benders decomposition algorithm. We compare the effect of using cuts in two ways: (i) cut-and-project, where integrality constraints are used to derive cuts in the extended variable space, and Benders cuts are then used … Read more

    Models and Solution Techniques for Production Planning Problems with Increasing Byproducts

  • Jeff Linderoth
  • James R. Luedtke
  • Srikrishna Sridhar
    • Categories Applications - OR and Management Sciences, Chemical Engineering, Facility Planning and Design Tags , ,

    We consider a production planning problem where the production process creates a mixture of desirable products and undesirable byproducts. In this production process, at any point in time the fraction of the mixture that is an undesirable byproduct increases monotonically as a function of the cumulative mixture production up to that time. The mathematical formulation … Read more

    Mixed-Integer Rounding Enhanced Benders Decomposition for Multiclass Service System Staffing and Scheduling with Arrival Rate Uncertainty

  • Merve Bodur
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Stochastic Programming Tags , , , ,

    We study server scheduling in multiclass service systems under stochastic uncertainty in the customer arrival volumes. Common practice in such systems is to first identify staffing levels, and then determine schedules for the servers that cover these targets. We propose a new stochastic integer programming model that integrates these two decisions, which can yield lower … Read more

    Locally Ideal Formulations for Piecewise Linear Functions with Indicator Variables

  • Jeff Linderoth
  • James R. Luedtke
  • Srikrishna Sridhar
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering

    In this paper, we consider mixed integer linear programming (MIP) formulations for piecewise linear functions (PLFs) that are evaluated when an indicator variable is turned on. We describe modifications to standard MIP formulations for PLFs with desirable theoretical properties and superior computational performance in this context. Citation Technical Report #1788, Computer Sciences Department, University of … Read more

    Mixed-Integer Nonlinear Optimization

  • Pietro Belotti
  • Christian Kirches
  • Sven Leyffer
  • Jeff Linderoth
  • James R. Luedtke
  • Ashutosh Mahajan
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    Many optimal decision problems in scientific, engineering, and public sector applications involve both discrete decisions and nonlinear system dynamics that affect the quality of the final design or plan. These decision problems lead to mixed-integer nonlinear programming (MINLP) problems that combine the combinatorial difficulty of optimizing over discrete variable sets with the challenges of handling … Read more

    Chance-constrained binary packing problems

  • Simge Küçükyavuz
  • James R. Luedtke
  • Yongjia Song
    • Categories Integer Programming, Stochastic Programming Tags ,

    We consider a class of packing problems with uncertain data, which we refer to as the chance-constrained binary packing problem. In this problem, a subset of items is selected that maximizes the total profit so that a generic packing constraint is satisfied with high probability. Interesting special cases of our problem include chance-constrained knapsack and … Read more

    Branch-and-cut Approaches for Chance-constrained Formulations of Reliable Network Design Problems

  • James R. Luedtke
  • Yongjia Song
    • Categories Branch and Cut Algorithms, Stochastic Programming Tags , ,

    We study solution approaches for the design of reliably connected networks. Speci fically, given a network with arcs that may fail at random, the goal is to select a minimum cost subset of arcs such the probability that a connectivity requirement is satis ed is at least 1-\epsilon, where \epsilon is a risk tolerance. We consider two … Read more

    Strong Branching Inequalities for Convex Mixed Integer Nonlinear Programs

  • Mustafa Kilinc
  • Jeff Linderoth
  • James R. Luedtke
  • Andrew J. Miller
    • Categories (Mixed) Integer Nonlinear Programming

    Strong branching is an effective branching technique that can significantly reduce the size of the branch-and-bound tree for solving Mixed Integer Nonlinear Programming (MINLP) problems. The focus of this paper is to demonstrate how to effectively use discarded information from strong branching to strengthen relaxations of MINLP problems. Valid inequalities such as branching-based linearizations, various … Read more