Description

Francisco Ortega, Laurence Wolsey
A branch-and-cut algorithm for the single-commodity, uncapacitated,
fixed-charge network flow problem.
Networks 41 (2003), no. 3, 143--158.

https://dial.uclouvain.be/pr/boreal/en/object/boreal%3A4138

Michael Bussieck, Hua Ni, Alexey Koptsevich
Technical Note: Solving the Steiner Tree Problem with GAMS Branch-and-Cut Facility.
Technical report, GAMS Development Corp. 2003.

Keywords: mixed integer linear programming, minimum cost flow problem,
          branch and cut and heuristic facility, network optimization,
          fixed charge

Large Model of Type : MIP

Category : GAMS Model library

Main file : bchfcnet.gms   includes :  bchdicut.inc  berlin2.inc

$title Fixed Cost Network Flow Problem with Cuts using BCH Facility (BCHFCNET,SEQ=287)

$onText
Francisco Ortega, Laurence Wolsey
A branch-and-cut algorithm for the single-commodity, uncapacitated,
fixed-charge network flow problem.
Networks 41 (2003), no. 3, 143--158.

https://dial.uclouvain.be/pr/boreal/en/object/boreal%3A4138

Michael Bussieck, Hua Ni, Alexey Koptsevich
Technical Note: Solving the Steiner Tree Problem with GAMS Branch-and-Cut Facility.
Technical report, GAMS Development Corp. 2003.

Keywords: mixed integer linear programming, minimum cost flow problem,
          branch and cut and heuristic facility, network optimization,
          fixed charge
$offText

$eolCom //

Set
   n          'nodes'
   s          'sub arcs index'
   arc(n,n,s) 'arcs';

Alias (n,nn,m), (s,ss);

Parameter
   demand(n)    'node demand'
   fcost(n,n,s) 'fixed cost'
   vcost(n,n,s) 'variable cost'
   xupp(n,n,s)  'upper bound on flow'
   yupp(n,n,s)  'upper bound on build';

Scalar
   u       'sum of demand'
   usetree 'whether the additional equation is present' / 0 /
   usett1  'same'                                       / 0 /
   usett2  'same'                                       / 0 /;

$include berlin2.inc

arc(m,n,s)$(fcost(m,n,s) or vcost(m,n,s) or xupp(m,n,s) or yupp(m,n,s)) = yes;

* Export data for use in the cut generator
execute_unload 'net.gdx', nn ss arc demand fcost vcost u usetree usett1 usett2 xupp yupp;

Variable
   cost
   x(n,n,s) 'flow over the arc'
   y(n,n,s) 'usage of the arc';

Positive Variable x;
Binary   Variable y;

Equation
   obj       'objective'
   tt2(n)    'no flow through non-demanding nodes'
   bf(n,n,s) 'binary forcing constraints'
   bal(n)    'flow conservation constraints'
   tree(n)   'outflow via one arc only'
   tt1(n)    'demanding nodes are fed via one arc only';

obj..     sum(arc, vcost(arc)*x(arc) + fcost(arc)*y(arc)) =e= cost;

bal(n)..  sum(arc(m,n,s), x(m,n,s)) - sum(arc(n,m,s), x(n,m,s)) =e= demand(n);

bf(arc).. x(arc) =l= xupp(arc)*y(arc);

tree(n)$usetree.. sum(arc(n,m,s), y(n,m,s)) =l= 1;

tt1(n)$(usett1 and demand(n) > 0).. sum((m,s), y(m,n,s)) =e= 1;

tt2(n)$(usett2 and demand(n) = 0).. sum((m,s), y(m,n,s)) =l= 1;

Model master / all /;

$ifThenI %system.mip% == cplex $set solver cplex
$else
$abort 'BCH Facility not available for MIP solver %system.mip%.'
$endIf

master.optFile = 1;
$onEcho > %solver%.opt
mipInterval 1
userCutCall bchdicut.inc minlp baron optCr 0.0 optCa 0.5 resLim 10 optFile = 1 lo = 2 --cplex = 1
userCutFirst 100
$offEcho

$onEcho > baron.opt
iSolTol 0.99
numSol 20
gdxOut bchdicut
firstFeas 1
$offEcho

xupp(arc) = min(u,xupp(arc));
x.up(arc) = xupp(arc);
y.up(arc)$yupp(arc) = yupp(arc);

master.optCr = 0;
solve master minimizing cost using mip;