lemon/lp_glpk.cc
author deba
Mon, 12 Sep 2005 09:19:52 +0000
changeset 1680 4f8b9cee576b
parent 1473 876c7b7f4dae
child 1787 932b8490caf0
permissions -rw-r--r--
Fixing and improving GridGraph
     1 /* -*- C++ -*-
     2  * 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 //#include <iostream>
    25 namespace lemon {
    26 
    27 
    28   LpGlpk::LpGlpk() : Parent(), 
    29 		     lp(lpx_create_prob()) {
    30     ///\todo constrol function for this:
    31     lpx_set_int_parm(lp, LPX_K_DUAL, 1);
    32     messageLevel(0);
    33   }
    34   
    35   LpGlpk::~LpGlpk() {
    36     lpx_delete_prob(lp);
    37   }
    38   
    39   int LpGlpk::_addCol() { 
    40     int i=lpx_add_cols(lp, 1);
    41     _setColLowerBound(i, -INF);
    42     _setColUpperBound(i, INF);
    43     return i;
    44   }
    45 
    46   ///\e
    47 
    48 
    49   LpSolverBase &LpGlpk::_newLp()
    50   {
    51     LpGlpk* newlp=new LpGlpk();
    52     return *newlp;
    53   }
    54   
    55   ///\e
    56 
    57   LpSolverBase &LpGlpk::_copyLp()
    58   {
    59     LpGlpk* newlp=new LpGlpk();
    60 
    61     //Coefficient matrix, row bounds
    62     lpx_add_rows(newlp->lp, lpx_get_num_rows(lp));
    63     lpx_add_cols(newlp->lp, lpx_get_num_cols(lp));
    64     int len;
    65     int ind[1+lpx_get_num_cols(lp)];
    66     Value val[1+lpx_get_num_cols(lp)];
    67     for (int i=1;i<=lpx_get_num_rows(lp);++i){
    68       len=lpx_get_mat_row(lp,i,ind,val);
    69       lpx_set_mat_row(newlp->lp, i,len,ind,val);
    70       lpx_set_row_bnds(newlp->lp,i,lpx_get_row_type(lp,i),
    71 		       lpx_get_row_lb(lp,i),lpx_get_row_ub(lp,i));
    72     }
    73 
    74     //Objective function, coloumn bounds
    75     lpx_set_obj_dir(newlp->lp, lpx_get_obj_dir(lp));
    76     //Objectif function's constant term treated separately
    77     lpx_set_obj_coef(newlp->lp,0,lpx_get_obj_coef(lp,0));
    78     for (int i=1;i<=lpx_get_num_cols(lp);++i){
    79       lpx_set_obj_coef(newlp->lp,i,lpx_get_obj_coef(lp,i));
    80       lpx_set_col_bnds(newlp->lp,i,lpx_get_col_type(lp,i),
    81 		       lpx_get_col_lb(lp,i),lpx_get_col_ub(lp,i));
    82       
    83       
    84     }
    85 
    86     return *newlp;
    87   }
    88 
    89   int LpGlpk::_addRow() { 
    90     int i=lpx_add_rows(lp, 1);
    91     return i;
    92   }
    93 
    94   
    95   void LpGlpk::_eraseCol(int i) {
    96     int cols[2];
    97     cols[1]=i;
    98     lpx_del_cols(lp, 1, cols);
    99   }
   100   
   101   void LpGlpk::_eraseRow(int i) {
   102     int rows[2];
   103     rows[1]=i;
   104     lpx_del_rows(lp, 1, rows);
   105   }
   106 
   107   void LpGlpk::_setRowCoeffs(int i, 
   108 			     int length,
   109 			     const int   * indices, 
   110 			     const Value   * values )
   111   {
   112     lpx_set_mat_row(lp, i, length,
   113 		    const_cast<int * >(indices) ,
   114 		    const_cast<Value * >(values));
   115   }
   116   
   117   void LpGlpk::_setColCoeffs(int i, 
   118 			     int length,
   119 			     const int   * indices, 
   120 			     const Value   * values)
   121   {
   122     lpx_set_mat_col(lp, i, length,
   123 		    const_cast<int * >(indices),
   124 		    const_cast<Value * >(values));
   125   }
   126 
   127 
   128   void LpGlpk::_setCoeff(int row, int col, Value value) 
   129   {
   130     ///FIXME Of course this is not efficient at all, but GLPK knows not more.
   131     // First approach: get one row, apply changes and set it again
   132     //(one idea to improve this: maybe it is better to do this with 1 coloumn)
   133     
   134     int mem_length=2+lpx_get_num_cols(lp);
   135     int* indices = new int[mem_length];
   136     Value* values = new Value[mem_length];
   137     
   138 
   139     int length=lpx_get_mat_row(lp, row, indices, values);
   140 
   141     //The following code does not suppose that the elements of the array indices are sorted
   142     int i=1;
   143     bool found=false;
   144     while (i <= length && !found){
   145       if (indices[i]==col){
   146 	found = true;
   147 	values[i]=value;
   148       }
   149       ++i;
   150     }
   151     if (!found){
   152       ++length;
   153       indices[length]=col;
   154       values[length]=value;
   155     }
   156     
   157     lpx_set_mat_row(lp, row, length, indices, values);
   158     delete [] indices;
   159     delete [] values;
   160     
   161   }
   162 
   163   void LpGlpk::_setColLowerBound(int i, Value lo)
   164   {
   165     if (lo==INF) {
   166       //FIXME error
   167     }
   168     int b=lpx_get_col_type(lp, i);
   169     double up=lpx_get_col_ub(lp, i);	
   170     if (lo==-INF) {
   171       switch (b) {
   172       case LPX_FR:
   173       case LPX_LO:
   174 	lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
   175 	break;
   176       case LPX_UP:
   177 	break;
   178       case LPX_DB:
   179       case LPX_FX:
   180 	lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
   181 	break;
   182       default: ;
   183 	//FIXME error
   184       }
   185     } else {
   186       switch (b) {
   187       case LPX_FR:
   188       case LPX_LO:
   189 	lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
   190 	break;
   191       case LPX_UP:	  
   192       case LPX_DB:
   193       case LPX_FX:
   194 	if (lo==up) 
   195 	  lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
   196 	else 
   197 	  lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
   198 	break;
   199       default: ;
   200 	//FIXME error
   201       }
   202     }
   203 
   204   }
   205   
   206   void LpGlpk::_setColUpperBound(int i, Value up)
   207   {
   208     if (up==-INF) {
   209       //FIXME error
   210     }
   211     int b=lpx_get_col_type(lp, i);
   212     double lo=lpx_get_col_lb(lp, i);
   213     if (up==INF) {
   214       switch (b) {
   215       case LPX_FR:
   216       case LPX_LO:
   217 	break;
   218       case LPX_UP:
   219 	lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
   220 	break;
   221       case LPX_DB:
   222       case LPX_FX:
   223 	lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
   224 	break;
   225       default: ;
   226 	//FIXME error
   227       }
   228     } else {
   229       switch (b) {
   230       case LPX_FR:
   231 	lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
   232 	break;
   233       case LPX_UP:
   234 	lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
   235 	break;
   236       case LPX_LO:
   237       case LPX_DB:
   238       case LPX_FX:
   239 	if (lo==up) 
   240 	  lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
   241 	else 
   242 	  lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
   243 	break;
   244       default: ;
   245 	//FIXME error
   246       }
   247     }
   248   }
   249   
   250 //   void LpGlpk::_setRowLowerBound(int i, Value lo)
   251 //   {
   252 //     if (lo==INF) {
   253 //       //FIXME error
   254 //     }
   255 //     int b=lpx_get_row_type(lp, i);
   256 //     double up=lpx_get_row_ub(lp, i);	
   257 //     if (lo==-INF) {
   258 //       switch (b) {
   259 //       case LPX_FR:
   260 //       case LPX_LO:
   261 // 	lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
   262 // 	break;
   263 //       case LPX_UP:
   264 // 	break;
   265 //       case LPX_DB:
   266 //       case LPX_FX:
   267 // 	lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
   268 // 	break;
   269 //       default: ;
   270 // 	//FIXME error
   271 //       }
   272 //     } else {
   273 //       switch (b) {
   274 //       case LPX_FR:
   275 //       case LPX_LO:
   276 // 	lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
   277 // 	break;
   278 //       case LPX_UP:	  
   279 //       case LPX_DB:
   280 //       case LPX_FX:
   281 // 	if (lo==up) 
   282 // 	  lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
   283 // 	else 
   284 // 	  lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
   285 // 	break;
   286 //       default: ;
   287 // 	//FIXME error
   288 //       }
   289 //     }
   290 //   }
   291   
   292 //   void LpGlpk::_setRowUpperBound(int i, Value up)
   293 //   {
   294 //     if (up==-INF) {
   295 //       //FIXME error
   296 //     }
   297 //     int b=lpx_get_row_type(lp, i);
   298 //     double lo=lpx_get_row_lb(lp, i);
   299 //     if (up==INF) {
   300 //       switch (b) {
   301 //       case LPX_FR:
   302 //       case LPX_LO:
   303 // 	break;
   304 //       case LPX_UP:
   305 // 	lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
   306 // 	break;
   307 //       case LPX_DB:
   308 //       case LPX_FX:
   309 // 	lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
   310 // 	break;
   311 //       default: ;
   312 // 	//FIXME error
   313 //       }
   314 //     } else {
   315 //       switch (b) {
   316 //       case LPX_FR:
   317 // 	lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
   318 // 	break;
   319 //       case LPX_UP:
   320 // 	lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
   321 // 	break;
   322 //       case LPX_LO:
   323 //       case LPX_DB:
   324 //       case LPX_FX:
   325 // 	if (lo==up) 
   326 // 	  lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
   327 // 	else 
   328 // 	  lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
   329 // 	break;
   330 //       default: ;
   331 // 	//FIXME error
   332 //       }
   333 //     }
   334 //   }
   335 
   336   void LpGlpk::_setRowBounds(int i, Value lb, Value ub)
   337   {
   338     //Bad parameter
   339     if (lb==INF || ub==-INF) {
   340       //FIXME error
   341     }
   342 
   343     if (lb == -INF){
   344       if (ub == INF){
   345 	lpx_set_row_bnds(lp, i, LPX_FR, lb, ub);
   346       }
   347       else{
   348 	lpx_set_row_bnds(lp, i, LPX_UP, lb, ub);
   349       }
   350     }
   351     else{
   352       if (ub==INF){
   353 	lpx_set_row_bnds(lp, i, LPX_LO, lb, ub);
   354 
   355       }
   356       else{
   357 	if (lb == ub){
   358 	  lpx_set_row_bnds(lp, i, LPX_FX, lb, ub);
   359 	}
   360 	else{
   361 	  lpx_set_row_bnds(lp, i, LPX_DB, lb, ub);
   362 	}
   363       }
   364     }
   365 
   366   }
   367   
   368   void LpGlpk::_setObjCoeff(int i, Value obj_coef)
   369   {
   370     //i=0 means the constant term (shift)
   371     lpx_set_obj_coef(lp, i, obj_coef);
   372   }
   373 
   374   void LpGlpk::_clearObj()
   375   {
   376     for (int i=0;i<=lpx_get_num_cols(lp);++i){
   377       lpx_set_obj_coef(lp, i, 0);
   378     }
   379   }
   380 //   void LpGlpk::_setObj(int length,
   381 // 		       int  const * indices, 
   382 // 		       Value  const * values )
   383 //   {
   384 //     Value new_values[1+lpx_num_cols()];
   385 //     for (i=0;i<=lpx_num_cols();++i){
   386 //       new_values[i]=0;
   387 //     }
   388 //     for (i=1;i<=length;++i){
   389 //       new_values[indices[i]]=values[i];
   390 //     }
   391     
   392 //     for (i=0;i<=lpx_num_cols();++i){
   393 //       lpx_set_obj_coef(lp, i, new_values[i]);
   394 //     }
   395 //   }
   396 
   397   LpGlpk::SolveExitStatus LpGlpk::_solve()
   398   {
   399     int i =  lpx_simplex(lp);
   400     switch (i) {
   401     case LPX_E_OK: 
   402       return SOLVED;
   403     default:
   404       return UNSOLVED;
   405     }
   406   }
   407 
   408   LpGlpk::Value LpGlpk::_getPrimal(int i)
   409   {
   410     return lpx_get_col_prim(lp,i);
   411   }
   412   
   413   LpGlpk::Value LpGlpk::_getPrimalValue()
   414   {
   415     return lpx_get_obj_val(lp);
   416   }
   417   
   418  
   419   LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()
   420   {
   421     int stat=  lpx_get_status(lp);
   422     switch (stat) {
   423     case LPX_UNDEF://Undefined (no solve has been run yet)
   424       return UNDEFINED;
   425     case LPX_NOFEAS://There is no feasible solution (primal, I guess)
   426     case LPX_INFEAS://Infeasible 
   427       return INFEASIBLE;
   428     case LPX_UNBND://Unbounded
   429       return INFINITE;
   430     case LPX_FEAS://Feasible
   431       return FEASIBLE;
   432     case LPX_OPT://Feasible
   433       return OPTIMAL;
   434     default:
   435       return UNDEFINED; //to avoid gcc warning
   436       //FIXME error
   437     }
   438   }
   439 
   440   LpGlpk::SolutionStatus LpGlpk::_getDualStatus()
   441   {
   442 //     std::cout<<"Itt megy: "<<lpx_get_dual_stat(lp)<<std::endl;
   443 //     std::cout<<"Itt a primal: "<<lpx_get_prim_stat(lp)<<std::endl;
   444 
   445     switch (lpx_get_dual_stat(lp)) {
   446     case LPX_D_UNDEF://Undefined (no solve has been run yet)
   447       return UNDEFINED;
   448     case LPX_D_NOFEAS://There is no dual feasible solution 
   449 //    case LPX_D_INFEAS://Infeasible 
   450       return INFEASIBLE;
   451     case LPX_D_FEAS://Feasible    
   452       switch (lpx_get_status(lp)) {
   453       case LPX_NOFEAS:
   454 	return INFINITE;
   455       case LPX_OPT:
   456 	return OPTIMAL;
   457       default:
   458 	return FEASIBLE;
   459       }
   460     default:
   461       return UNDEFINED; //to avoid gcc warning
   462       //FIXME error
   463     }
   464   }
   465 
   466   LpGlpk::ProblemTypes LpGlpk::_getProblemType()
   467   {
   468       //int stat=  lpx_get_status(lp);
   469     int statp=  lpx_get_prim_stat(lp);
   470     int statd=  lpx_get_dual_stat(lp);
   471     if (statp==LPX_P_FEAS && statd==LPX_D_FEAS)
   472 	return PRIMAL_DUAL_FEASIBLE;
   473     if (statp==LPX_P_FEAS && statd==LPX_D_NOFEAS)
   474 	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
   475     if (statp==LPX_P_NOFEAS && statd==LPX_D_FEAS)
   476 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
   477     if (statp==LPX_P_NOFEAS && statd==LPX_D_NOFEAS)
   478 	return PRIMAL_DUAL_INFEASIBLE;
   479     //In all other cases
   480     return UNKNOWN;
   481   }
   482 
   483   void LpGlpk::_setMax()
   484   {
   485     lpx_set_obj_dir(lp, LPX_MAX);
   486   }
   487 
   488   void LpGlpk::_setMin()
   489   {
   490     lpx_set_obj_dir(lp, LPX_MIN);
   491   }
   492 
   493  
   494   void LpGlpk::messageLevel(int m)
   495   {
   496     lpx_set_int_parm(lp, LPX_K_MSGLEV, m);
   497   }
   498 
   499   void LpGlpk::presolver(bool b)
   500   {
   501     lpx_set_int_parm(lp, LPX_K_PRESOL, b);
   502   }
   503 
   504  
   505 } //END OF NAMESPACE LEMON
   506 
   507 #endif //LEMON_LP_GLPK_CC