lemon-0.x: lemon/lp_glpk.cc@a979fcdda073

     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  */

    19 #ifndef LEMON_LP_GLPK_CC

    20 #define LEMON_LP_GLPK_CC

    22 ///\file

    23 ///\brief Implementation of the LEMON-GLPK lp solver interface.

    25 #include <lemon/lp_glpk.h>

    26 //#include <iostream>

    27 namespace lemon {

    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   }

    37   LpGlpk::~LpGlpk() {

    38     lpx_delete_prob(lp);

    39   }

    41   int LpGlpk::_addCol() {

    42     int i=lpx_add_cols(lp, 1);

    43     _setColLowerBound(i, -INF);

    44     _setColUpperBound(i, INF);

    45     return i;

    46   }

    48   ///\e

    51   LpSolverBase &LpGlpk::_newLp()

    52   {

    53     LpGlpk* newlp=new LpGlpk();

    54     return *newlp;

    55   }

    57   ///\e

    59   LpSolverBase &LpGlpk::_copyLp()

    60   {

    61     LpGlpk* newlp=new LpGlpk();

    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     }

    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));

    86     }

    88     return *newlp;

    89   }

    91   int LpGlpk::_addRow() {

    92     int i=lpx_add_rows(lp, 1);

    93     return i;

    94   }

    97   void LpGlpk::_eraseCol(int i) {

    98     int cols[2];

    99     cols[1]=i;

   100     lpx_del_cols(lp, 1, cols);

   101   }

   103   void LpGlpk::_eraseRow(int i) {

   104     int rows[2];

   105     rows[1]=i;

   106     lpx_del_rows(lp, 1, rows);

   107   }

   109   void LpGlpk::_getColName(int col, std::string & name)

   110   {

   112     char *n = lpx_get_col_name(lp,col);

   113     name = n?n:"";

   114   }

   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   }

   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   }

   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   }

   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)

   149     int mem_length=2+lpx_get_num_cols(lp);

   150     int* indices = new int[mem_length];

   151     Value* values = new Value[mem_length];

   154     int length=lpx_get_mat_row(lp, row, indices, values);

   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     }

   172     lpx_set_mat_row(lp, row, length, indices, values);

   173     delete [] indices;

   174     delete [] values;

   176   }

   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     }

   219   }

   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   }

   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 //   }

   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 //   }

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

   352   {

   353     //Bad parameter

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

   355       //FIXME error

   356     }

   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);

   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     }

   381   }

   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   }

   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 //     }

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

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

   409 //     }

   410 //   }

   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   }

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

   424   {

   425     return lpx_get_col_prim(lp,i);

   426   }

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

   429   {

   430     return lpx_get_row_dual(lp,i);

   431   }

   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   }

   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   }

   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;

   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   }

   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   }

   506   void LpGlpk::_setMax()

   507   {

   508     lpx_set_obj_dir(lp, LPX_MAX);

   509   }

   511   void LpGlpk::_setMin()

   512   {

   513     lpx_set_obj_dir(lp, LPX_MIN);

   514   }

   517   void LpGlpk::messageLevel(int m)

   518   {

   519     lpx_set_int_parm(lp, LPX_K_MSGLEV, m);

   520   }

   522   void LpGlpk::presolver(bool b)

   523   {

   524     lpx_set_int_parm(lp, LPX_K_PRESOL, b);

   525   }

   528 } //END OF NAMESPACE LEMON

   530 #endif //LEMON_LP_GLPK_CC

author	ladanyi
	Wed, 21 Jun 2006 08:35:23 +0000
changeset 2103	a979fcdda073
parent 1895	5b01801efbc0
child 2253	1645f6cc9667
permissions	-rw-r--r--