My Project  UNKNOWN_GIT_VERSION
Public Member Functions | Data Fields | Private Member Functions | Private Attributes
simplex Class Reference

Linear Programming / Linear Optimization using Simplex - Algorithm. More...

#include <mpr_numeric.h>

Public Member Functions

 simplex (int rows, int cols)
 #rows should be >= m+2, #cols >= n+1 More...
 
 ~simplex ()
 
BOOLEAN mapFromMatrix (matrix m)
 
matrix mapToMatrix (matrix m)
 
intvecposvToIV ()
 
intveczrovToIV ()
 
void compute ()
 

Data Fields

int m
 
int n
 
int m1
 
int m2
 
int m3
 
int icase
 
int * izrov
 
int * iposv
 
mprfloat ** LiPM
 

Private Member Functions

 simplex (const simplex &)
 
void simp1 (mprfloat **a, int mm, int ll[], int nll, int iabf, int *kp, mprfloat *bmax)
 
void simp2 (mprfloat **a, int n, int l2[], int nl2, int *ip, int kp, mprfloat *q1)
 
void simp3 (mprfloat **a, int i1, int k1, int ip, int kp)
 

Private Attributes

int LiPM_cols
 
int LiPM_rows
 

Detailed Description

Linear Programming / Linear Optimization using Simplex - Algorithm.

On output, the tableau LiPM is indexed by two arrays of integers. ipsov[j] contains, for j=1..m, the number i whose original variable is now represented by row j+1 of LiPM. (left-handed vars in solution) (first row is the one with the objective function) izrov[j] contains, for j=1..n, the number i whose original variable x_i is now a right-handed variable, rep. by column j+1 of LiPM. These vars are all zero in the solution. The meaning of n<i<n+m1+m2 is the same as above.

Definition at line 194 of file mpr_numeric.h.

Constructor & Destructor Documentation

◆ simplex() [1/2]

simplex::simplex ( int  rows,
int  cols 
)

#rows should be >= m+2, #cols >= n+1

Definition at line 976 of file mpr_numeric.cc.

977  : LiPM_cols(cols), LiPM_rows(rows)
978 {
979  int i;
980 
983 
984  LiPM = (mprfloat **)omAlloc( LiPM_rows * sizeof(mprfloat *) ); // LP matrix
985  for( i= 0; i < LiPM_rows; i++ )
986  {
987  // Mem must be allocated aligned, also for type double!
988  LiPM[i] = (mprfloat *)omAlloc0Aligned( LiPM_cols * sizeof(mprfloat) );
989  }
990 
991  iposv = (int *)omAlloc0( 2*LiPM_rows*sizeof(int) );
992  izrov = (int *)omAlloc0( 2*LiPM_rows*sizeof(int) );
993 
994  m=n=m1=m2=m3=icase=0;
995 
996 #ifdef mprDEBUG_ALL
997  Print("LiPM size: %d, %d\n",LiPM_rows,LiPM_cols);
998 #endif
999 }

◆ ~simplex()

simplex::~simplex ( )

Definition at line 1001 of file mpr_numeric.cc.

1002 {
1003  // clean up
1004  int i;
1005  for( i= 0; i < LiPM_rows; i++ )
1006  {
1007  omFreeSize( (void *) LiPM[i], LiPM_cols * sizeof(mprfloat) );
1008  }
1009  omFreeSize( (void *) LiPM, LiPM_rows * sizeof(mprfloat *) );
1010 
1011  omFreeSize( (void *) iposv, 2*LiPM_rows*sizeof(int) );
1012  omFreeSize( (void *) izrov, 2*LiPM_rows*sizeof(int) );
1013 }

◆ simplex() [2/2]

simplex::simplex ( const simplex )
private

Member Function Documentation

◆ compute()

void simplex::compute ( )

Definition at line 1099 of file mpr_numeric.cc.

