[Scip] Clustering problem

Ambros Gleixner gleixner at zib.de
Mon Apr 26 15:27:20 MEST 2010


Hi Marty,

I could imagine that your model might always allow for a trivially
feasible solution.  If this is the case, you could provide it to SCIP
using the functions SCIPcreateSol, SCIPsetSolVal/SCIPsetSolVals,
SCIPtrySol/SCIPtrySolFree.
In some cases, this can help SCIP during the solution process, even if
the solution is highly suboptimal, e.g. because SCIP can run its
improvement heuristics on it.

With

   SCIPwriteOrigProblem(_scip, "clustering.lp", NULL, TRUE)
   SCIPwriteOrigProblem(_scip, "clustering.cip", NULL, TRUE)

you can write your problem in LP and the SCIP-specific CIP format to the
disk.  If you send us some of your instances for which SCIP does not
find a solution, then we can look into this.

Please do not send the instances to the mailing list, but directly to
gleixner at zib.de, or if they are very large rather put them online for
download.

Thanks,
ambros



Am 26.04.2010 12:53, schrieb Martina Astegno:
> 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

-- 
____________________________________________________________
Ambros M. Gleixner
Zuse Institute Berlin - Matheon - Berlin Mathematical School
http://www.zib.de/gleixner


More information about the Scip mailing list