The Sample Average Approximation Method for Stochastic Programs with Integer Recourse

  • Shabbir Ahmed
  • Alexander Shapiro
    • Categories Integer Programming, Stochastic Approaches, Stochastic Programming Tags , , ,

    This paper develops a solution strategy for two-stage stochastic programs with integer recourse. The proposed methodology relies on approximating the underlying stochastic program via sampling, and solving the approximate problem via a specialized optimization algorithm. We show that the proposed scheme will produce an optimal solution to the true problem with probability approaching one exponentially … Read more

    A new class of merit functions for the semidefinite complementarity problem

  • Rosely M. B. Goes
  • Paulo Roberto Oliveira
    • Categories Complementarity and Variational Inequalities, Semi-definite Programming Tags , ,

    Recently,Tseng extended a class of merit functions for the nonlinear complementarity problem to semidefinite complementarity problem (SDCP), showing some properties under suitable assumptions. Yamashita and Fukushima also presented other properties. In this paper, we propose a new class of merit functions for the SDCP, and prove some of those properties, under weaker hypothesis. Particularly, we … Read more

    Improved Interval Constraint Propagation for Constraints on Partial Derivatives

  • Frederic Benhamou
  • Evgueni Petrov
    • Categories Optimization Software Design Principles

    Automatic differentiation (AD) automatically transforms programs which calculate elementary functions into programs which calculate the gradients of these functions. Unlike other differentiation techniques, AD allows one to calculate the gradient of any function at the cost of at most 5 values of the function (in terms of time). Interval constraint programming (ICP) is a part … Read more

    Computational Experience and the Explanatory Value of Condition Numbers for Linear Optimization

  • Robert M. Freund
  • Fernando Ordóñez
    • Categories Linear Programming, Optimization Software and Modeling Systems Tags , ,

    The goal of this paper is to develop some computational experience and test the practical relevance of the theory of condition numbers C(d) for linear optimization, as applied to problem instances that one might encounter in practice. We used the NETLIB suite of linear optimization problems as a test bed for condition number computation and … Read more

    A Robust Primal-Dual Interior-Point Algorithm for Nonlinear Programs

  • Xinwei Liu
  • Jie Sun
    • Categories Constrained Nonlinear Optimization Tags , ,

    We present a primal-dual interior-point algorithm of line-search type for nonlinear programs, which uses a new decomposition scheme of sequential quadratic programming. The algorithm can circumvent the convergence difficulties of some existing interior-point methods. Global convergence properties are derived without assuming regularity conditions. The penalty parameter rho in the merit function is updated automatically such … Read more

    A 1.52-Approximation Algorithm for the Uncapacitated Facility Location Problem

  • Mohammad Mahdian
  • Yinyu Ye
  • Jiawei Zhang
    • Categories Applications - OR and Management Sciences, Production and Logistics, Supply Chain Management Tags

    In this note we present an improved approximation algorithm for the (uncapacitated) metric facility location problem. This algorithm uses the idea of cost scaling, the greedy algorithm of \cite{JMS}, and the greedy augmentation procedure of \cite{CG,GK}. Citation Working Paper, MIT and the University of Iowa Article Download View A 1.52-Approximation Algorithm for the Uncapacitated Facility … Read more

    Statistical inference of multistage stochastic programming problems

  • Alexander Shapiro
    • Categories Stochastic Programming Tags , , , ,

    We discuss in this paper statistical inference of sample average approximations of multistage stochastic programming problems. We show that any random sampling scheme provides a valid statistical lower bound for the optimal value of the true problem. However, in order for such lower bound to be consistent one needs to employ the conditional sampling procedure. … Read more

    Reformulating Linear Programs with Transportation Constraints — with Applications to Workforce Scheduling

  • Tolga Cezik
  • Oktay Gunluk
    • Categories Combinatorial Optimization, Network Optimization Tags , ,

    We study linear programming models that contain transportation constraints in their formulation. Typically, these models have a multi-stage nature and the transportation constraints together with the associated flow variables are used to achieve consistency between consecutive stages. We describe how to reformulate these models by projecting out the flow variables. The reformulation can be more … Read more

    Treewidth: Computational Experiments

  • Hans L. Bodlaender
  • Arie M.C.A. Koster
  • Stan P.M. van Hoesel
    • Categories Graphs and Matroids Tags , , ,

    Many NP-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for many optimization … Read more

    Bounds on measures satisfying moment conditions

  • Jean-Bernard Lasserre
    • Categories Semi-definite Programming, Statistics

    Given a semi algebraic set S of R^n we provide a numerical approximation procedure that yields upper and lower bounds on mu(S), for measures mu that satisfy some given moment conditions. The bounds are obtained as solutions of positive semidefinite programs that can be solved via standard software packages like the LMI MATLAB toolbox. Citation … Read more