approximation scheme

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

    ACCPM with a nonlinear constraint and an active set strategy to solve nonlinear multicommodity flow problems

  • Frédéric Babonneau
  • Jean-Philippe Vial
    • Categories Network Optimization, Nonsmooth Optimization Tags , ,

    This paper proposes an implementation of a constrained analytic center cutting plane method to solve nonlinear multicommodity flow problems. The new approach exploits the property that the objective of the Lagrangian dual problem has a smooth component with second order derivatives readily available in closed form. The cutting planes issued from the nonsmooth component and … Read more