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-01-01
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
