icut.gms : Integer Cut Example

Description

```Sometimes it may be required to exclude certain integer solutions.
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.
```

Small Model of Type : MIP

Category : GAMS Model library

Main file : icut.gms

``````\$title Integer Cut Example (ICUT,SEQ=160)

\$onText
Sometimes it may be required to exclude certain integer solutions.
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.

Keywords: mixed integer linear programming, GAMS formulation and language examples,
integer cuts, mathematics
\$offText

\$eolCom //

Set
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';

Variable
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;

Equation
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';

Parameter
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;  // initial 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
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 using 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;
``````
GAMS Development Corp.
GAMS Software GmbH

General Information and Sales
U.S. (+1) 202 342-0180
Europe: (+49) 221 949-9170