1100 {
1101  int i,ip,ir,is,k,kh,kp,m12,nl1,nl2;
1102  int *l1,*l2,*l3;
1103  mprfloat q1, bmax;
1104 
1105  if ( m != (m1+m2+m3) )
1106  {
1107  // error: bad input
1108  error(WarnS("simplex::compute: Bad input constraint counts!");)
1109  icase=-2;
1110  return;
1111  }
1112 
1113  l1= (int *) omAlloc0( (n+1) * sizeof(int) );
1114  l2= (int *) omAlloc0( (m+1) * sizeof(int) );
1115  l3= (int *) omAlloc0( (m+1) * sizeof(int) );
1116 
1117  nl1= n;
1118  for ( k=1; k<=n; k++ ) l1[k]=izrov[k]=k;
1119  nl2=m;
1120  for ( i=1; i<=m; i++ )
1121  {
1122  if ( LiPM[i+1][1] < 0.0 )
1123  {
1124  // error: bad input
1125  error(WarnS("simplex::compute: Bad input tableau!");)
1126  error(Warn("simplex::compute: in input Matrix row %d, column 1, value %f",i+1,LiPM[i+1][1]);)
1127  icase=-2;
1128  // free mem l1,l2,l3;
1129  omFreeSize( (void *) l3, (m+1) * sizeof(int) );
1130  omFreeSize( (void *) l2, (m+1) * sizeof(int) );
1131  omFreeSize( (void *) l1, (n+1) * sizeof(int) );
1132  return;
1133  }
1134  l2[i]= i;
1135  iposv[i]= n+i;
1136  }
1137  for ( i=1; i<=m2; i++) l3[i]= 1;
1138  ir= 0;
1139  if (m2+m3)
1140  {
1141  ir=1;
1142  for ( k=1; k <= (n+1); k++ )
1143  {
1144  q1=0.0;
1145  for ( i=m1+1; i <= m; i++ ) q1+= LiPM[i+1][k];
1146  LiPM[m+2][k]= -q1;
1147  }
1148 
1149  do
1150  {
1151  simp1(LiPM,m+1,l1,nl1,0,&kp,&bmax);
1152  if ( bmax <= SIMPLEX_EPS && LiPM[m+2][1] < -SIMPLEX_EPS )
1153  {
1154  icase= -1; // no solution found
1155  // free mem l1,l2,l3;
1156  omFreeSize( (void *) l3, (m+1) * sizeof(int) );
1157  omFreeSize( (void *) l2, (m+1) * sizeof(int) );
1158  omFreeSize( (void *) l1, (n+1) * sizeof(int) );
1159  return;
1160  }
1161  else if ( bmax <= SIMPLEX_EPS && LiPM[m+2][1] <= SIMPLEX_EPS )
1162  {
1163  m12= m1+m2+1;
1164  if ( m12 <= m )
1165  {
1166  for ( ip= m12; ip <= m; ip++ )
1167  {
1168  if ( iposv[ip] == (ip+n) )
1169  {
1170  simp1(LiPM,ip,l1,nl1,1,&kp,&bmax);
1171  if ( fabs(bmax) >= SIMPLEX_EPS)
1172  goto one;
1173  }
1174  }
1175  }
1176  ir= 0;
1177  --m12;
1178  if ( m1+1 <= m12 )
1179  for ( i=m1+1; i <= m12; i++ )
1180  if ( l3[i-m1] == 1 )
1181  for ( k=1; k <= n+1; k++ )
1182  LiPM[i+1][k] = -(LiPM[i+1][k]);
1183  break;
1184  }
1185  //#if DEBUG
1186  //print_bmat( a, m+2, n+3);
1187  //#endif
1188  simp2(LiPM,n,l2,nl2,&ip,kp,&q1);
1189  if ( ip == 0 )
1190  {
1191  icase = -1; // no solution found
1192  // free mem l1,l2,l3;
1193  omFreeSize( (void *) l3, (m+1) * sizeof(int) );
1194  omFreeSize( (void *) l2, (m+1) * sizeof(int) );
1195  omFreeSize( (void *) l1, (n+1) * sizeof(int) );
1196  return;
1197  }
1198  one: simp3(LiPM,m+1,n,ip,kp);
1199  // #if DEBUG
1200  // print_bmat(a,m+2,n+3);
1201  // #endif
1202  if ( iposv[ip] >= (n+m1+m2+1))
1203  {
1204  for ( k= 1; k <= nl1; k++ )
1205  if ( l1[k] == kp ) break;
1206  --nl1;
1207  for ( is=k; is <= nl1; is++ ) l1[is]= l1[is+1];
1208  ++(LiPM[m+2][kp+1]);
1209  for ( i= 1; i <= m+2; i++ ) LiPM[i][kp+1] = -(LiPM[i][kp+1]);
1210  }
1211  else
1212  {
1213  if ( iposv[ip] >= (n+m1+1) )
1214  {
1215  kh= iposv[ip]-m1-n;
1216  if ( l3[kh] )
1217  {
1218  l3[kh]= 0;
1219  ++(LiPM[m+2][kp+1]);
1220  for ( i=1; i<= m+2; i++ )
1221  LiPM[i][kp+1] = -(LiPM[i][kp+1]);
1222  }
1223  }
1224  }
1225  is= izrov[kp];
1226  izrov[kp]= iposv[ip];
1227  iposv[ip]= is;
1228  } while (ir);
1229  }
1230  /* end of phase 1, have feasible sol, now optimize it */
1231  loop
1232  {
1233  // #if DEBUG
1234  // print_bmat( a, m+1, n+5);
1235  // #endif
1236  simp1(LiPM,0,l1,nl1,0,&kp,&bmax);
1237  if (bmax <= /*SIMPLEX_EPS*/0.0)
1238  {
1239  icase=0; // finite solution found
1240  // free mem l1,l2,l3
1241  omFreeSize( (void *) l3, (m+1) * sizeof(int) );
1242  omFreeSize( (void *) l2, (m+1) * sizeof(int) );
1243  omFreeSize( (void *) l1, (n+1) * sizeof(int) );
1244  return;
1245  }
1246  simp2(LiPM,n,l2,nl2,&ip,kp,&q1);
1247  if (ip == 0)
1248  {
1249  //printf("Unbounded:");
1250  // #if DEBUG
1251  // print_bmat( a, m+1, n+1);
1252  // #endif
1253  icase=1; /* unbounded */
1254  // free mem
1255  omFreeSize( (void *) l3, (m+1) * sizeof(int) );
1256  omFreeSize( (void *) l2, (m+1) * sizeof(int) );
1257  omFreeSize( (void *) l1, (n+1) * sizeof(int) );
1258  return;
1259  }
1260  simp3(LiPM,m,n,ip,kp);
1261  is= izrov[kp];
1262  izrov[kp]= iposv[ip];
1263  iposv[ip]= is;
1264  }/*for ;;*/
1265 }

