[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