| 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
PREVIOUS
NEXT
|
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 |