Benchmarks Library Transfer Line Balancing Problem
|
|
$offsymxref
$offsymlist
$include "problem.GMS"
$setglobal CPU_TIME_CPLEX 90
* CPU time limit for CPLEX
$setglobal ABS_ERROR_CPLEX 0
* Absolute error limit for CPLEX
scalar r temporary value;
*========================================== calculated sets and parameters
set QQ(j,q) "set of indices q of blocks to which operation j can be assigned";
loop((j,q)$((ord(q) ge a(j)) and (ord(q) le b(j))), QQ(j,q)=yes);
set KK(j,k) "set of indices k of stations to which operation j can be assigned";
loop((j,k)$((ord(k) ge AA(j)) and (ord(k) le BB(j))), KK(j,k)=yes);
set SS(k,q) the set of block indices q for the stations k;
loop(k,
loop(q$((ord(q) > (ord(k)-1)*n_0) and (ord(q) le ord(k)*n_0)),
SS(k,q)= yes;
);
);
parameters
IS_size(IS_name) sizes of station inclusion subsets e,
XS_size(XS_name) sizes of station exclusion subsets e,
XB_size(XB_name) sizes of block exclusion subsets e
;
set je_IS(j,IS_name) je is some fixed operation from the set IS_name;
set KK_IS(k,IS_name) the set of stations where all operations of IS_name can be placed;
KK_IS(k,IS_name)=yes;
loop(IS_name,
r=smin(IS(IS_name,j),ord(j));
* choose the operation with minimal index in IS_name as je_IS for IS_name
loop(j$(ord(j)=r), je_IS(j,IS_name)=yes);
IS_size(IS_name)=sum(IS(IS_name,j),1);
loop((j,k)$(IS(IS_name,j) and not(KK(j,k))),
KK_IS(k,IS_name)=no;
)
);
set je_XS(j,XS_name) je is some fixed operation from the set XS_name;
loop(XS_name,
r=smin(XS(XS_name,j),ord(j));
* choose the operation with minimal index in XS_name as je_XS for XS_name
loop(j$(ord(j)=r), je_XS(j,XS_name)=yes);
XS_size(XS_name)=sum(XS(XS_name,j),1);
);
set je_XB(j,XB_name) je is some fixed operation from the set XB_name;
loop(XB_name,
r=smin(XB(XB_name,j),ord(j));
* choose the operation with minimal index in XB_name as je_XB for XB_name
loop(j$(ord(j)=r), je_XB(j,XB_name)=yes);
XB_size(XB_name)=sum(XB(XB_name,j),1);
);
parameter
t(i,j) supplementary parameter to compute the block time t_b
;
loop((i,j),
t(i,j)=max(l(i),l(j))/min(s(i),s(j));
);
display t;
parameter
min_num_st "minimal number of stations (computed on the basis of AA)"
;
min_num_st=smax(j,AA(j));
scalar UseEq7Prime the flag to use (7') if not all s_j are identical;
UseEq7Prime=0;
loop(j$(ord(j)>1),
if(not(s(j)=s(j-1)),
UseEq7Prime=1;
);
);
*======================================== end of calculated sets and parameters
alias (q, qprime);
alias (j,je);
alias (q,qminus1);
alias (k,kminus1);
*======================================== Model
Binary Variables
Z(k) "indicates if the station k exists or not"
Y(q) "indicates if the block q exists or not"
;
Positive Variables
F(q) "the time of block q"
;
Binary Variables
X(j,q) "decision variable: equals to 1 iff operation j is assigned to block q"
Variables
cost "the overall cost, to be minimized"
;
Equations
obj
cone_block_op(j)
cpreced2(i,j)
cincusion_st(IS_name,k,je)
cexclusion_bl(XB_name,q)
cexclusion_st(XS_name,k)
clb_block_time1(i,q)
clb_block_time2(i,j,q)
cub_station_time(k)
cexist_block(q,j)
cexist_station(q,k)
ccont_block(q,k,qminus1)
ccont_station(k,kminus1)
cut_station(k)
cut_block(q)
;
* (1) Objective function (minimization)
obj..
cost =e= C_1 * sum(k, Z(k)) + C_2 * sum(q, Y(q));
* (2") Precedence constraint
cpreced2(i,j)$(Pred(i,j))..
sum(q$QQ(j,q), (ord(q)-1)*X(j,q)) =g= sum(q$QQ(i,q), (ord(q)-1)*X(i,q));
* (3) Each operation is assigned only to one block
cone_block_op(j)..
sum(q$(QQ(j,q)), X(j,q))=e= 1;
* (4) Inclusion constraint for stations
cincusion_st(IS_name,k,je)$(KK(je,k) and je_IS(je,IS_name))..
sum(j$(IS(IS_name,j) and not je_IS(j,IS_name)),
sum(q$(SS(k,q) and QQ(j,q)), X(j,q))
)
=e=(IS_size(IS_name)-1) * sum(q$SS(k,q), X(je,q));
* (5) Exclusion constraint for blocks
cexclusion_bl(XB_name,q)$
( sum(j$(XB(XB_name,j) and QQ(j,q)),1) = XB_size(XB_name) )..
sum(j$XB(XB_name,j), X(j,q)) =l= XB_size(XB_name)-1;
* (6) Exclusion constraint for stations
cexclusion_st(XS_name,k)$
( sum(j$(XS(XS_name,j) and KK(j,k)),1) = XS_size(XS_name) )..
sum(j$XS(XS_name,j),
sum(q$(SS(k,q) and QQ(j,q)),
X(j,q)
)
) =l= XS_size(XS_name)-1;
* (7) lower bound on block time
clb_block_time1(i,q)$(QQ(i,q))..
F(q) =g=t(i,i)* X(i,q);
* (7') lower bound on block time
clb_block_time2(i,j,q)$(ord(i)<ord(j) and QQ(i,q) and QQ(j,q))..
F(q) =g= t(i,j)*(X(i,q)+X(j,q)-1) - (1-UseEq7Prime)*T_0;
* (8) the station time does not exceed the cycle time T_0
cub_station_time(k)..
tau_s+sum(q$SS(k,q), F(q)) =l= T_0;
* (9) existence of block q
cexist_block(q,j)$QQ(j,q)..
Y(q) =g= X(j,q);
* (10) existence of station k
cexist_station(q,k)$(ord(q)=(ord(k)-1)*n_0+1)..
Z(k) =e= Y(q);
* (11) block q can be created only if block q-1 exists in station k
ccont_block(q,k,qminus1)$(SS(k,q) and not(ord(q)=(ord(k)-1)*n_0+1) and ord(qminus1)=ord(q)-1)..
Y(qminus1) - Y(q) =g= 0;
* (12) staion k can be created only if station k-1 exists
ccont_station(k,kminus1)$(ord(k)>1 and ord(kminus1)=ord(k)-1)..
Z(kminus1) - Z(k)=g= 0;
* Additional constraint that serves as a cut
cut_station(k)..
Z(k) =l= sum(q$SS(k,q), Y(q));
* Additional constraint that serves as a cut
cut_block(q)..
Y(q) =l= sum(j$QQ(j,q), X(j,q));
*Bounds on variables
Y.up(q)= 1;
Z.up(k)= 1;
Y.lo(q)= 0;
Z.lo(k)= 0;
F.up(q)=T_0-tau_s-tau_b;
* Eliminate/fix unnecesary binary variables
loop((j,q)$(not(QQ(j,q))), X.up(j,q)=0);
loop((j,k)$(not(KK(j,k))),
loop(q$SS(k,q),X.up(j,q)=0);
);
loop(k$(ord(k) le min_num_st),
Z.fx(k)=1;
loop(q$(ord(q) = (ord(k)-1)*n_0+1), Y.fx(q)=1);
);
Model MIP2
/
obj
cone_block_op
cpreced2
cincusion_st
cexclusion_bl
cexclusion_st
clb_block_time1
clb_block_time2
cub_station_time
cexist_block
cexist_station
ccont_block
ccont_station
cut_station
cut_block
/;
MIP2.NodLim = 1e09;
MIP2.holdfixed = 1;
option mip = CPLEX;
option optcr = 0.0;
option optca = %ABS_ERROR_CPLEX%;
option reslim = %CPU_TIME_CPLEX%;
option iterlim = 1e08;
option solprint = off;
file series_report / results.csv /;
series_report.ap=1;
put series_report;
put " ";
Solve MIP2 using MIP minimizing cost;
put series_report;
put "f best found , CPLEX CPU time (sec), CPU time given (sec) , modelstat flag;
put solvestat flag, variables, LB, Use (7')? " /;
if(not(execerror) and (MIP2.modelstat=1 or MIP2.modelstat=8 ),
put cost.l, " , ", MIP2.resusd, " , ", %CPU_TIME_CPLEX% , " , ",MIP2.modelstat;
put " , ", MIP2.solvestat , " , ", MIP2.numvar , " , ", MIP2.objest, ", ",UseEq7Prime;
else
put "NOT FOUND", " , ", " , ", %CPU_TIME_CPLEX% , " , ", MIP2.modelstat;
put " , ", MIP2.solvestat , " , ", MIP2.numvar, ", ", " , ", UseEq7Prime;
);
display X.l;