In this chapter the following model is considered: We assume that an instance I of a computationally hard optimization problem has been solved and that we know the optimum solution of such an instance. Then a new instance I' is proposed, obtained by means of a slight perturbation of instance I. How can we exploit the knowledge we have on the solution of instance I to compute an (approximate) solution of instance I' in an efficient way? This computation model is called reoptimization and is of practical interest in various circumstances. In this chapter we first discuss what kind of performance we can expect for specific classes of problems and then we present some classical optimization problems (i.e. Max Knapsack, Min Steiner Tree, Scheduling) in which this approach has been fruitfully applied. Subsequently, we address vehicle routing problems and we show how the reoptimization approach can be used to obtain good approximate solutions in an efficient way for some of these problems.

Ausiello, G., Bonifaci, V., Escoffier, B. (2011). Complexity and approximation in reoptimization. In S. Barry Cooper, Sorbi A. (a cura di), Computability in Context: Computation and Logic in the Real World (pp. 101-129). Londra : Imperial College Press [10.1142/9781848162778_0004].

Complexity and approximation in reoptimization

Bonifaci V.;
2011

Abstract

In this chapter the following model is considered: We assume that an instance I of a computationally hard optimization problem has been solved and that we know the optimum solution of such an instance. Then a new instance I' is proposed, obtained by means of a slight perturbation of instance I. How can we exploit the knowledge we have on the solution of instance I to compute an (approximate) solution of instance I' in an efficient way? This computation model is called reoptimization and is of practical interest in various circumstances. In this chapter we first discuss what kind of performance we can expect for specific classes of problems and then we present some classical optimization problems (i.e. Max Knapsack, Min Steiner Tree, Scheduling) in which this approach has been fruitfully applied. Subsequently, we address vehicle routing problems and we show how the reoptimization approach can be used to obtain good approximate solutions in an efficient way for some of these problems.
978-1-84816-245-7
Ausiello, G., Bonifaci, V., Escoffier, B. (2011). Complexity and approximation in reoptimization. In S. Barry Cooper, Sorbi A. (a cura di), Computability in Context: Computation and Logic in the Real World (pp. 101-129). Londra : Imperial College Press [10.1142/9781848162778_0004].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11590/381651
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 38
  • ???jsp.display-item.citation.isi??? ND
social impact