approximate linear programming

Network-based Approximate Linear Programming for Discrete Optimization

  • Andre Augusto Cire
  • Selvaprabu Nadarajah
    • Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming, Linear Programming Tags , ,

    We develop a new class of approximate linear programs (ALPs) that project the high-dimensional value function of dynamic programs onto a class of basis functions, each defined as a network that represents aggregrations over the state space. The resulting ALP is a minimum-cost flow problem over an extended variable space that synchronizes flows across multiple … Read more

    Revisiting Approximate Linear Programming Using a Saddle Point Approach

  • Qihang Lin
  • Selvaprabu Nadarajah
  • Negar Soheili
    • Categories Dynamic Programming, Semi-infinite Programming, Stochastic Programming Tags , , , , ,

    Approximate linear programs (ALPs) are well-known models for computing value function approximations (VFAs) of intractable Markov decision processes (MDPs) arising in applications. VFAs from ALPs have desirable theoretical properties, define an operating policy, and provide a lower bound on the optimal policy cost, which can be used to assess the suboptimality of heuristic policies. However, … Read more