We study 0-1 reformulations of the Network Loading problem, a capacitated network design problem which is usually modeled with general integer variables to represent design decisions on the number of facilities to install on each arc of the network. The reformulations are based on the multiple choice model, a generic approach to represent piecewise linear costs using 0-1 variables. This model is improved by the addition of extended linking inequalities, derived from variable disaggregation techniques. We show that these extended linking inequalities for the 0-1 model are equivalent to the residual capacity inequalities, a class of valid inequalities derived for the model with general integer variables. This result yields three strategies to compute the same lower bound on the optimal value of the problem: 1) A Dantzig-Wolfe (DW) approach applied to the model with general integer variables; 2) A cutting-plane algorithm based on the residual capacity inequalities; 3) A Structured DW method that solves the 0-1 reformulation with extended linking inequalities by variables and constraints generation.

0-1 Reformulations of the Network Loading Problem

FRANGIONI, ANTONIO;
2005

Abstract

We study 0-1 reformulations of the Network Loading problem, a capacitated network design problem which is usually modeled with general integer variables to represent design decisions on the number of facilities to install on each arc of the network. The reformulations are based on the multiple choice model, a generic approach to represent piecewise linear costs using 0-1 variables. This model is improved by the addition of extended linking inequalities, derived from variable disaggregation techniques. We show that these extended linking inequalities for the 0-1 model are equivalent to the residual capacity inequalities, a class of valid inequalities derived for the model with general integer variables. This result yields three strategies to compute the same lower bound on the optimal value of the problem: 1) A Dantzig-Wolfe (DW) approach applied to the model with general integer variables; 2) A cutting-plane algorithm based on the residual capacity inequalities; 3) A Structured DW method that solves the 0-1 reformulation with extended linking inequalities by variables and constraints generation.
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/11568/92361
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact