Shabbir Ahmed

A Lifted Linear Programming Branch-and-Bound Algorithm for Mixed Integer Conic Quadratic Programs

  • Shabbir Ahmed
  • George L. Nemhauser
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Nonlinear Programming

    This paper develops a linear programming based branch-and-bound algorithm for mixed integer conic quadratic programs. The algorithm is based on a higher dimensional or lifted polyhedral relaxation of conic quadratic constraints introduced by Ben-Tal and Nemirovski. The algorithm is different from other linear programming based branch-and-bound algorithms for mixed integer nonlinear programs in that, it … Read more

    An integer programming approach to the OSPF weight setting problem

  • Shabbir Ahmed
  • Amandeep Parmar
  • Joel Sokol
    • Categories Applications - OR and Management Sciences, Integer Programming, Network Optimization Tags , ,

    Under the Open Shortest Path First (OSPF) protocol, traffic flow in an Internet Protocol (IP) network is routed on the shortest paths between each source and destination. The shortest path is calculated based on pre-assigned weights on the network links. The OSPF weight setting problem is to determine a set of weights such that, if … Read more

    Cutting planes for multi-stage stochastic integer programs

  • Shabbir Ahmed
  • Yongpei Guan
  • George L. Nemhauser
    • Categories Cutting Plane Approaches, Stochastic Programming Tags , , ,

    This paper addresses the problem of finding cutting planes for multi-stage stochastic integer programs. We give a general method for generating cutting planes for multi-stage stochastic integer programs based on combining inequalities that are valid for the individual scenarios. We apply the method to generate cuts for a stochastic version of a dynamic knapsack problem … Read more

    Totally Unimodular Stochastic Programs

  • Shabbir Ahmed
  • Andrew J. Schaefer
  • Nan Kong
    • Categories Stochastic Programming

    We consider totally unimodular stochastic programs, that is, stochastic programs whose extensive-form constraint matrix is totally unimodular. We generalize the notion of total unimodularity to apply to sets of matrics and provide properties of such sets. Using this notion, we give several sufficient conditions for specific classes of problems. When solving such problems using the … Read more

    Smooth minimization of two-stage stochastic linear programs

  • Shabbir Ahmed
    • Categories Nonsmooth Optimization, Stochastic Programming Tags ,

    This note presents an application of the smooth optimization technique of Nesterov for solving two-stage stochastic linear programs. It is shown that the original O(1/e) bound of Nesterov on the number of main iterations required to obtain an e-optimal solution is retained. Citation Technical Report, School of Industrial & Systems Engineering, Georgia Institute of Technology, … Read more

    Coherent Risk Measures in Inventory Problems

  • Shabbir Ahmed
  • Ulas Cakmak
  • Alexander Shapiro
    • Categories Production and Logistics, Stochastic Programming Tags , , , ,

    We analyze an extension of the classical multi-period, single-item, linear cost inventory problem where the objective function is a coherent risk measure. Properties of coherent risk measures allow us to offer a unifying treatment of risk averse and min-max type formulations. For the single period newsvendor problem, we show that the structure of the optimal … Read more

    The value of multi-stage stochastic programming in capacity planning under uncertainty

  • Shabbir Ahmed
  • Kai Huang
    • Categories Production and Logistics, Stochastic Programming Tags , , , ,

    This paper addresses a general class of capacity planning problems under uncertainty, which arises, for example, in semiconductor tool purchase planning. Using a scenario tree to model the evolution of the uncertainties, we develop a multi-stage stochastic integer programming formulation for the problem. In contrast to earlier two-stage approaches, the multi-stage model allows for revision … Read more

    Sequential pairing of mixed integer inequalities

  • Shabbir Ahmed
  • Yongpei Guan
  • George L. Nemhauser
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We present a scheme for generating new valid inequalities for mixed integer programs by taking pair-wise combinations of existing valid inequalities. Our scheme is related to mixed integer rounding and mixing. The scheme is in general sequence-dependent and therefore leads to an exponential number of inequalities. For some important cases, we identify combination sequences that … Read more

    A Branch-Reduce-Cut Algorithm for the Global Optimization of Probabilistically Constrained Linear Programs

  • Shabbir Ahmed
  • Faiz Al-Khayyal
  • Myun-Seok Cheon
    • Categories Global Optimization, Stochastic Programming

    We consider probabilistic constrained linear programs with general distributions for the uncertain parameters. These problems generally involve non-convex feasible sets. We develop a branch and bound algorithm that searches for a global solution to this problem by successively partitioning the non-convex feasible region and by using bounds on the objective function to fathom inferior partitions. … Read more

    Mean-risk objectives in stochastic programming

  • Shabbir Ahmed
    • Categories Nonsmooth Optimization, Stochastic Programming Tags , , ,

    Traditional stochastic programming is risk neutral in the sense that it is concerned with the optimization of an expectation criteria. A common approach to addressing risk in decision making problems is to consider a weighted mean-risk criterion, where some dispersion statistic is used as a measure of risk. We investigate the computational suitability of various … Read more