[Scip] Clustering problem
Martina Astegno
talpatina at yahoo.it
Mon Apr 26 12:53:16 MEST 2010
Hi all!
This is the code that I've written to solve a clustering problem. The idea is to minimize the sum of max distance inter-cluster (diameter) and maximize the sum of min_distance intra-cluster.
OBJECTIVE FUNCTION
MIN sum[j=1..Nclusters] _diameter[j] - sum[j=1..Nclusters-1] sum[h= j+1..Nclusters] _minDistance[j][h]
s.t.
sum[j=1...Nclusters] w[i][j] = 1 for each i=1...Nelements
z[i][l][j][h] = w[i][j] AND w[l][h] for each i, l, j, h
_diameter[j] >= z[i][l][j][j] *d[i][l] for each j, i, l
_minDistance[j][h] <= z[i][l][j][h] *d[i][l] for each j, h, i, l
w[i][j] = 1 if element i is in cluster j; o otherwise.
i = 1..Nelements
j = 1..Nclusters
The input is:
- number of elements
- number of clusters
- matrix distances between each element
/* constructor */
scipMeMOC::ClusterSolver::ClusterSolver(char * fname)
: _scip(0), _cons()
{
cout << "READING... " << endl;
// initialize instance data
readData(fname);
cout << "INIT SCIP... " << endl;
// initialize scip
SCIP_CALL_EXC( SCIPcreate(& _scip) );
// load default plugins like separators, heuristics, etc.
SCIP_CALL_EXC( SCIPincludeDefaultPlugins(_scip) );
// disable scip output to stdout
SCIP_CALL_EXC( SCIPsetMessagehdlr(NULL) );
// create an empty problem
SCIP_CALL_EXC( SCIPcreateProb(_scip, "clustering", NULL, NULL, NULL, NULL, NULL, NULL) );
// set the objective sense to minimize
SCIP_CALL_EXC( SCIPsetObjsense(_scip, SCIP_OBJSENSE_MINIMIZE) );
// create a binary variable for each element for each cluster w[i][j]
ostringstream namebuf;
for (int i = 0; i < _numElements; ++i)
{
std::vector<SCIP_VAR*>* v = new vector<SCIP_VAR*>();
for(int j = 0; j < _numClusters; ++j)
{
SCIP_VAR * var;
namebuf.str("");
namebuf << "w#" << i << "#" << j;
// create the SCIP_VAR object
SCIP_CALL_EXC( SCIPcreateVar(_scip, & var, namebuf.str().c_str(), 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, TRUE, FALSE, NULL, NULL, NULL, NULL) );
// add the SCIP_VAR object to the scip problem
SCIP_CALL_EXC( SCIPaddVar(_scip, var) );
// storing the SCIP_VAR pointer for later access
v->push_back(var);
}
_varsW.push_back(*v);
}
// create a binary variable for z[i][l][j][h]
for (int i = 0; i < _numElements; ++i)
{
std::vector<vector<vector<SCIP_VAR* > > > v2;
std::vector<vector < SCIP_VAR* > > v1;
std::vector<SCIP_VAR*>* v = new vector<SCIP_VAR*>();
for(int l = 0; l < _numElements; ++l)
{
for(int j= 0; j < _numClusters; ++j)
{
for(int h=0; h < _numClusters; ++h)
{
SCIP_VAR * var;
namebuf.str("");
namebuf << "z#" << i << "#" << l << "#" << j << "#" << h ;
// create the SCIP_VAR object
SCIP_CALL_EXC( SCIPcreateVar(_scip, & var, namebuf.str().c_str(), 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, TRUE, FALSE, NULL, NULL, NULL, NULL) );
// add the SCIP_VAR object to the scip problem
SCIP_CALL_EXC( SCIPaddVar(_scip, var) );
// storing the SCIP_VAR pointer for later access
v->push_back(var);
}
v1.push_back(*v);
}
v2.push_back(v1);
}
_varsZ.push_back(v2);
}
//create a variable for diameter of each cluster
for(int j=0; j < _numClusters; ++j)
{
SCIP_VAR * var;
namebuf.str("");
namebuf << "D#" << j;
// create the SCIP_VAR object
SCIP_CALL_EXC( SCIPcreateVar(_scip, & var, namebuf.str().c_str(), 0.0, SCIPinfinity(_scip), 1.0, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL) );
// add the SCIP_VAR object to the scip problem
SCIP_CALL_EXC( SCIPaddVar(_scip, var) );
// storing the SCIP_VAR pointer for later access
_diameter.push_back(var);
}
//create a variable for minimun distance of each pair of cluster
for(int j=0; j < _numClusters-1; ++j)
{
std::vector<SCIP_VAR*>* v = new vector<SCIP_VAR*>();
for(int h=j+1; h < _numClusters; ++h)
{
SCIP_VAR * var;
namebuf.str("");
namebuf << "MinDistance#" << j <<"#" << h;
// create the SCIP_VAR object
SCIP_CALL_EXC( SCIPcreateVar(_scip, & var, namebuf.str().c_str(), 0.0, SCIPinfinity(_scip), -1.0, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL) );
// add the SCIP_VAR object to the scip problem
SCIP_CALL_EXC( SCIPaddVar(_scip, var) );
// storing the SCIP_VAR pointer for later access
v->push_back(var);
}
_minDistance.push_back(*v);
}
// create constraints
// each element is exactly only in a cluster
for (int i=0; i < _numElements; ++i)
{
SCIP_CONS * cons;
namebuf.str("");
namebuf<<"element_"<<i;
// create SCIP_CONS object
// this is an equality since an element must be only in a cluster
SCIP_CALL_EXC( SCIPcreateConsLinear(_scip, & cons, namebuf.str().c_str(), 0, NULL, NULL, 1.0, 1.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
// add the vars belonging to field in this row to the constraint
for (int j = 0; j < _numClusters; ++j)
SCIP_CALL_EXC( SCIPaddCoefLinear(_scip, cons, _varsW[i][j], 1.0) );
// add the constraint to scip
SCIP_CALL_EXC( SCIPaddCons(_scip, cons) );
// store the constraint for later on
_cons.push_back(cons);
}
//vincolo and
for(int i=0; i< _numElements; ++i)
{
for(int j=0; j< _numClusters; ++j)
{
for(int l=0; l< _numElements; ++l)
{
for(int h=0; h< _numClusters; ++h)
{
SCIP_CONS * cons;
namebuf.str("");
namebuf<<"and" << i <<"#"<<l<<"#"<<j<<"#"<<h;
SCIP_VAR* support[2];
support[0] = _varsW[i][j];
support[1] = _varsW[l][h];
SCIP_CALL_EXC(SCIPcreateConsAnd(_scip, & cons, namebuf.str().c_str(), _varsZ[i][l][j][h], 2, support, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE));
// add the constraint to scip
SCIP_CALL_EXC( SCIPaddCons(_scip, cons) );
// store the constraint for later on
_cons.push_back(cons);
}
}
}
}
/constraints to find diameter for each cluster
for (int j=0; j < _numClusters; ++j)
{
for(int i=0; i < _numElements-1; ++i )
{
for(int l=i+1; l < _numElements; ++l )
{
SCIP_CONS * cons;
namebuf.str("");
namebuf<<"diameter_"<<j;
// create SCIP_CONS object
SCIP_CALL_EXC(SCIPcreateConsVarbound(_scip, & cons, namebuf.str().c_str(), _diameter[j], _varsZ[i][l][j][j], -(_distances[i][l]), 0, SCIPinfinity(_scip), TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ));
// add the constraint to scip
SCIP_CALL_EXC( SCIPaddCons(_scip, cons) );
// store the constraint for later on
_cons.push_back(cons);
}
}
}
//constraints to find the minimun distance between each pair of cluster
for (int j=0; j < _numClusters-1; ++j)
{
for (int h=j+1; h < _numClusters; ++h)
{
for(int i=0; i < _numElements-1; ++i )
{
for(int l=i+1; l < _numElements; ++l)
{
SCIP_CONS * cons;
namebuf.str("");
namebuf<<"minDistance_"<<j << "#" << h;
// create SCIP_CONS object
SCIP_CALL_EXC(SCIPcreateConsVarbound(_scip, & cons, namebuf.str().c_str(), _minDistance[j][h], _varsZ[i][l][j][h], -(_distances[i][l]), -SCIPinfinity(_scip), 0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ));
// add the constraint to scip
SCIP_CALL_EXC( SCIPaddCons(_scip, cons) );
// store the constraint for later on
_cons.push_back(cons);
}
}
}
}
}
In the header file I've defined the following SCIP var and cons:
std::vector<std::vector<std::vector<std::vector<SCIP_VAR *> > > > _varsZ;
std::vector<std::vector<SCIP_VAR *> > _varsW;
std::vector<SCIP_VAR *> _diameter;
std::vector<std::vector<SCIP_VAR *> > _minDistance;
std::vector<SCIP_CONS *> _cons;
In trivial case when the number of clusters is 1, it works; but when clusters are more then one it doesn't find a solution.
Any idea??
Many thanks!!
Marty
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20100426/4d7e28ec/attachment.html
More information about the Scip
mailing list