◆ mapFromMatrix()

BOOLEAN simplex::mapFromMatrix ( matrix  m)

Definition at line 1015 of file mpr_numeric.cc.

1016 {
1017  int i,j;
1018 // if ( MATROWS( m ) > LiPM_rows || MATCOLS( m ) > LiPM_cols ) {
1019 // WarnS("");
1020 // return FALSE;
1021 // }
1022 
1023  number coef;
1024  for ( i= 1; i <= MATROWS( mm ); i++ )
1025  {
1026  for ( j= 1; j <= MATCOLS( mm ); j++ )
1027  {
1028  if ( MATELEM(mm,i,j) != NULL )
1029  {
1030  coef= pGetCoeff( MATELEM(mm,i,j) );
1031  if ( coef != NULL && !nIsZero(coef) )
1032  LiPM[i][j]= (double)(*(gmp_float*)coef);
1033  //#ifdef mpr_DEBUG_PROT
1034  //Print("%f ",LiPM[i][j]);
1035  //#endif
1036  }
1037  }
1038  // PrintLn();
1039  }
1040 
1041  return TRUE;
1042 }

◆ mapToMatrix()

matrix simplex::mapToMatrix ( matrix  m)

Definition at line 1044 of file mpr_numeric.cc.

1045 {
1046  int i,j;
1047 // if ( MATROWS( mm ) < LiPM_rows-3 || MATCOLS( m ) < LiPM_cols-2 ) {
1048 // WarnS("");
1049 // return NULL;
1050 // }
1051 
1052 //Print(" %d x %d\n",MATROWS( mm ),MATCOLS( mm ));
1053 
1054  number coef;
1055  gmp_float * bla;
1056  for ( i= 1; i <= MATROWS( mm ); i++ )
1057  {
1058  for ( j= 1; j <= MATCOLS( mm ); j++ )
1059  {
1060  pDelete( &(MATELEM(mm,i,j)) );
1061  MATELEM(mm,i,j)= NULL;
1062 //Print(" %3.0f ",LiPM[i][j]);
1063  if ( LiPM[i][j] != 0.0 )
1064  {
1065  bla= new gmp_float(LiPM[i][j]);
1066  coef= (number)bla;
1067  MATELEM(mm,i,j)= pOne();
1068  pSetCoeff( MATELEM(mm,i,j), coef );
1069  }
1070  }
1071 //PrintLn();
1072  }
1073 
1074  return mm;
1075 }

