An easier method to find all corner points for a system of linear inequalities is to encode the basis using binary variables and then use the Cplex solution pool. Here we used a loop where we added binary cuts to prevent an earlier found basis to be revisited again. A complete description of the problem can be found in that post also. With the Cplex solution pool we just use one solve and we don’t have to bother with specifying the cuts. In addition we expect to see much of a performance improvement. So how does performance stack up with the loop?

As we can see the performance of the solution pool is superior compared to the loop implementation. Note: it will give the same solution (although in a different order).

##### Model

The complete model listing is here:

setk 'rows+columns' /1*5,r1*r5/j(k) 'columns' /1*5/i(k) 'rows' /r1*r5/bnd 'bounds' /lo,up/; variablesx(j) 'original decision variables'r(i) 'row levels'; equationse1,e2,e3,e4,e5 ; e1.. r('r1') =e= 5*x('1')+3*x('2')+3*x('3')+5*x('4'); e2.. r('r2') =e= x('2')+x('3'); e3.. r('r3') =e= x('1')+x('4'); e4.. r('r4') =e= 3*x('3')+5*x('4'); e5.. r('r5') =e= 5*x('1')+3*x('2'); table rowbound(i,bnd)lo up r1 3 5 r2 1 r3 1 r4 1 3 r5 2 ; r.lo(i) = rowbound(i,'lo'); r.up(i) = rowbound(i,'up'); x.lo(j) = 0; x.up(j) = 1; *-----------------------------------* basis encoding using* binary variables*-----------------------------------scalar m 'number of LP rows';m = card(i);set b 'basis status'/NBLO 'nonbasic at lower bound'NBUP 'nonbasic at upper bound'B 'basic'/; binary variablesbs(k,b) 'basis status of each row and column'; equationsonebs(k) 'only basis status is current'countb 'number of basics = m'vlower(j) 'variable is nb at lower'rlower(i) 'row is nb at lower'vupper(j) 'variable is nb at upper'rupper(i) 'row is nb at upper'; onebs(k).. sum(b, bs(k,b)) =e= 1;countb.. sum(k, bs(k,'B')) =e= m;vlower(j).. x(j) =l= x.lo(j) + (x.up(j)-x.lo(j))*(1-bs(j,'NBLO')); rlower(i).. r(i) =l= r.lo(i) + (r.up(i)-r.lo(i))*(1-bs(i,'NBLO')); vupper(j).. x(j) =g= x.up(j) - (x.up(j)-x.lo(j))*(1-bs(j,'NBUP')); rupper(i).. r(i) =g= r.up(i) - (r.up(i)-r.lo(i))*(1-bs(i,'NBUP')); *-----------------------------------* dummy objective*-----------------------------------equation edummy;variable dummy;edummy.. dummy =e= 0; *-----------------------------------* model statement*-----------------------------------model Model1 /all/;Model1.solvelink=%Solvelink.LoadLibrary%; Model1.solprint=%Solprint.Quiet%; option optcr=0;option mip=cplex;*-----------------------------------* solution pool solve*-----------------------------------$onecho > cplex.opt SolnPoolAGap = 0.0SolnPoolIntensity = 4PopulateLim = 10000SolnPoolPop = 2solnpoolmerge solutions.gdx$offecho model1.optfile=1; Solve Model1 using mip minimizing dummy;*-----------------------------------* read solution data*-----------------------------------setsp 'solution points' /soln_model1_p1*soln_model1_p1000/c(p) ; parametersv(p,k) 'collect values'bas(p,k,b) 'collect basis status'; execute_load "solutions.gdx",v=x,bas=bs,c=index;*-----------------------------------* remove duplicate values*-----------------------------------parametersw(k,p) 'unique values'found /0/ ; set u(p) 'subset of index';u(p) = no;loop(c,if(card(u)=0,u(c) = yes;w(k,c) = v(c,k); elsefound = 0; loop(u$(not found),found$( sum(k,abs(w(k,u)-v(c,k)))<1.0e-5) = 1;); if(not found,u(c) = yes;w(k,c) = v(c,k); ); ); ); display w; |