icut.gms : Integer Cut Example

**Description**

Sometimes it may be required to exclude certain integer solutions. Additional constraints, called cuts, can be added to exclude such solutions. To exclude the k'th integer solution we can write: cut(k).. sum(i, abs(x(i)-xsol(i,k)) =g= 1; The absolute function has to be simulated using 0/1 variables and some additional constraints. When the solution to be excluded is at lower or upper bound, we do not need additional 0/1 variables. In this example we simply show how to enumerate all possible combinations of four integer variables.

**Reference**

- GAMS Development Corporation, Formulation and Language Example.

**Small Model of Type :** MIP

**Category :** GAMS Model library

**Main file :** icut.gms

$title Integer Cut Example (ICUT,SEQ=160) $eolcom ! $Ontext Sometimes it may be required to exclude certain integer solutions. Additional constraints, called cuts, can be added to exclude such solutions. To exclude the k'th integer solution we can write: cut(k).. sum(i, abs(x(i)-xsol(i,k)) =g= 1; The absolute function has to be simulated using 0/1 variables and some additional constraints. When the solution to be excluded is at lower or upper bound, we do not need additional 0/1 variables. In this example we simply show how to enumerate all possible combinations of four integer variables. GAMS Development Corporation, Formulation and Language Example. $Offtext sets i index on integer variable / 1 * 4 / ie(i) variables fixed in(i) not fixed il(i) solutions at lower bound iu(i) solutions at upper bound ib(i) solution between bounds kk cut identification set / 1 * 100 / k(kk) dynamic subset of k bb(kk,i) cut memory bl(kk,i) cut memory bu(kk,i) cut memory variables x(i) test variable z some objective variable b(kk,i) flip-flop for in between solutions u(kk,i) changes up l(kk,i) changes down integer variable x; binary variable b; positive variable u,l; equations cut(kk) main cut equations cutu(kk,i) upper bound limit for inbetween integers cutl(kk,i) lower bound limit for inbetween integers cutul(kk,i) definition of positive and negative deviations obj obj definition; parameters cutrhs(kk) cut RHS value cutlx(kk,i) cut lower bound cutux(kk,i) cut upper bound cuts(kk,i) cut solution value report(kk,*) cut report variable whatnext loop control variable; * pick an objective function which will order the solutions obj.. z =e= sum(i, power(10,card(i)-ord(i))*x(i)); cut(k).. - sum(bu(k,i), x(i)) + sum(bl(k,i),x(i)) + sum(bb(k,i), l(bb) + u(bb)) =g= cutrhs(k); cutu(bb(k,i)).. u(bb) =l= cutux(bb)*b(bb); cutl(bb(k,i)).. l(bb) =l= cutlx(bb)*(1-b(bb)); cutul(bb(k,i)).. x(i) =e= cuts(bb) + u(bb) - l(bb); model enum / all /; * get an initial solution and set bounds x.lo(i) = 2; x.up(i) = 4; x.fx('2') = 3; ! fix one variable x.up('4') = 3; ! only two values x.l(i) = x.lo(i); k(kk) = no; ! make cut set empty ie(i) = yes$(x.lo(i)=x.up(i)); ! find fixed variables in(i) = yes - ie(i); ! find free variables whatnext = 1; ! initial loop control enum.resusd = 0; ! inital CPU used enum.reslim = 60; ! dont spend more than 60 seconds on on problem * We enumerate all solutions so we are happy with the first solution * the solver finds. enum.optcr = 0; enum.optca = 1e06; loop(kk$whatnext, il(in) = yes$(x.l(in)=x.lo(in)); ! find variables at lower iu(in) = yes$(x.l(in)=x.up(in)); ! find variables at upper ib(in) = yes - ie(in) - iu(in) - il(in); ! find variables between k(kk) = yes; ! add bl(kk,il) = yes; ! cut bu(kk,iu) = yes; ! information bb(kk,ib) = yes; ! as needed cutux(kk,ib) = x.up(ib) - x.l(ib); cutlx(kk,ib) = x.l(ib) - x.lo(ib); cuts(kk,ib) = x.l(ib); cutrhs(kk) = 1 + sum(il, x.l(il)) - sum(iu, x.l(iu)); report(kk,i) = x.l(i); ! save previous solution report(kk,'binaries') = card(bb); ! remember binaries report(kk,'CPU time') = enum.resusd; ! remember time solve enum min z us mip; enum.limcol = 0; ! turn off enum.limrow = 0; ! all enum.solprint = %solprint.Quiet%; ! output whatnext = enum.modelstat=%modelstat.Optimal% or enum.modelstat=%modelstat.IntegerSolution% ); display enum.solvestat, enum.modelstat, report;