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, 18 Dec 2006 10:12:07 +0000
changeset 2330 9dccb1abc721
parent 2326 af8c695372be
child 2345 bfcaad2b84e8
permissions -rw-r--r--
Better handling of inexact computation.
We do not use tolerance for excess, just for edges 
     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   LpGlpk::Value LpGlpk::_getCoeff(int row, int col)

   217   {

   218 

   219     int length=lpx_get_mat_row(lp, row, 0, 0);

   220     

   221     std::vector<int> indices(length + 2);

   222     std::vector<Value> values(length + 2);

   223     

   224     lpx_get_mat_row(lp, row, &indices[0], &values[0]);

   225     

   226     //The following code does not suppose that the elements of the

   227     //array indices are sorted

   228     for (int i = 1; i <= length; ++i) {

   229       if (indices[i]==col){

   230 	return values[i];

   231       }

   232     }

   233     return 0;

   234 

   235   }

   236 

   237 

   238   void LpGlpk::_setColLowerBound(int i, Value lo)

   239   {

   240     if (lo==INF) {

   241       //FIXME error

   242     }

   243     int b=lpx_get_col_type(lp, i);

   244     double up=lpx_get_col_ub(lp, i);	

   245     if (lo==-INF) {

   246       switch (b) {

   247       case LPX_FR:

   248       case LPX_LO:

   249 	lpx_set_col_bnds(lp, i, LPX_FR, lo, up);

   250 	break;

   251       case LPX_UP:

   252 	break;

   253       case LPX_DB:

   254       case LPX_FX:

   255 	lpx_set_col_bnds(lp, i, LPX_UP, lo, up);

   256 	break;

   257       default: ;

   258 	//FIXME error

   259       }

   260     } else {

   261       switch (b) {

   262       case LPX_FR:

   263       case LPX_LO:

   264 	lpx_set_col_bnds(lp, i, LPX_LO, lo, up);

   265 	break;

   266       case LPX_UP:	  

   267       case LPX_DB:

   268       case LPX_FX:

   269 	if (lo==up) 

   270 	  lpx_set_col_bnds(lp, i, LPX_FX, lo, up);

   271 	else 

   272 	  lpx_set_col_bnds(lp, i, LPX_DB, lo, up);

   273 	break;

   274       default: ;

   275 	//FIXME error

   276       }

   277     }

   278 

   279   }

   280 

   281   LpGlpk::Value LpGlpk::_getColLowerBound(int i)

   282   {

   283     int b=lpx_get_col_type(lp, i);

   284       switch (b) {

   285       case LPX_LO:

   286       case LPX_DB:

   287       case LPX_FX:

   288 	return lpx_get_col_lb(lp, i);	

   289       default: ;

   290 	return -INF;

   291       }

   292   }

   293   

   294   void LpGlpk::_setColUpperBound(int i, Value up)

   295   {

   296     if (up==-INF) {

   297       //FIXME error

   298     }

   299     int b=lpx_get_col_type(lp, i);

   300     double lo=lpx_get_col_lb(lp, i);

   301     if (up==INF) {

   302       switch (b) {

   303       case LPX_FR:

   304       case LPX_LO:

   305 	break;

   306       case LPX_UP:

   307 	lpx_set_col_bnds(lp, i, LPX_FR, lo, up);

   308 	break;

   309       case LPX_DB:

   310       case LPX_FX:

   311 	lpx_set_col_bnds(lp, i, LPX_LO, lo, up);

   312 	break;

   313       default: ;

   314 	//FIXME error

   315       }

   316     } else {

   317       switch (b) {

   318       case LPX_FR:

   319 	lpx_set_col_bnds(lp, i, LPX_UP, lo, up);

   320 	break;

   321       case LPX_UP:

   322 	lpx_set_col_bnds(lp, i, LPX_UP, lo, up);

   323 	break;

   324       case LPX_LO:

   325       case LPX_DB:

   326       case LPX_FX:

   327 	if (lo==up) 

   328 	  lpx_set_col_bnds(lp, i, LPX_FX, lo, up);

   329 	else 

   330 	  lpx_set_col_bnds(lp, i, LPX_DB, lo, up);

   331 	break;

   332       default: ;

   333 	//FIXME error

   334       }

   335     }

   336   }

   337 

   338   LpGlpk::Value LpGlpk::_getColUpperBound(int i)

   339   {

   340     int b=lpx_get_col_type(lp, i);

   341       switch (b) {

   342       case LPX_UP:

   343       case LPX_DB:

   344       case LPX_FX:

   345 	return lpx_get_col_ub(lp, i);	

   346       default: ;

   347 	return INF;

   348       }

   349   }

   350   

   351 //   void LpGlpk::_setRowLowerBound(int i, Value lo)

   352 //   {

   353 //     if (lo==INF) {

   354 //       //FIXME error

   355 //     }

   356 //     int b=lpx_get_row_type(lp, i);

   357 //     double up=lpx_get_row_ub(lp, i);	

   358 //     if (lo==-INF) {

   359 //       switch (b) {

   360 //       case LPX_FR:

   361 //       case LPX_LO:

   362 // 	lpx_set_row_bnds(lp, i, LPX_FR, lo, up);

   363 // 	break;

   364 //       case LPX_UP:

   365 // 	break;

   366 //       case LPX_DB:

   367 //       case LPX_FX:

   368 // 	lpx_set_row_bnds(lp, i, LPX_UP, lo, up);

   369 // 	break;

   370 //       default: ;

   371 // 	//FIXME error

   372 //       }

   373 //     } else {

   374 //       switch (b) {

   375 //       case LPX_FR:

   376 //       case LPX_LO:

   377 // 	lpx_set_row_bnds(lp, i, LPX_LO, lo, up);

   378 // 	break;

   379 //       case LPX_UP:	  

   380 //       case LPX_DB:

   381 //       case LPX_FX:

   382 // 	if (lo==up) 

   383 // 	  lpx_set_row_bnds(lp, i, LPX_FX, lo, up);

   384 // 	else 

   385 // 	  lpx_set_row_bnds(lp, i, LPX_DB, lo, up);

   386 // 	break;

   387 //       default: ;

   388 // 	//FIXME error

   389 //       }

   390 //     }

   391 //   }

   392   

   393 //   void LpGlpk::_setRowUpperBound(int i, Value up)

   394 //   {

   395 //     if (up==-INF) {

   396 //       //FIXME error

   397 //     }

   398 //     int b=lpx_get_row_type(lp, i);

   399 //     double lo=lpx_get_row_lb(lp, i);

   400 //     if (up==INF) {

   401 //       switch (b) {

   402 //       case LPX_FR:

   403 //       case LPX_LO:

   404 // 	break;

   405 //       case LPX_UP:

   406 // 	lpx_set_row_bnds(lp, i, LPX_FR, lo, up);

   407 // 	break;

   408 //       case LPX_DB:

   409 //       case LPX_FX:

   410 // 	lpx_set_row_bnds(lp, i, LPX_LO, lo, up);

   411 // 	break;

   412 //       default: ;

   413 // 	//FIXME error

   414 //       }

   415 //     } else {

   416 //       switch (b) {

   417 //       case LPX_FR:

   418 // 	lpx_set_row_bnds(lp, i, LPX_UP, lo, up);

   419 // 	break;

   420 //       case LPX_UP:

   421 // 	lpx_set_row_bnds(lp, i, LPX_UP, lo, up);

   422 // 	break;

   423 //       case LPX_LO:

   424 //       case LPX_DB:

   425 //       case LPX_FX:

   426 // 	if (lo==up) 

   427 // 	  lpx_set_row_bnds(lp, i, LPX_FX, lo, up);

   428 // 	else 

   429 // 	  lpx_set_row_bnds(lp, i, LPX_DB, lo, up);

   430 // 	break;

   431 //       default: ;

   432 // 	//FIXME error

   433 //       }

   434 //     }

   435 //   }

   436 

   437   void LpGlpk::_setRowBounds(int i, Value lb, Value ub)

   438   {

   439     //Bad parameter

   440     if (lb==INF || ub==-INF) {

   441       //FIXME error

   442     }

   443 

   444     if (lb == -INF){

   445       if (ub == INF){

   446 	lpx_set_row_bnds(lp, i, LPX_FR, lb, ub);

   447       }

   448       else{

   449 	lpx_set_row_bnds(lp, i, LPX_UP, lb, ub);

   450       }

   451     }

   452     else{

   453       if (ub==INF){

   454 	lpx_set_row_bnds(lp, i, LPX_LO, lb, ub);

   455 

   456       }

   457       else{

   458 	if (lb == ub){

   459 	  lpx_set_row_bnds(lp, i, LPX_FX, lb, ub);

   460 	}

   461 	else{

   462 	  lpx_set_row_bnds(lp, i, LPX_DB, lb, ub);

   463 	}

   464       }

   465     }

   466 

   467   }

   468 

   469   void LpGlpk::_getRowBounds(int i, Value &lb, Value &ub)

   470   {

   471 

   472     int b=lpx_get_row_type(lp, i);

   473     switch (b) {

   474     case LPX_FR:

   475     case LPX_UP:

   476       lb = -INF;

   477 	break;

   478     default: 

   479       lb=lpx_get_row_lb(lp, i);

   480     }

   481 

   482     switch (b) {

   483     case LPX_FR:

   484     case LPX_LO:

   485       ub = INF;

   486 	break;

   487     default: 

   488       ub=lpx_get_row_ub(lp, i);

   489     }

   490     

   491   }

   492   

   493   void LpGlpk::_setObjCoeff(int i, Value obj_coef)

   494   {

   495     //i=0 means the constant term (shift)

   496     lpx_set_obj_coef(lp, i, obj_coef);

   497   }

   498 

   499   LpGlpk::Value LpGlpk::_getObjCoeff(int i){

   500     //i=0 means the constant term (shift)

   501     return lpx_get_obj_coef(lp, i);

   502   }

   503 

   504   void LpGlpk::_clearObj()

   505   {

   506     for (int i=0;i<=lpx_get_num_cols(lp);++i){

   507       lpx_set_obj_coef(lp, i, 0);

   508     }

   509   }

   510 //   void LpGlpk::_setObj(int length,

   511 // 		       int  const * indices, 

   512 // 		       Value  const * values )

   513 //   {

   514 //     Value new_values[1+lpx_num_cols()];

   515 //     for (i=0;i<=lpx_num_cols();++i){

   516 //       new_values[i]=0;

   517 //     }

   518 //     for (i=1;i<=length;++i){

   519 //       new_values[indices[i]]=values[i];

   520 //     }

   521     

   522 //     for (i=0;i<=lpx_num_cols();++i){

   523 //       lpx_set_obj_coef(lp, i, new_values[i]);

   524 //     }

   525 //   }

   526 

   527   LpGlpk::SolveExitStatus LpGlpk::_solve()

   528   {

   529     int i =  lpx_simplex(lp);

   530     switch (i) {

   531     case LPX_E_OK: 

   532       return SOLVED;

   533     default:

   534       return UNSOLVED;

   535     }

   536   }

   537 

   538   LpGlpk::Value LpGlpk::_getPrimal(int i)

   539   {

   540     return lpx_get_col_prim(lp,i);

   541   }

   542 

   543   LpGlpk::Value LpGlpk::_getDual(int i)

   544   {

   545     return lpx_get_row_dual(lp,i);

   546   }

   547   

   548   LpGlpk::Value LpGlpk::_getPrimalValue()

   549   {

   550     return lpx_get_obj_val(lp);

   551   }

   552   bool LpGlpk::_isBasicCol(int i) {

   553     return (lpx_get_col_stat(lp, i)==LPX_BS);

   554   }

   555   

   556  

   557   LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()

   558   {

   559     int stat=  lpx_get_status(lp);

   560     switch (stat) {

   561     case LPX_UNDEF://Undefined (no solve has been run yet)

   562       return UNDEFINED;

   563     case LPX_NOFEAS://There is no feasible solution (primal, I guess)

   564     case LPX_INFEAS://Infeasible 

   565       return INFEASIBLE;

   566     case LPX_UNBND://Unbounded

   567       return INFINITE;

   568     case LPX_FEAS://Feasible

   569       return FEASIBLE;

   570     case LPX_OPT://Feasible

   571       return OPTIMAL;

   572     default:

   573       return UNDEFINED; //to avoid gcc warning

   574       //FIXME error

   575     }

   576   }

   577 

   578   LpGlpk::SolutionStatus LpGlpk::_getDualStatus()

   579   {

   580 //     std::cout<<"Itt megy: "<<lpx_get_dual_stat(lp)<<std::endl;

   581 //     std::cout<<"Itt a primal: "<<lpx_get_prim_stat(lp)<<std::endl;

   582 

   583     switch (lpx_get_dual_stat(lp)) {

   584     case LPX_D_UNDEF://Undefined (no solve has been run yet)

   585       return UNDEFINED;

   586     case LPX_D_NOFEAS://There is no dual feasible solution 

   587 //    case LPX_D_INFEAS://Infeasible 

   588       return INFEASIBLE;

   589     case LPX_D_FEAS://Feasible    

   590       switch (lpx_get_status(lp)) {

   591       case LPX_NOFEAS:

   592 	return INFINITE;

   593       case LPX_OPT:

   594 	return OPTIMAL;

   595       default:

   596 	return FEASIBLE;

   597       }

   598     default:

   599       return UNDEFINED; //to avoid gcc warning

   600       //FIXME error

   601     }

   602   }

   603 

   604   LpGlpk::ProblemTypes LpGlpk::_getProblemType()

   605   {

   606       //int stat=  lpx_get_status(lp);

   607     int statp=  lpx_get_prim_stat(lp);

   608     int statd=  lpx_get_dual_stat(lp);

   609     if (statp==LPX_P_FEAS && statd==LPX_D_FEAS)

   610 	return PRIMAL_DUAL_FEASIBLE;

   611     if (statp==LPX_P_FEAS && statd==LPX_D_NOFEAS)

   612 	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

   613     if (statp==LPX_P_NOFEAS && statd==LPX_D_FEAS)

   614 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;

   615     if (statp==LPX_P_NOFEAS && statd==LPX_D_NOFEAS)

   616 	return PRIMAL_DUAL_INFEASIBLE;

   617     //In all other cases

   618     return UNKNOWN;

   619   }

   620 

   621   void LpGlpk::_setMax()

   622   {

   623     lpx_set_obj_dir(lp, LPX_MAX);

   624   }

   625 

   626   void LpGlpk::_setMin()

   627   {

   628     lpx_set_obj_dir(lp, LPX_MIN);

   629   }

   630 

   631   bool LpGlpk::_isMax()

   632   {

   633     return (lpx_get_obj_dir(lp)==LPX_MAX);

   634   }

   635 

   636  

   637 

   638   void LpGlpk::messageLevel(int m)

   639   {

   640     lpx_set_int_parm(lp, LPX_K_MSGLEV, m);

   641   }

   642 

   643   void LpGlpk::presolver(bool b)

   644   {

   645     lpx_set_int_parm(lp, LPX_K_PRESOL, b);

   646   }

   647 

   648  

   649 } //END OF NAMESPACE LEMON
lemon-0.x