xpress07.gms : XPRESS test suite - solution enumerator example

Description

Test the XPRESS solution enumerator.  This test model is interesting
because it can be solved as two independent models, it has some
dominated solutions removed by presolve, and it benefits from orbital
branching.  So the XPRESS presolve wants to do some work, but we turn
this off by default when the solution enumerator is used.

Here we test that the XPRESS solution enumerator finds all 16
solutions when run on defaults.  To suppress this test, run with
--SKIP_XPRESS=1.

A second test adds cuts to the model to enumerate all solutions.

Contributor: Steve Dirkse, Jul 2019


Small Model of Type : MIP


Category : GAMS Test library


Main file : xpress07.gms

$title XPRESS test suite - solution enumerator example (XPRESS07,SEQ=802)

$onText
Test the XPRESS solution enumerator.  This test model is interesting
because it can be solved as two independent models, it has some
dominated solutions removed by presolve, and it benefits from orbital
branching.  So the XPRESS presolve wants to do some work, but we turn
this off by default when the solution enumerator is used.

Here we test that the XPRESS solution enumerator finds all 16
solutions when run on defaults.  To suppress this test, run with
--SKIP_XPRESS=1.

A second test adds cuts to the model to enumerate all solutions.

Contributor: Steve Dirkse, Jul 2019
$offText

$onDollar
$if not set SKIP_XPRESS $set SKIP_XPRESS 0

sets
  i / 1*2 /
  j / 1*4 /
  ;
table d(i,j)  'distance between i and j'
         1       2       3       4
1        10      12      0       0
2        0       0       8       10  ;

variable         z;
binary variable  y(i,j);

equations
  oDef      'objective definition'
  oneJperI  'only one j can be selected for each i'
  ;

oDef..          sum{(i,j), d(i,j)*y(i,j)} =e= z;
oneJperI(i) ..  sum{j, y(i,j)} =e= 1;

model mBasic 'basic model with no cuts' / oDef, oneJperI /;

scalar nSols;

$ifThen not "%SKIP_XPRESS%" == "1"
option mip = xpress;
mBasic.optfile = 150;
$onEcho > xpress.150
solnpool           allSols.gdx
solnpoolDupPolicy  0
solnpoolPop        2
solnpoolPrefix     xpxsol
$offEcho

execute 'rm -f allSols.gdx xpxsol_mBasic_p*.gdx'
solve mBasic maximize z using mip;

set solFiles / file1 * file20 /;
set index(solFiles) 'index of solutions in XPRESS pool';
scalar nSols;
execute_load 'allSols', index;
nSols = card(index);
abort$[nSols <> 16] 'XPRESS solution pool should contain 16 solutions', nSols;

$endIf

$onText
-------------------------------------------------------------------------
Now add cuts to the basic model, so we can iteratively find solutions,
cut them off, and find other solutions, until there are no more
solutions left to find.
-------------------------------------------------------------------------
$offText

sets
  sols  'all possible previous solutions' / s1 * s500 /
  s(sols) 'solutions found thus far' / system.empty /
  prevSol(sols,i,j) 'on iff y(i,j) was 1' / system.empty . system.empty . system.empty /

equation cuts(sols)  'cut off previously found solutions';
cuts(s)..  sum{prevSol(s,i,j), (1-y(i,j))}
         + sum{(i,j)$[not prevSol(s,i,j)], y(i,j)} =g= 1;

model mCuts / mBasic, cuts /;

* since we want to enumerate all sols, we can ignore the objective if we like
mCuts.optca = 1000;
parameter report(sols, *);
loop {sols,
  solve mCuts using mip maximize z;
  break$[(mCuts.modelStat <> %modelStat.optimal%) and
         (mCuts.modelStat <> %modelStat.integerSolution%)];

* record the solution so it will not recur
  report(sols,'time') = mCuts.resUsd;
  report(sols,'obj') = mCuts.objVal;
  report(sols,'modelStat') = mCuts.modelStat;
  report(sols,'solveStat') = mCuts.solveStat;
  prevSol(sols,i,j) = round(y.L(i,j));
  s(sols) = yes;
};

display report;
nSols = card(s);
abort$[nSols <> 16] 'cut set should contain 16 solutions', nSols;