linear programming

Toward breaking the curse of dimensionality: an FPTAS for stochastic dynamic programs with multidimensional action and scalar state

  • Nir Halman
  • Giacomo Nannicini
    • Categories Approximation Algorithms, Dynamic Programming, Supply Chain Management Tags , , , ,

    We propose a Fully Polynomial-Time Approximation Scheme (FPTAS) for stochastic dynamic programs with multidimensional action, scalar state, convex costs and linear state transition function. The action spaces are polyhedral and described by parametric linear programs. This type of problems finds applications in the area of optimal planning under uncertainty, and can be thought of as … Read more

    DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization

  • Amir Ali Ahmadi
  • Anirudha Majumdar
    • Categories Linear Programming, Second-Order Cone Programming, Semi-definite Programming Tags , , , , ,

    In recent years, optimization theory has been greatly impacted by the advent of sum of squares (SOS) optimization. The reliance of this technique on large-scale semidefinite programs however, has limited the scale of problems to which it can be applied. In this paper, we introduce DSOS and SDSOS optimization as linear programming and second-order cone … Read more

    Random projections for trust region subproblems

  • Claudia D'Ambrosio
  • Leo Liberti
  • Pierre-Louis Poirion
  • Ky Vu
    • Categories Linear Programming, Quadratic Programming Tags , ,

    The trust region method is an algorithm traditionally used in the field of derivative free optimization. The method works by iteratively constructing surrogate models (often linear or quadratic functions) to approximate the true objective function inside some neighborhood of a current iterate. The neighborhood is called “trust region” in the sense that the model is … Read more

    Generation techniques for linear and integer programming instances with controllable properties

  • Davaatseren Baatar
  • Hans D Mittelmann
  • Simon Bowly
  • Kate Smith-Miles
    • Categories (Mixed) Integer Linear Programming, Optimization Software and Modeling Systems Tags , ,

    This paper addresses the problem of generating synthetic test cases for experimentation in linear programming. We propose a method which maps instance generation and instance space search to an alternative encoded space. This allows us to develop a generator for feasible bounded linear programming instances with controllable properties. We show that this method is capable … Read more

    Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time

  • Mengdi Wang
    • Categories Dynamic Programming, Linear Programming Tags , , , , , ,

    We propose a randomized linear programming algorithm for approximating the optimal policy of the discounted Markov decision problem. By leveraging the value-policy duality, the algorithm adaptively samples state transitions and makes exponentiated primal-dual updates. We show that it finds an ε-optimal policy using nearly-linear running time in the worst case. For Markov decision processes that … Read more

    The SCIP Optimization Suite 4.0

  • Tobias Fischer
  • Tristan Gally
  • Gerald Gamrath
  • Ambros Gleixner
  • Robert Lion Gottwald
  • Gregor Hendel
  • Thorsten Koch
  • Marco E. Lübbecke
  • Stephen J. Maher
  • Matthias Miltenberger
  • Marc E. Pfetsch
  • Felipe Serrano
  • Dieter Weninger
  • Jakob Witzig
  • Benjamin Müller
  • Christian Puchert
  • Daniel Rehfeldt
  • Sebastian Schenker
  • Robert Schwarz
  • Yuji Shinano
  • Jonas T. Witt
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems Tags , ,

    The SCIP Optimization Suite is a powerful collection of optimization software that consists of the branch-cut-and-price framework and mixed-integer programming solver SCIP, the linear programming solver SoPlex, the modeling language Zimpl, the parallelization framework UG, and the generic branch-cut-and-price solver GCG. Additionally, it features the extensions SCIP-Jack for solving Steiner tree problems, PolySCIP for solving … Read more

    A polynomial algorithm for linear feasibility problems given by separation oracles

  • Sergei Chubanov
    • Categories Linear Programming Tags ,

    The algorithm proposed in this paper runs in a polynomial oracle time, i.e., in a number of arithmetic operations and calls to the separation oracle bounded by a polynomial in the number of variables and in the maximum binary size of an entry of the coefficient matrix. This algorithm is much simpler than traditional polynomial … Read more

    Permutations in the factorization of simplex bases

  • Ricardo Fukasawa
  • Laurent Poirrier
    • Categories Linear Programming Tags , ,

    The basis matrices corresponding to consecutive iterations of the simplex method only differ in a single column. This fact is commonly exploited in current LP solvers to avoid having to compute a new factorization of the basis at every iteration. Instead, a previous factorization is updated to reflect the modified column. Several methods are known … Read more

    A Successive LP Approach with C-VaR Type Constraints for IMRT Optimization

  • Shogo Kishimoto
  • Makoto Yamashita
    • Categories Applications - OR and Management Sciences, Linear Programming Tags , , ,

    Radiation therapy is considered to be one of important treatment protocols for cancers. Radiation therapy employs several beams of ionizing radiation to kill cancer tumors, but such irradiation also causes damage to normal tissues. Therefore, a treatment plan should satisfy dose-volume constraints (DVCs). Intensity-modulated radiotherapy treatment (IMRT) enables to control the beam intensities and gives … Read more

    Rescaling Algorithms for Linear Programming Part I: Conic feasibility

  • Daniel Dadush
  • Laszlo Vegh
  • Giacomo Zambelli
    • Categories Linear Programming Tags , ,

    We propose simple polynomial-time algorithms for two linear conic feasibility problems. For a matrix $A\in \R^{m\times n}$, the {\em kernel problem} requires a positive vector in the kernel of $A$, and the {\em image problem} requires a positive vector in the image of $A^\T$. Both algorithms iterate between simple first order steps and rescaling steps. … Read more