◆ posvToIV()

intvec * simplex::posvToIV ( )

Definition at line 1077 of file mpr_numeric.cc.

1078 {
1079  int i;
1080  intvec * iv = new intvec( m );
1081  for ( i= 1; i <= m; i++ )
1082  {
1083  IMATELEM(*iv,i,1)= iposv[i];
1084  }
1085  return iv;
1086 }

◆ simp1()

void simplex::simp1 ( mprfloat **  a,
int  mm,
int  ll[],
int  nll,
int  iabf,
int *  kp,
mprfloat bmax 
)
private

Definition at line 1267 of file mpr_numeric.cc.

1268 {
1269  int k;
1270  mprfloat test;
1271 
1272  if( nll <= 0)
1273  { /* init'tion: fixed */
1274  *bmax = 0.0;
1275  return;
1276  }
1277  *kp=ll[1];
1278  *bmax=a[mm+1][*kp+1];
1279  for (k=2;k<=nll;k++)
1280  {
1281  if (iabf == 0)
1282  {
1283  test=a[mm+1][ll[k]+1]-(*bmax);
1284  if (test > 0.0)
1285  {
1286  *bmax=a[mm+1][ll[k]+1];
1287  *kp=ll[k];
1288  }
1289  }
1290  else
1291  { /* abs values: have fixed it */
1292  test=fabs(a[mm+1][ll[k]+1])-fabs(*bmax);
1293  if (test > 0.0)
1294  {
1295  *bmax=a[mm+1][ll[k]+1];
1296  *kp=ll[k];
1297  }
1298  }
1299  }
1300 }

◆ simp2()

void simplex::simp2 ( mprfloat **  a,
int  n,
int  l2[],
int  nl2,
int *  ip,
int  kp,
mprfloat q1 
)
private

Definition at line 1302 of file mpr_numeric.cc.

1303 {
1304  int k,ii,i;
1305  mprfloat qp,q0,q;
1306 
1307  *ip= 0;
1308  for ( i=1; i <= nl2; i++ )
1309  {
1310  if ( a[l2[i]+1][kp+1] < -SIMPLEX_EPS )
1311  {
1312  *q1= -a[l2[i]+1][1] / a[l2[i]+1][kp+1];
1313  *ip= l2[i];
1314  for ( i= i+1; i <= nl2; i++ )
1315  {
1316  ii= l2[i];
1317  if (a[ii+1][kp+1] < -SIMPLEX_EPS)
1318  {
1319  q= -a[ii+1][1] / a[ii+1][kp+1];
1320  if (q - *q1 < -SIMPLEX_EPS)
1321  {
1322  *ip=ii;
1323  *q1=q;
1324  }
1325  else if (q - *q1 < SIMPLEX_EPS)
1326  {
1327  for ( k=1; k<= nn; k++ )
1328  {
1329  qp= -a[*ip+1][k+1]/a[*ip+1][kp+1];
1330  q0= -a[ii+1][k+1]/a[ii+1][kp+1];
1331  if ( q0 != qp ) break;
1332  }
1333  if ( q0 < qp ) *ip= ii;
1334  }
1335  }
1336  }
1337  }
1338  }
1339 }

◆ simp3()

void simplex::simp3 ( mprfloat **  a,
int  i1,
int  k1,
int  ip,
int  kp 
)
private

Definition at line 1341 of file mpr_numeric.cc.

1342 {
1343  int kk,ii;
1344  mprfloat piv;
1345 
1346  piv= 1.0 / a[ip+1][kp+1];
1347  for ( ii=1; ii <= i1+1; ii++ )
1348  {
1349  if ( ii -1 != ip )
1350  {
1351  a[ii][kp+1] *= piv;
1352  for ( kk=1; kk <= k1+1; kk++ )
1353  if ( kk-1 != kp )
1354  a[ii][kk] -= a[ip+1][kk] * a[ii][kp+1];
1355  }
1356  }
1357  for ( kk=1; kk<= k1+1; kk++ )
1358  if ( kk-1 != kp ) a[ip+1][kk] *= -piv;
1359  a[ip+1][kp+1]= piv;
1360 }

◆ zrovToIV()

intvec * simplex::zrovToIV ( )

Definition at line 1088 of file mpr_numeric.cc.

