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