[Scip] Clustering problem
Marc Pfetsch
m.pfetsch at tu-bs.de
Mon Apr 26 16:40:59 MEST 2010
Hi Marty,
I am not sure whether I understand your model - I assume that you
actually want to do something similar to a paper of ours:
http://www.optimization-online.org/DB_HTML/2006/11/1529.html
It contains a model for the graph partitioning problem in which the w
variables of you model appear as well. The variables z in your model
seem to have too many indices. We use one variable y[i][k] which is 1
exactly when nodes i and k are in the same cluster. Then we force
w[i][j] + w[k][j] - y[i][k] <= 1.
This guarantees y[i][k] to be 1 if i and k are in the same cluster.
(Depending on the objective function you may need to add other
inequalties that also force y[i][k] to be zero). You can also model it
using an AND-Constraint, which adds the constraints automatically.
Best,
Marc
Martina Astegno schrieb:
> 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
>
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
More information about the Scip
mailing list