IBM ILOG Solver User's Manual > Extending the Library > Writing a Constraint: Allocating Frequencies > Writing a constraint: Frequency allocation > Complete frequency allocation program |
Complete frequency allocation program |
INDEX
![]() |
The complete program follows. You can also view the entire program online in the file YourSolverHome
/examples/src/freq.cpp.
#include <ilsolver/ilosolverint.h> ILOSTLBEGIN const int nbCell = 25; const int nbAvailFreq = 256; const int nbChannel[nbCell] = { 8,6,6,1,4,4,8,8,8,8,4,9,8,4,4,10,8,9,8,4,5,4,8,1,1 }; const int dist[nbCell][nbCell] = { { 16,1,1,0,0,0,0,0,1,1,1,1,1,2,2,1,1,0,0,0,2,2,1,1,1 }, { 1,16,2,0,0,0,0,0,2,2,1,1,1,2,2,1,1,0,0,0,0,0,0,0,0 }, { 1,2,16,0,0,0,0,0,2,2,1,1,1,2,2,1,1,0,0,0,0,0,0,0,0 }, { 0,0,0,16,2,2,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,1 }, { 0,0,0,2,16,2,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,1 }, { 0,0,0,2,2,16,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,1 }, { 0,0,0,0,0,0,16,2,0,0,1,1,1,0,0,1,1,1,1,2,0,0,0,1,1 }, { 0,0,0,0,0,0,2,16,0,0,1,1,1,0,0,1,1,1,1,2,0,0,0,1,1 }, { 1,2,2,0,0,0,0,0,16,2,2,2,2,2,2,1,1,1,1,1,1,1,0,1,1 }, { 1,2,2,0,0,0,0,0,2,16,2,2,2,2,2,1,1,1,1,1,1,1,0,1,1 }, { 1,1,1,0,0,0,1,1,2,2,16,2,2,2,2,2,2,1,1,2,1,1,0,1,1 }, { 1,1,1,0,0,0,1,1,2,2,2,16,2,2,2,2,2,1,1,2,1,1,0,1,1 }, { 1,1,1,0,0,0,1,1,2,2,2,2,16,2,2,2,2,1,1,2,1,1,0,1,1 }, { 2,2,2,0,0,0,0,0,2,2,2,2,2,16,2,1,1,1,1,1,1,1,1,1,1 }, { 2,2,2,0,0,0,0,0,2,2,2,2,2,2,16,1,1,1,1,1,1,1,1,1,1 }, { 1,1,1,0,0,0,1,1,1,1,2,2,2,1,1,16,2,2,2,1,2,2,1,2,2 }, { 1,1,1,0,0,0,1,1,1,1,2,2,2,1,1,2,16,2,2,1,2,2,1,2,2 }, { 0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,2,2,16,2,2,1,1,0,2,2 }, { 0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,16,2,1,1,0,2,2 }, { 0,0,0,1,1,1,2,2,1,1,2,2,2,1,1,1,1,2,2,16,1,1,0,1,1 }, { 2,0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,1,1,1,16,2,1,2,2 }, { 2,0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,1,1,1,2,16,1,2,2 }, { 1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,1,1,16,1,1 }, { 1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,1,2,2,1,16,2 }, { 1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,1,2,2,1,2,16 } }; IlcRevInt** freqUsage; class IlcFreqConstraintI : public IlcConstraintI { protected: IlcIntVarArray _x; public: IlcFreqConstraintI(IloSolver s, IlcIntVarArray x) : IlcConstraintI(s), _x(x) {} ~IlcFreqConstraintI() {} virtual void post(); virtual void propagate() {} void varDemon(IlcIntVar var); }; ILCCTDEMON1(FreqDemon, IlcFreqConstraintI, varDemon, IlcIntVar, var); void IlcFreqConstraintI::post () { IlcInt i; for (i = 0; i < _x.getSize(); i++) _x[i].whenValue(FreqDemon(getSolver(), this, _x[i])); } void IlcFreqConstraintI::varDemon (IlcIntVar var) { IlcRevInt& freq = *freqUsage[var.getValue()]; freq.setValue(getSolver(), freq.getValue() + 1); } IlcConstraint IlcFreqConstraint(IloSolver s, IlcIntVarArray x) { return new (s.getHeap()) IlcFreqConstraintI(s, x); } ILOCPCONSTRAINTWRAPPER1(IloFreqConstraint, solver, IloIntVarArray, _vars) { use(solver, _vars); return IlcFreqConstraint(solver, solver.getIntVarArray(_vars)); } IlcInt bestFreq(IlcIntVar var) { IlcInt max = -1; IlcInt maxIndex = 0; IlcInt i; for(IlcIntExpIterator iter(var);iter.ok();++iter){ i=*iter; if (*freqUsage[i] > max){ max = *freqUsage[i]; maxIndex = i; } } return maxIndex; } ILCGOAL1(Instantiate, IlcIntVar, var) { if (var.isBound()) return 0; IlcInt val = bestFreq(var); return IlcOr(var == val, IlcAnd(var != val, this)); } void SetCluster(IlcIntVar var, IlcInt clusterSize) { var.setObject((IlcAny) clusterSize); } IlcInt GetCluster(IlcIntVar var) { return (IlcInt) (var.getObject()); } static IlcChooseIndex2(IlcChooseClusterFreq, var.getSize(), GetCluster(var), IlcIntVar) ILCGOAL1(MyGenerate, IlcIntVarArray, vars) { IloSolver solver = getSolver(); IlcInt chosen = IlcChooseClusterFreq(vars); if(chosen == -1) return 0; return IlcAnd(Instantiate(solver, vars[chosen]),this); } ILOCPGOALWRAPPER1(MyIloGenerate, solver, IloIntVarArray, vars) { return MyGenerate(solver, solver.getIntVarArray(vars)); } IlcInt partialsum[nbCell]; inline IlcInt acc(IlcInt i, IlcInt j) { return partialsum[i]+j; } int main(){ IloEnv env; try { IloModel model(env); IloSolver solver(env); IlcInt i, ii, j, jj; IlcInt usedFreq = 0; IlcInt nbXmiter = 0; for (i = 0; i < nbCell; i++) { partialsum[i] = nbXmiter; nbXmiter += nbChannel[i]; } IloIntVarArray X(env, nbXmiter, 0, nbAvailFreq - 1); for (i = 0; i < nbCell; i++) for (j = i; j < nbCell; j++) for (ii = 0; ii < nbChannel[i]; ii++) for (jj = 0; jj < nbChannel[j]; jj++) if (dist[i][j] != 0 && (i != j || ii != jj)) model.add(IloAbs(X[acc(i,ii)] - X[acc(j,jj)]) >= dist[i][j]); model.add(IloFreqConstraint(env, X)); solver.extract(model); for (i = 0; i < nbCell; i++) for (ii = 0; ii < nbChannel[i]; ii++) SetCluster(solver.getIntVar(X[acc(i,ii)]), nbChannel[i]); freqUsage = new (env) IlcRevInt* [nbAvailFreq]; for (i = 0; i < nbAvailFreq; i++) freqUsage[i] = new (env) IlcRevInt(solver); solver.solve(MyIloGenerate(env, X)); for (i = 0; i < nbCell; i++) { for (j = 0; j < nbChannel[i]; j++) solver.out() << solver.getValue(X[acc(i,j)]) << " " ; solver.out() << endl; } solver.out() << "Total # of sites " << nbXmiter << endl; for (i = 0; i < nbAvailFreq; i++) if (freqUsage[i]->getValue() != 0) usedFreq++; solver.out() << "Total # of frequencies " << usedFreq << endl; } catch (IloException& ex) { cout << "Error: " << ex << endl; } env.end(); return 0; }
The strategy used here allows the program to find good solutions. Indeed, on this data, it leads directly to the optimal solution. Here is the output:
© Copyright IBM Corp. 1987, 2009. Legal terms. | PREVIOUS NEXT |