Optimization Online


K-Adaptability in stochastic optimization

Enrico Malaguti(enrico.malaguti***at***unibo.it)
Michele Monaci(michele.monaci***at***unibo.it)
Jonas Pruente(jonas.pruente***at***math.tu-dortmund.de)

Abstract: We consider stochastic problems in which both the objective function and the feasible set are affected by uncertainty. We address these problems using a K-adaptability approach, in which K solutions for the underlying problem are computed before the uncertainty dissolves and afterwards the best of them can be chosen for the realised scenario. This paradigm can be used for any underlying optimization problem. We analyze the complexity of the resulting problem from a theoretical viewpoint by showing that deciding if a feasible solution exists, is NP-hard for discrete probability distributions and that evaluating the objective function is # P-hard for continuous probability distributions. Besides that, we prove that an approximation factor for the underlying problem can be carried over to our problem. Finally, we present exact solution approaches including a branch-and-price algorithm. An extensive computational analysis compares the performances of the proposed algorithms on a large set of randomly generated instances.

Keywords: Stochastic programming ; K-adaptability ; Exact algorithms ; Branch-and-price ; Computational experiments

Category 1: Global Optimization (Stochastic Approaches )

Category 2: Stochastic Programming

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 04/21/2020
Entry Accepted: 04/21/2020
Entry Last Modified: 04/21/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society