00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00016
00017
00018
00019
00021
00022 #include <abacus/constraint.h>
00023 #include <abacus/variable.h>
00024 #include "abacus/row.h"
00025
00026 #include "StableSetModKSeparator.hh"
00027 #include "GeneralConstraint.hh"
00028 #include "Graph.hh"
00029 #include "ModkSeparator.hh"
00030 #include "StableSetLPSolution.hh"
00031 #include "StableSetMaster.hh"
00032
00033 #include <vector>
00034
00035 using namespace std;
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047 StableSetModKSeparator::StableSetModKSeparator(StableSetLPSolution *solution,
00048 Graph *theGraph):
00049 ABA_SEPARATOR<ABA_CONSTRAINT, ABA_VARIABLE> (solution, true, 10000),
00050 lpSolution(solution),
00051 itsGraph(theGraph)
00052 {
00053 nVariables = theGraph->numberOfNodes();
00054 }
00055
00056
00057
00058
00059
00060 StableSetModKSeparator::~StableSetModKSeparator() {
00061 }
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071 void StableSetModKSeparator::separate() {
00072
00073
00074
00075
00076
00077 StableSetMaster *master = lpSolution->stableSetMaster();
00078
00079 ABA_SUB *sub = lpSolution->sub();
00080
00081 ABA_STANDARDPOOL<ABA_CONSTRAINT,ABA_VARIABLE> *poolPointer;
00082 poolPointer = master->cliqueCutPool();
00083
00084 int nConstraints = poolPointer->number();
00085
00086 int i, j, a;
00087
00088 int nSlack0Constr = 0;
00089
00090 static double eps = 0.0000001;
00091
00092
00093 int *nNonZeros = new int[nConstraints +nVariables];
00094 int **nonZeroIndices = new int*[nConstraints +nVariables];
00095 double **nonZeroCoeffs = new double*[nConstraints +nVariables];
00096 double *rhs = new double[nConstraints +nVariables];
00097
00098 ABA_ROW *row = new ABA_ROW(master, nVariables);
00099
00100 ABA_CONSTRAINT *constrPointer;
00101 vector<int> indexVector;
00102 int numberOfVariablesInConstr;
00103 int index;
00104 double *solutionVal = lpSolution->zVal();
00105
00106 int theKs[] = {2, 3, 5, 7};
00107 int numberOfKs = 4;
00108
00109
00110
00111
00112 for (i=0; i<nConstraints; i++){
00113
00114 constrPointer = (ABA_CONSTRAINT *)(( poolPointer->slot(i) )->conVar());
00115 if (constrPointer == NULL) {
00116 continue;
00117 }
00118
00119
00120 if (constrPointer->slack(sub->actVar(), lpSolution->zVal()) < -eps
00121 || constrPointer->slack(sub->actVar(), lpSolution->zVal()) > +eps) {
00122 continue;
00123 }
00124
00125
00126 rhs[nSlack0Constr] = constrPointer->rhs();
00127 numberOfVariablesInConstr = constrPointer->genRow(sub->actVar(), *row);
00128
00129 for (j=0; j<numberOfVariablesInConstr; j++) {
00130 index = row->support(j);
00131 if (solutionVal[index] >= eps) {
00132 indexVector.push_back(index);
00133 }
00134 }
00135 if (indexVector.size() == 0) {
00136 cout << "\n\n\n\nALARM!!!\n\n\n\n" << endl;
00137 int abcd;
00138 cin >> abcd;
00139 }
00140 nNonZeros[nSlack0Constr] = indexVector.size();
00141 nonZeroIndices[nSlack0Constr] = new int[nNonZeros[nSlack0Constr]];
00142 nonZeroCoeffs[nSlack0Constr] = new double[nNonZeros[nSlack0Constr]];
00143 for (j=0; j<indexVector.size(); j++) {
00144 nonZeroIndices[nSlack0Constr][j] = indexVector[j];
00145 nonZeroCoeffs[nSlack0Constr][j] = row->coeff(j);
00146 }
00147 nSlack0Constr++;
00148
00149
00150 row->clear();
00151 indexVector.clear();
00152 }
00153
00154
00155 for (i=0; i<nVariables; i++) {
00156 if (solutionVal[i] <= eps) {
00157 nNonZeros[nSlack0Constr] = 1;
00158 nonZeroIndices[nSlack0Constr] = new int[1];
00159 nonZeroIndices[nSlack0Constr][0] = i;
00160 nonZeroCoeffs[nSlack0Constr] = new double[1];
00161 nonZeroCoeffs[nSlack0Constr][0] = -1;
00162 rhs[nSlack0Constr] = 0;
00163 nSlack0Constr++;
00164 }
00165 else {
00166 if (solutionVal[i] >= 1-eps) {
00167 nNonZeros[nSlack0Constr] = 1;
00168 nonZeroIndices[nSlack0Constr] = new int[1];
00169 nonZeroIndices[nSlack0Constr][0] = i;
00170 nonZeroCoeffs[nSlack0Constr] = new double[1];
00171 nonZeroCoeffs[nSlack0Constr][0] = 1;
00172 rhs[nSlack0Constr] = 1;
00173 nSlack0Constr++;
00174 }
00175 }
00176 }
00177
00178
00179
00180
00181
00182 if (nSlack0Constr == 0) {
00183 cout << "\n\t\tNo constraints with slack 0." << endl;
00184
00185 return;
00186 }
00187
00188
00189
00190
00191
00192 for (a=0; a<numberOfKs; a++) {
00193
00194
00195 ModkSeparator *modkSeparator;
00196 modkSeparator = new ModkSeparator(theKs[a], nSlack0Constr, nVariables,
00197 nNonZeros,
00198 nonZeroIndices, nonZeroCoeffs, rhs,
00199 lpSolution->zVal());
00200
00201 int num = modkSeparator->separate( nVariables );
00202
00203 ofstream fout(itsGraph->getFileName(), ios::app);
00204 fout << "\n* Mod :" << theKs[a] << endl;
00205 fout.close();
00206
00207
00208 if (num) {
00209
00210 int *cutInfo;
00211
00212 vector<int> lhs;
00213 vector<int> coeff;
00214 int rhsCut;
00215 int cutSize;
00216
00217
00218 for (i=0; i<num; i++) {
00219
00220 cutInfo = modkSeparator->getCut();
00221
00222 if (cutInfo == NULL || cutInfo[0] == 0) {
00223 if (cutInfo != NULL) {
00224 delete [] cutInfo;
00225 }
00226 continue;
00227 }
00228
00229
00230 cutSize = cutInfo[0];
00231 lhs.resize(cutSize);
00232 coeff.resize(cutSize);
00233 for (j=0; j<cutSize; j++) {
00234 lhs[j] = cutInfo[j+1];
00235 }
00236 for (j=0; j<cutSize; j++) {
00237 coeff[j] = cutInfo[j +1 +cutSize];
00238 }
00239 rhsCut = cutInfo[1 +cutSize +cutSize];
00240
00241
00242 GeneralConstraint *generalConstr;
00243 generalConstr = new GeneralConstraint(master, &lhs, &coeff,
00244 rhsCut, itsGraph);
00245
00246 cutFound(generalConstr);
00247
00248
00249 delete[] cutInfo;
00250 }
00251
00252 }
00253
00254
00255 lpSolution->stableSetMaster()->out() << "\tMod " << theKs[a] << ":\t";
00256 lpSolution->stableSetMaster()->out() << num << endl;
00257
00258
00259 delete modkSeparator;
00260
00261 }
00262
00263
00264
00265 delete row;
00266 for (i=0; i<nSlack0Constr; i++){
00267 delete[] nonZeroIndices[i];
00268 delete[] nonZeroCoeffs[i];
00269 }
00270 delete[] nNonZeros;
00271 delete[] rhs;
00272 delete[] nonZeroIndices;
00273 delete[] nonZeroCoeffs;
00274
00275 }
00276
00277
00278
00279
00280
00281 void StableSetModKSeparator::applyRanking(ABA_BUFFER<double> *rank) {
00282
00283
00284 if (cutBuffer().number() == 0) {
00285 return;
00286 }
00287
00288
00289
00290
00291 StableSetMaster *master = lpSolution->stableSetMaster();
00292 ABA_SUB *sub = lpSolution->sub();
00293 ABA_CONSTRAINT *constrPointer;
00294 ABA_POOLSLOT<ABA_CONSTRAINT, ABA_VARIABLE> *constrSlot;
00295 int i, j;
00296 double slack, nNonZeroCoeffs, rankValue;
00297
00298 ABA_STANDARDPOOL<ABA_VARIABLE, ABA_CONSTRAINT> *varPool;
00299 ABA_POOLSLOT<ABA_VARIABLE, ABA_CONSTRAINT> *varSlot;
00300 varPool = master->varPool();
00301 ABA_VARIABLE *varPointer;
00302 double constrCoeff, objectiveCoeff, scaleCoeff = 0, scaleObj = 0;
00303
00304
00305
00306
00307 for (i=0; i<cutBuffer().number(); i++){
00308 constrPointer = cutBuffer()[i];
00309 rankValue = 0;
00310 for(j=0; j<nVariables; j++){
00311 varPointer = (varPool->slot(j))->conVar();
00312 objectiveCoeff = varPointer->obj();
00313 if (objectiveCoeff > 0.999999 && objectiveCoeff < 1.000001) {
00314 objectiveCoeff = 1;
00315 }
00316 if(objectiveCoeff < -0.999999 && objectiveCoeff > -1.000001) {
00317 objectiveCoeff = -1;
00318 }
00319 constrCoeff = constrPointer->coeff(varPointer);
00320
00321 rankValue += (objectiveCoeff * constrCoeff);
00322
00323 scaleCoeff += (constrCoeff * constrCoeff);
00324 scaleObj += (objectiveCoeff* objectiveCoeff);
00325
00326 }
00327
00328 scaleCoeff = sqrt(scaleCoeff);
00329 scaleObj = sqrt(scaleObj);
00330 rankValue = rankValue / (scaleCoeff * scaleObj);
00331
00332
00333 rankValue = 1 - rankValue;
00334 rank->push(rankValue);
00335 }
00336
00337 return;
00338
00339 }
00340
00341