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