Mercuriallemon-0.x / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
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
lemon-0.x