1089 {
1090  int i;
1091  intvec * iv = new intvec( n );
1092  for ( i= 1; i <= n; i++ )
1093  {
1094  IMATELEM(*iv,i,1)= izrov[i];
1095  }
1096  return iv;
1097 }

Field Documentation

◆ icase

int simplex::icase

Definition at line 201 of file mpr_numeric.h.

◆ iposv

int * simplex::iposv

Definition at line 203 of file mpr_numeric.h.

◆ izrov

int* simplex::izrov

Definition at line 203 of file mpr_numeric.h.

◆ LiPM

mprfloat** simplex::LiPM

Definition at line 205 of file mpr_numeric.h.

◆ LiPM_cols

int simplex::LiPM_cols
private

Definition at line 225 of file mpr_numeric.h.

◆ LiPM_rows

int simplex::LiPM_rows
private

Definition at line 225 of file mpr_numeric.h.

◆ m

int simplex::m

Definition at line 198 of file mpr_numeric.h.

◆ m1

int simplex::m1

Definition at line 200 of file mpr_numeric.h.

◆ m2

int simplex::m2

Definition at line 200 of file mpr_numeric.h.

◆ m3

int simplex::m3

Definition at line 200 of file mpr_numeric.h.

◆ n

int simplex::n

Definition at line 199 of file mpr_numeric.h.


The documentation for this class was generated from the following files:
test
CanonicalForm test
Definition: cfModGcd.cc:4037
simplex::m
int m
Definition: mpr_numeric.h:198
j
int j
Definition: facHensel.cc:105
simplex::simp3
void simp3(mprfloat **a, int i1, int k1, int ip, int kp)
Definition: mpr_numeric.cc:1341
k
int k
Definition: cfEzgcd.cc:92
MATELEM
#define MATELEM(mat, i, j)
Definition: matpol.h:28
simplex::izrov
int * izrov
Definition: mpr_numeric.h:203
simplex::LiPM
mprfloat ** LiPM
Definition: mpr_numeric.h:205
simplex::simp2
void simp2(mprfloat **a, int n, int l2[], int nl2, int *ip, int kp, mprfloat *q1)
Definition: mpr_numeric.cc:1302
pDelete
#define pDelete(p_ptr)
Definition: polys.h:181
loop
#define loop
Definition: structs.h:78
simplex::m1
int m1
Definition: mpr_numeric.h:200
TRUE
#define TRUE
Definition: auxiliary.h:98
simplex::simp1
void simp1(mprfloat **a, int mm, int ll[], int nll, int iabf, int *kp, mprfloat *bmax)
Definition: mpr_numeric.cc:1267
i
int i
Definition: cfEzgcd.cc:125
omFreeSize
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
simplex::m2
int m2
Definition: mpr_numeric.h:200
simplex::icase
int icase
Definition: mpr_numeric.h:201
pOne
#define pOne()
Definition: polys.h:309
intvec
Definition: intvec.h:21
omAlloc0Aligned
#define omAlloc0Aligned
Definition: omAllocDecl.h:274
omAlloc
#define omAlloc(size)
Definition: omAllocDecl.h:210
pSetCoeff
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31
simplex::LiPM_rows
int LiPM_rows
Definition: mpr_numeric.h:225
nIsZero
#define nIsZero(n)
Definition: numbers.h:20
IMATELEM
#define IMATELEM(M, I, J)
Definition: intvec.h:83
simplex::m3
int m3
Definition: mpr_numeric.h:200
mprfloat
double mprfloat
Definition: mpr_global.h:17
Print
#define Print
Definition: emacs.cc:80
error
#define error(a)
Definition: mpr_numeric.cc:970
MATCOLS
#define MATCOLS(i)
Definition: matpol.h:27
WarnS
#define WarnS
Definition: emacs.cc:78
NULL
#define NULL
Definition: omList.c:10
simplex::LiPM_cols
int LiPM_cols
Definition: mpr_numeric.h:225
SIMPLEX_EPS
#define SIMPLEX_EPS
Definition: mpr_numeric.h:181
Warn
#define Warn
Definition: emacs.cc:77
pGetCoeff
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:45
simplex::n
int n
Definition: mpr_numeric.h:199
MATROWS
#define MATROWS(i)
Definition: matpol.h:26
omAlloc0
#define omAlloc0(size)
Definition: omAllocDecl.h:211
gmp_float
Definition: mpr_complex.h:32
simplex::iposv
int * iposv
Definition: mpr_numeric.h:203