- Main Page
- Classes
- Files

- File List

# OptFrame/Exact/setpart/SetPart.hpp

    00001 /*
    00002 Class SetPart
    00003 Description: exact set partition model
    00004 Author: Sabir Ribas
    00005 Email: sabirribas@gmail.com
    00006 Date: Jun 22, 2010
    00007 Version: 0.6
    00008 */
    00009
    00010 #ifndef SETPART_HPP
    00011 #define SETPART_HPP
    00012
    00013 #include <cstdio>
    00014 #include <cstdlib>
    00015 #include <iostream>
    00016 #include <sstream>
    00017 #include <vector>
    00018
    00019 #include "../../Util/Scanner++/Scanner.h"
    00020 #include "../../Util/printable.h"
    00021
    00022 #include <ilcplex/ilocplex.h>
    00023 ILOSTLBEGIN
    00024
    00025 using namespace std;
    00026
    00027 /***
    00028 Class Column
    00029 */
    00030
    00031 class Column
    00032 {
    00033 public:
    00034         double cost;
    00035         vector<bool> values;
    00036         Column(double _cost, vector<bool> _values):cost(_cost),values(_values){};
    00037 };
    00038
    00039 typedef vector<Column> Columns;
    00040 typedef IloArray<IloNumArray>    NumMatrix;
    00041 typedef IloArray<IloNumVarArray> NumVarMatrix;
    00042
    00043 /***
    00044 Class SetPart
    00045 */
    00046
    00047 class SetPart
    00048 {
    00049 protected:
    00050         int lines,maxColumns;
    00051         Columns columns;
    00052
    00053 public:
    00054
    00055         SetPart(int _lines,int _maxColumns):lines(_lines),maxColumns(_maxColumns){};
    00056
    00057         // SetPart::setColumn
    00058         //   Parameters: cost and column
    00059         //   Return: int column index (if >= 0) or error code (if < 0)
    00060         int addColumn(double cost, vector<bool> values)
    00061         {
    00062                 if (values.size() != lines)
    00063                 {
    00064                         //cerr << "[SetPart::addColumn] Warning: the column size must be equal the number of lines" << endl;
    00065                         return -1;
    00066                 }
    00067
    00068                 bool hasATrue = false;
    00069                 for (unsigned i = 0 ; i < values.size() && !hasATrue ; i++)
    00070                         if (values[i] == true)
    00071                                 hasATrue = true;
    00072
    00073                 if (!hasATrue)
    00074                 {
    00075                         //cerr << "[SetPart::addColumn] Warning: there are no elements at this column" << endl;
    00076                         return -2;
    00077                 }
    00078
    00079                 if (exists(cost,values))
    00080                 {
    00081                         //cerr << "[SetPart::addColumn] Warning: this column already exists in the set" << endl;
    00082                         return -3;
    00083                 }
    00084
    00085                 if (cost < 0)
    00086                 {
    00087                         //cerr << "[SetPart::addColumn] Warning: the cost must be non-negative" << endl;
    00088                         return -4;
    00089                 }
    00090
    00091                 columns.push_back( Column(cost,values) );
    00092
    00093                 return columns.size()-1;
    00094         };
    00095
    00096         bool exists(double cost, vector<bool> values)
    00097         {
    00098                 for (unsigned i = 0 ; i < columns.size() ; i++)
    00099                         if (cost == columns[i].cost && values == columns[i].values) return true;
    00100                 return false;
    00101         }
    00102
    00103         pair< double , vector<int> > solve()
    00104         {
    00105                 cout << "[SetPart::solve]: Calling optimizer" << endl;
    00106
    00107                 double finalCost = 0;
    00108                 vector<int> cs;
    00109
    00110                 /* Solving by Concert */
    00111
    00112                 //model
    00113                 /*
    00114                         minimize Z:
    00115                            sum {j in C} Custos[j] * Y[j];
    00116
    00117                         subject to
    00118                            R2 {i in L}:
    00119                           sum {j in C} Y[j] * Matriz[i,j] = 1;
    00120                            R2 sum {j in C} Y[j] <= k;
    00121                  */
    00122
    00123                 IloEnv env;
    00124                 try {
    00125                         IloModel model(env);
    00126
    00127                         IloInt i,j;
    00128                         IloInt m(lines);
    00129                         IloInt n(columns.size());
    00130
    00131                         IloIntVarArray y(env, n);
    00132
    00133                         for(j = 0; j < n; j++) {
    00134                                 stringstream str; str << "Y[" << j << "]";
    00135                                 y[j] = IloIntVar(env, 0, 1, str.str().c_str());
    00136                         }
    00137
    00138                         IloNumArray costs(env,n);
    00139                         IloIntArray2 matrix(env, m);
    00140
    00141                         for(i = 0; i < lines; i++) {
    00142                                 //cout << endl;
    00143                                 matrix[i] = IloIntArray(env,columns.size());
    00144                                 for(j = 0; j < columns.size(); j++) {
    00145                                         matrix[i][j] = IloInt(columns[j].values[i]);
    00146                                         //cout << i << " " << j << " " << matrix[i][j] << " | ";
    00147                                 }
    00148                         }
    00149
    00150                         IloExpr obj(env);
    00151                         for(j = 0; j < n; j++) {
    00152                                 costs[j] = IloNum(columns[j].cost);
    00153                                 obj += costs[j] * y[j];
    00154                         }
    00155
    00156                         model.add(IloMinimize(env,obj));
    00157
    00158                         for(i = 0; i < m; i++)
    00159                         {
    00160                                 IloExpr r2(env);
    00161                                 for(j = 0; j < n; j++)
    00162                                         r2 += y[j] * matrix[i][j];
    00163                                 //model.add(v == IloInt(1));
    00164                                 model.add(IloConstraint( r2 == 1 ));
    00165                                 r2.end();
    00166                         }
    00167
    00168                         IloExpr r3(env);
    00169                         for(j = 0; j < n; j++) r3 += y[j];
    00170                         model.add(IloConstraint( r3 <= maxColumns ));
    00171                         r3.end();
    00172
    00173                         //cplex
    00174                         IloCplex cplex(model);
    00175                         cplex.exportModel("setpart.lp");
    00176                         cplex.solve();
    00177
    00178                         for(j = 0; j < columns.size(); j++)
    00179                                 if (cplex.getValue(y[j]) > .5) { cs.push_back( j ); finalCost += costs[j]; }
    00180
    00181                         for(i = 0; i < lines; i++) {
    00182                                 cout << endl;
    00183                                 for(j = 0; j < columns.size(); j++) {
    00184                                         if (cplex.getValue(y[j]) > .5)
    00185                                                 cout << matrix[i][j] << " | ";
    00186                                 }
    00187                         }
    00188
    00189
    00190                 }catch(...)
    00191                 {};
    00192
    00193                 return make_pair( finalCost , cs );
    00194         }
    00195
    00196         int numberOfColumns(){return columns.size();}
    00197
    00198 };
    00199
    00200 #endif /*SETPART_HPP*/
    00201

All Classes Functions