1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235
|
/* cddproj.c: Polyhedral Projections in cddlib
written by Komei Fukuda, fukuda@cs.mcgill.ca
Version 0.94i, March 9, 2018
*/
/* cddlib : C-library of the double description method for
computing all vertices and extreme rays of the polyhedron
P= {x : b - A x >= 0}.
Please read COPYING (GNU General Public Licence) and
the manual cddlibman.tex for detail.
*/
#include "setoper.h" /* set operation library header (Ver. June 1, 2000 or later) */
#include "cdd.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <string.h>
dd_MatrixPtr dd_BlockElimination(dd_MatrixPtr M, dd_colset delset, dd_ErrorType *error)
/* Eliminate the variables (columns) delset by
the Block Elimination with dd_DoubleDescription algorithm.
Given (where y is to be eliminated):
c1 + A1 x + B1 y >= 0
c2 + A2 x + B2 y = 0
1. First construct the dual system: z1^T B1 + z2^T B2 = 0, z1 >= 0.
2. Compute the generators of the dual.
3. Then take the linear combination of the original system with each generator.
4. Remove redundant inequalies.
*/
{
dd_MatrixPtr Mdual=NULL, Mproj=NULL, Gdual=NULL;
dd_rowrange i,h,m,mproj,mdual,linsize;
dd_colrange j,k,d,dproj,ddual,delsize;
dd_colindex delindex;
mytype temp,prod;
dd_PolyhedraPtr dualpoly;
dd_ErrorType err=dd_NoError;
dd_boolean localdebug=dd_FALSE;
*error=dd_NoError;
m= M->rowsize;
d= M->colsize;
delindex=(long*)calloc(d+1,sizeof(long));
dd_init(temp);
dd_init(prod);
k=0; delsize=0;
for (j=1; j<=d; j++){
if (set_member(j, delset)){
k++; delsize++;
delindex[k]=j; /* stores the kth deletion column index */
}
}
if (localdebug) dd_WriteMatrix(stdout, M);
linsize=set_card(M->linset);
ddual=m+1;
mdual=delsize + m - linsize; /* #equalitions + dimension of z1 */
/* setup the dual matrix */
Mdual=dd_CreateMatrix(mdual, ddual);
Mdual->representation=dd_Inequality;
for (i = 1; i <= delsize; i++){
set_addelem(Mdual->linset,i); /* equality */
for (j = 1; j <= m; j++) {
dd_set(Mdual->matrix[i-1][j], M->matrix[j-1][delindex[i]-1]);
}
}
k=0;
for (i = 1; i <= m; i++){
if (!set_member(i, M->linset)){
/* set nonnegativity for the dual variable associated with
each non-linearity inequality. */
k++;
dd_set(Mdual->matrix[delsize+k-1][i], dd_one);
}
}
/* 2. Compute the generators of the dual system. */
dualpoly=dd_DDMatrix2Poly(Mdual, &err);
Gdual=dd_CopyGenerators(dualpoly);
/* 3. Take the linear combination of the original system with each generator. */
dproj=d-delsize;
mproj=Gdual->rowsize;
Mproj=dd_CreateMatrix(mproj, dproj);
Mproj->representation=dd_Inequality;
set_copy(Mproj->linset, Gdual->linset);
for (i=1; i<=mproj; i++){
k=0;
for (j=1; j<=d; j++){
if (!set_member(j, delset)){
k++; /* new index of the variable x_j */
dd_set(prod, dd_purezero);
for (h = 1; h <= m; h++){
dd_mul(temp,M->matrix[h-1][j-1],Gdual->matrix[i-1][h]);
dd_add(prod,prod,temp);
}
dd_set(Mproj->matrix[i-1][k-1],prod);
}
}
}
if (localdebug) printf("Size of the projection system: %ld x %ld\n", mproj, dproj);
dd_FreePolyhedra(dualpoly);
free(delindex);
dd_clear(temp);
dd_clear(prod);
dd_FreeMatrix(Mdual);
dd_FreeMatrix(Gdual);
return Mproj;
}
dd_MatrixPtr dd_FourierElimination(dd_MatrixPtr M,dd_ErrorType *error)
/* Eliminate the last variable (column) from the given H-matrix using
the standard Fourier Elimination.
*/
{
dd_MatrixPtr Mnew=NULL;
dd_rowrange i,inew,ip,in,iz,m,mpos=0,mneg=0,mzero=0,mnew;
dd_colrange j,d,dnew;
dd_rowindex posrowindex, negrowindex,zerorowindex;
mytype temp1,temp2;
dd_boolean localdebug=dd_FALSE;
*error=dd_NoError;
m= M->rowsize;
d= M->colsize;
if (d<=1){
*error=dd_ColIndexOutOfRange;
if (localdebug) {
printf("The number of column is too small: %ld for Fourier's Elimination.\n",d);
}
goto _L99;
}
if (M->representation==dd_Generator){
*error=dd_NotAvailForV;
if (localdebug) {
printf("Fourier's Elimination cannot be applied to a V-polyhedron.\n");
}
goto _L99;
}
if (set_card(M->linset)>0){
*error=dd_CannotHandleLinearity;
if (localdebug) {
printf("The Fourier Elimination function does not handle equality in this version.\n");
}
goto _L99;
}
/* Create temporary spaces to be removed at the end of this function */
posrowindex=(long*)calloc(m+1,sizeof(long));
negrowindex=(long*)calloc(m+1,sizeof(long));
zerorowindex=(long*)calloc(m+1,sizeof(long));
dd_init(temp1);
dd_init(temp2);
for (i = 1; i <= m; i++) {
if (dd_Positive(M->matrix[i-1][d-1])){
mpos++;
posrowindex[mpos]=i;
} else if (dd_Negative(M->matrix[i-1][d-1])) {
mneg++;
negrowindex[mneg]=i;
} else {
mzero++;
zerorowindex[mzero]=i;
}
} /*of i*/
if (localdebug) {
dd_WriteMatrix(stdout, M);
printf("No of (+ - 0) rows = (%ld, %ld, %ld)\n", mpos,mneg, mzero);
}
/* The present code generates so many redundant inequalities and thus
is quite useless, except for very small examples
*/
mnew=mzero+mpos*mneg; /* the total number of rows after elimination */
dnew=d-1;
Mnew=dd_CreateMatrix(mnew, dnew);
dd_CopyArow(Mnew->rowvec, M->rowvec, dnew);
/* set_copy(Mnew->linset,M->linset); */
Mnew->numbtype=M->numbtype;
Mnew->representation=M->representation;
Mnew->objective=M->objective;
/* Copy the inequalities independent of x_d to the top of the new matrix. */
for (iz = 1; iz <= mzero; iz++){
for (j = 1; j <= dnew; j++) {
dd_set(Mnew->matrix[iz-1][j-1], M->matrix[zerorowindex[iz]-1][j-1]);
}
}
/* Create the new inequalities by combining x_d positive and negative ones. */
inew=mzero; /* the index of the last x_d zero inequality */
for (ip = 1; ip <= mpos; ip++){
for (in = 1; in <= mneg; in++){
inew++;
dd_neg(temp1, M->matrix[negrowindex[in]-1][d-1]);
for (j = 1; j <= dnew; j++) {
dd_LinearComb(temp2,M->matrix[posrowindex[ip]-1][j-1],temp1,\
M->matrix[negrowindex[in]-1][j-1],\
M->matrix[posrowindex[ip]-1][d-1]);
dd_set(Mnew->matrix[inew-1][j-1],temp2);
}
dd_Normalize(dnew,Mnew->matrix[inew-1]);
}
}
free(posrowindex);
free(negrowindex);
free(zerorowindex);
dd_clear(temp1);
dd_clear(temp2);
_L99:
return Mnew;
}
/* end of cddproj.c */
|