src/lemon/lp_glpk.cc
author athos
Fri, 20 May 2005 09:43:40 +0000
changeset 1432 46b088b01f88
parent 1431 ad44b1dd8013
permissions -rw-r--r--
Functions _eraseRow(), _eraseCol(). Not yet implemented for cplex.
     1 /* -*- C++ -*-
     2  * src/lemon/lp_glpk.cc - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_LP_GLPK_CC
    18 #define LEMON_LP_GLPK_CC
    19 
    20 ///\file
    21 ///\brief Implementation of the LEMON-GLPK lp solver interface.
    22 
    23 #include <lemon/lp_glpk.h>
    24 
    25 namespace lemon {
    26 
    27   ///\e
    28 
    29   ///\bug Unimplemented!
    30   ///
    31   LpSolverBase &LpGlpk::_newLp()
    32   {
    33     LpSolverBase *tmp=0;
    34     return *tmp;
    35   }
    36   
    37   ///\e
    38 
    39   ///\bug Unimplemented!
    40   ///
    41   LpSolverBase &LpGlpk::_copyLp()
    42   {
    43     LpSolverBase *tmp=0;
    44     return *tmp;
    45   }
    46 
    47   LpGlpk::LpGlpk() : Parent(), 
    48 		     lp(lpx_create_prob()) {
    49     ///\todo constrol function for this:
    50     lpx_set_int_parm(lp, LPX_K_DUAL, 1);
    51     messageLevel(0);
    52   }
    53   
    54   LpGlpk::~LpGlpk() {
    55     lpx_delete_prob(lp);
    56   }
    57   
    58   int LpGlpk::_addCol() { 
    59     int i=lpx_add_cols(lp, 1);
    60     _setColLowerBound(i, -INF);
    61     _setColUpperBound(i, INF);
    62     return i;
    63   }
    64 
    65   int LpGlpk::_addRow() { 
    66     int i=lpx_add_rows(lp, 1);
    67     return i;
    68   }
    69 
    70   
    71   void LpGlpk::_eraseCol(int i) {
    72     int cols[2];
    73     cols[1]=i;
    74     lpx_del_cols(lp, 1, cols);
    75   }
    76   
    77   void LpGlpk::_eraseRow(int i) {
    78     int rows[2];
    79     rows[1]=i;
    80     lpx_del_rows(lp, 1, rows);
    81   }
    82 
    83   void LpGlpk::_setRowCoeffs(int i, 
    84 			     int length,
    85 			     const int   * indices, 
    86 			     const Value   * values )
    87   {
    88     lpx_set_mat_row(lp, i, length,
    89 		    const_cast<int * >(indices) ,
    90 		    const_cast<Value * >(values));
    91   }
    92   
    93   void LpGlpk::_setColCoeffs(int i, 
    94 			     int length,
    95 			     const int   * indices, 
    96 			     const Value   * values)
    97   {
    98     lpx_set_mat_col(lp, i, length,
    99 		    const_cast<int * >(indices),
   100 		    const_cast<Value * >(values));
   101   }
   102 
   103 
   104   void LpGlpk::_setCoeff(int row, int col, Value value) 
   105   {
   106     ///FIXME Of course this is not efficient at all, but GLPK knows not more.
   107     // First approach: get one row, apply changes and set it again
   108     //(one idea to improve this: maybe it is better to do this with 1 coloumn)
   109     
   110     int mem_length=2+lpx_get_num_cols(lp);
   111     int* indices = new int[mem_length];
   112     Value* values = new Value[mem_length];
   113     
   114 
   115     int length=lpx_get_mat_row(lp, row, indices, values);
   116 
   117     //The following code does not suppose that the elements of the array indices are sorted
   118     int i=1;
   119     bool found=false;
   120     while (i <= length && !found){
   121       if (indices[i]==col){
   122 	found = true;
   123 	values[i]=value;
   124       }
   125       ++i;
   126     }
   127     if (!found){
   128       ++length;
   129       indices[length]=col;
   130       values[length]=value;
   131     }
   132     
   133     lpx_set_mat_row(lp, row, length, indices, values);
   134     delete [] indices;
   135     delete [] values;
   136     
   137   }
   138 
   139   void LpGlpk::_setColLowerBound(int i, Value lo)
   140   {
   141     if (lo==INF) {
   142       //FIXME error
   143     }
   144     int b=lpx_get_col_type(lp, i);
   145     double up=lpx_get_col_ub(lp, i);	
   146     if (lo==-INF) {
   147       switch (b) {
   148       case LPX_FR:
   149       case LPX_LO:
   150 	lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
   151 	break;
   152       case LPX_UP:
   153 	break;
   154       case LPX_DB:
   155       case LPX_FX:
   156 	lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
   157 	break;
   158       default: ;
   159 	//FIXME error
   160       }
   161     } else {
   162       switch (b) {
   163       case LPX_FR:
   164       case LPX_LO:
   165 	lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
   166 	break;
   167       case LPX_UP:	  
   168       case LPX_DB:
   169       case LPX_FX:
   170 	if (lo==up) 
   171 	  lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
   172 	else 
   173 	  lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
   174 	break;
   175       default: ;
   176 	//FIXME error
   177       }
   178     }
   179 
   180   }
   181   
   182   void LpGlpk::_setColUpperBound(int i, Value up)
   183   {
   184     if (up==-INF) {
   185       //FIXME error
   186     }
   187     int b=lpx_get_col_type(lp, i);
   188     double lo=lpx_get_col_lb(lp, i);
   189     if (up==INF) {
   190       switch (b) {
   191       case LPX_FR:
   192       case LPX_LO:
   193 	break;
   194       case LPX_UP:
   195 	lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
   196 	break;
   197       case LPX_DB:
   198       case LPX_FX:
   199 	lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
   200 	break;
   201       default: ;
   202 	//FIXME error
   203       }
   204     } else {
   205       switch (b) {
   206       case LPX_FR:
   207 	lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
   208 	break;
   209       case LPX_UP:
   210 	lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
   211 	break;
   212       case LPX_LO:
   213       case LPX_DB:
   214       case LPX_FX:
   215 	if (lo==up) 
   216 	  lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
   217 	else 
   218 	  lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
   219 	break;
   220       default: ;
   221 	//FIXME error
   222       }
   223     }
   224   }
   225   
   226 //   void LpGlpk::_setRowLowerBound(int i, Value lo)
   227 //   {
   228 //     if (lo==INF) {
   229 //       //FIXME error
   230 //     }
   231 //     int b=lpx_get_row_type(lp, i);
   232 //     double up=lpx_get_row_ub(lp, i);	
   233 //     if (lo==-INF) {
   234 //       switch (b) {
   235 //       case LPX_FR:
   236 //       case LPX_LO:
   237 // 	lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
   238 // 	break;
   239 //       case LPX_UP:
   240 // 	break;
   241 //       case LPX_DB:
   242 //       case LPX_FX:
   243 // 	lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
   244 // 	break;
   245 //       default: ;
   246 // 	//FIXME error
   247 //       }
   248 //     } else {
   249 //       switch (b) {
   250 //       case LPX_FR:
   251 //       case LPX_LO:
   252 // 	lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
   253 // 	break;
   254 //       case LPX_UP:	  
   255 //       case LPX_DB:
   256 //       case LPX_FX:
   257 // 	if (lo==up) 
   258 // 	  lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
   259 // 	else 
   260 // 	  lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
   261 // 	break;
   262 //       default: ;
   263 // 	//FIXME error
   264 //       }
   265 //     }
   266 //   }
   267   
   268 //   void LpGlpk::_setRowUpperBound(int i, Value up)
   269 //   {
   270 //     if (up==-INF) {
   271 //       //FIXME error
   272 //     }
   273 //     int b=lpx_get_row_type(lp, i);
   274 //     double lo=lpx_get_row_lb(lp, i);
   275 //     if (up==INF) {
   276 //       switch (b) {
   277 //       case LPX_FR:
   278 //       case LPX_LO:
   279 // 	break;
   280 //       case LPX_UP:
   281 // 	lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
   282 // 	break;
   283 //       case LPX_DB:
   284 //       case LPX_FX:
   285 // 	lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
   286 // 	break;
   287 //       default: ;
   288 // 	//FIXME error
   289 //       }
   290 //     } else {
   291 //       switch (b) {
   292 //       case LPX_FR:
   293 // 	lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
   294 // 	break;
   295 //       case LPX_UP:
   296 // 	lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
   297 // 	break;
   298 //       case LPX_LO:
   299 //       case LPX_DB:
   300 //       case LPX_FX:
   301 // 	if (lo==up) 
   302 // 	  lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
   303 // 	else 
   304 // 	  lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
   305 // 	break;
   306 //       default: ;
   307 // 	//FIXME error
   308 //       }
   309 //     }
   310 //   }
   311 
   312   void LpGlpk::_setRowBounds(int i, Value lb, Value ub)
   313   {
   314     //Bad parameter
   315     if (lb==INF || ub==-INF) {
   316       //FIXME error
   317     }
   318 
   319     if (lb == -INF){
   320       if (ub == INF){
   321 	lpx_set_row_bnds(lp, i, LPX_FR, lb, ub);
   322       }
   323       else{
   324 	lpx_set_row_bnds(lp, i, LPX_UP, lb, ub);
   325       }
   326     }
   327     else{
   328       if (ub==INF){
   329 	lpx_set_row_bnds(lp, i, LPX_LO, lb, ub);
   330 
   331       }
   332       else{
   333 	if (lb == ub){
   334 	  lpx_set_row_bnds(lp, i, LPX_FX, lb, ub);
   335 	}
   336 	else{
   337 	  lpx_set_row_bnds(lp, i, LPX_DB, lb, ub);
   338 	}
   339       }
   340     }
   341 
   342   }
   343   
   344   void LpGlpk::_setObjCoeff(int i, Value obj_coef)
   345   {
   346     //i=0 means the constant term (shift)
   347     lpx_set_obj_coef(lp, i, obj_coef);
   348   }
   349 
   350   void LpGlpk::_clearObj()
   351   {
   352     for (int i=0;i<=lpx_get_num_cols(lp);++i){
   353       lpx_set_obj_coef(lp, i, 0);
   354     }
   355   }
   356 //   void LpGlpk::_setObj(int length,
   357 // 		       int  const * indices, 
   358 // 		       Value  const * values )
   359 //   {
   360 //     Value new_values[1+lpx_num_cols()];
   361 //     for (i=0;i<=lpx_num_cols();++i){
   362 //       new_values[i]=0;
   363 //     }
   364 //     for (i=1;i<=length;++i){
   365 //       new_values[indices[i]]=values[i];
   366 //     }
   367     
   368 //     for (i=0;i<=lpx_num_cols();++i){
   369 //       lpx_set_obj_coef(lp, i, new_values[i]);
   370 //     }
   371 //   }
   372 
   373   LpGlpk::SolveExitStatus LpGlpk::_solve()
   374   {
   375     int i=  lpx_simplex(lp);
   376     switch (i) {
   377     case LPX_E_OK: 
   378       return SOLVED;
   379       break;
   380     default:
   381       return UNSOLVED;
   382     }
   383   }
   384 
   385   LpGlpk::Value LpGlpk::_getPrimal(int i)
   386   {
   387     return lpx_get_col_prim(lp,i);
   388   }
   389   
   390   LpGlpk::Value LpGlpk::_getPrimalValue()
   391   {
   392     return lpx_get_obj_val(lp);
   393   }
   394   
   395  
   396   LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()
   397   {
   398     int stat=  lpx_get_status(lp);
   399     switch (stat) {
   400     case LPX_UNDEF://Undefined (no solve has been run yet)
   401       return UNDEFINED;
   402       break;
   403     case LPX_NOFEAS://There is no feasible solution (primal, I guess)
   404     case LPX_INFEAS://Infeasible 
   405       return INFEASIBLE;
   406       break;
   407     case LPX_UNBND://Unbounded
   408       return INFINITE;
   409       break;
   410     case LPX_FEAS://Feasible
   411       return FEASIBLE;
   412       break;
   413     case LPX_OPT://Feasible
   414       return OPTIMAL;
   415       break;
   416     default:
   417       return UNDEFINED; //to avoid gcc warning
   418       //FIXME error
   419     }
   420   }
   421 
   422 
   423   void LpGlpk::_setMax()
   424   {
   425     lpx_set_obj_dir(lp, LPX_MAX);
   426   }
   427 
   428   void LpGlpk::_setMin()
   429   {
   430     lpx_set_obj_dir(lp, LPX_MIN);
   431   }
   432 
   433  
   434   void LpGlpk::messageLevel(int m)
   435   {
   436     lpx_set_int_parm(lp, LPX_K_MSGLEV, m);
   437   }
   438 
   439   void LpGlpk::presolver(bool b)
   440   {
   441     lpx_set_int_parm(lp, LPX_K_PRESOL, b);
   442   }
   443 
   444  
   445 } //END OF NAMESPACE LEMON
   446 
   447 #endif //LEMON_LP_GLPK_CC