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