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

     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 ///\file

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

    22 #include <lemon/lp_glpk.h>

    23 //#include <iostream>

    24 namespace lemon {

    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   }

    34   LpGlpk::~LpGlpk() {

    35     lpx_delete_prob(lp);

    36   }

    38   int LpGlpk::_addCol() {

    39     int i=lpx_add_cols(lp, 1);

    40     _setColLowerBound(i, -INF);

    41     _setColUpperBound(i, INF);

    42     return i;

    43   }

    45   ///\e

    48   LpSolverBase &LpGlpk::_newLp()

    49   {

    50     LpGlpk* newlp=new LpGlpk();

    51     return *newlp;

    52   }

    54   ///\e

    56   LpSolverBase &LpGlpk::_copyLp()

    57   {

    58     LpGlpk* newlp=new LpGlpk();

    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     }

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

    83     }

    85     return *newlp;

    86   }

    88   int LpGlpk::_addRow() {

    89     int i=lpx_add_rows(lp, 1);

    90     return i;

    91   }

    94   void LpGlpk::_eraseCol(int i) {

    95     int cols[2];

    96     cols[1]=i;

    97     lpx_del_cols(lp, 1, cols);

    98   }

   100   void LpGlpk::_eraseRow(int i) {

   101     int rows[2];

   102     rows[1]=i;

   103     lpx_del_rows(lp, 1, rows);

   104   }

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

   107   {

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

   110     name = n?n:"";

   111   }

   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   }

   119   void LpGlpk::_setRowCoeffs(int i, LpRowIterator b, LpRowIterator e)

   120   {

   121     std::vector<int> indices;

   122     std::vector<Value> values;

   124     indices.push_back(0);

   125     values.push_back(0);

   127     for(LpRowIterator it=b; it!=e; ++it) {

   128       indices.push_back(it->first);

   129       values.push_back(it->second);

   130     }

   132     lpx_set_mat_row(lp, i, values.size() - 1, &indices[0], &values[0]);

   133   }

   135   void LpGlpk::_setColCoeffs(int i, LpColIterator b, LpColIterator e) {

   137     std::vector<int> indices;

   138     std::vector<Value> values;

   140     indices.push_back(0);

   141     values.push_back(0);

   143     for(LpColIterator it=b; it!=e; ++it) {

   144       indices.push_back(it->first);

   145       values.push_back(it->second);

   146     }

   148     lpx_set_mat_col(lp, i, values.size() - 1, &indices[0], &values[0]);

   149   }

   152   void LpGlpk::_setCoeff(int row, int col, Value value)

   153   {

   155     if (lpx_get_num_cols(lp) < lpx_get_num_rows(lp)) {

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

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

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

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

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

   165       //array indices are sorted

   166       bool found=false;

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

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

   169           found=true;

   170           values[i]=value;

   171           break;

   172         }

   173       }

   174       if (!found){

   175         ++length;

   176         indices[length]=col;

   177         values[length]=value;

   178       }

   180       lpx_set_mat_row(lp, row, length, &indices[0], &values[0]);

   182     } else {

   184       int length=lpx_get_mat_col(lp, col, 0, 0);

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

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

   189       lpx_get_mat_col(lp, col, &indices[0], &values[0]);

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

   192       //array indices are sorted

   193       bool found=false;

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

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

   196           found=true;

   197           values[i]=value;

   198           break;

   199         }

   200       }

   201       if (!found){

   202         ++length;

   203         indices[length]=row;

   204         values[length]=value;

   205       }

   207       lpx_set_mat_col(lp, col, length, &indices[0], &values[0]);

   208     }

   209   }

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

   212   {

   213     if (lo==INF) {

   214       //FIXME error

   215     }

   216     int b=lpx_get_col_type(lp, i);

   217     double up=lpx_get_col_ub(lp, i);

   218     if (lo==-INF) {

   219       switch (b) {

   220       case LPX_FR:

   221       case LPX_LO:

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

   223 	break;

   224       case LPX_UP:

   225 	break;

   226       case LPX_DB:

   227       case LPX_FX:

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

   229 	break;

   230       default: ;

   231 	//FIXME error

   232       }

   233     } else {

   234       switch (b) {

   235       case LPX_FR:

   236       case LPX_LO:

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

   238 	break;

   239       case LPX_UP:

   240       case LPX_DB:

   241       case LPX_FX:

   242 	if (lo==up)

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

   244 	else

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

   246 	break;

   247       default: ;

   248 	//FIXME error

   249       }

   250     }

   252   }

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

   255   {

   256     if (up==-INF) {

   257       //FIXME error

   258     }

   259     int b=lpx_get_col_type(lp, i);

   260     double lo=lpx_get_col_lb(lp, i);

   261     if (up==INF) {

   262       switch (b) {

   263       case LPX_FR:

   264       case LPX_LO:

   265 	break;

   266       case LPX_UP:

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

   268 	break;

   269       case LPX_DB:

   270       case LPX_FX:

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

   272 	break;

   273       default: ;

   274 	//FIXME error

   275       }

   276     } else {

   277       switch (b) {

   278       case LPX_FR:

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

   280 	break;

   281       case LPX_UP:

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

   283 	break;

   284       case LPX_LO:

   285       case LPX_DB:

   286       case LPX_FX:

   287 	if (lo==up)

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

   289 	else

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

   291 	break;

   292       default: ;

   293 	//FIXME error

   294       }

   295     }

   296   }

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

   299 //   {

   300 //     if (lo==INF) {

   301 //       //FIXME error

   302 //     }

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

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

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

   306 //       switch (b) {

   307 //       case LPX_FR:

   308 //       case LPX_LO:

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

   310 // 	break;

   311 //       case LPX_UP:

   312 // 	break;

   313 //       case LPX_DB:

   314 //       case LPX_FX:

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

   316 // 	break;

   317 //       default: ;

   318 // 	//FIXME error

   319 //       }

   320 //     } else {

   321 //       switch (b) {

   322 //       case LPX_FR:

   323 //       case LPX_LO:

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

   325 // 	break;

   326 //       case LPX_UP:

   327 //       case LPX_DB:

   328 //       case LPX_FX:

   329 // 	if (lo==up)

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

   331 // 	else

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

   333 // 	break;

   334 //       default: ;

   335 // 	//FIXME error

   336 //       }

   337 //     }

   338 //   }

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

   341 //   {

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

   343 //       //FIXME error

   344 //     }

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

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

   347 //     if (up==INF) {

   348 //       switch (b) {

   349 //       case LPX_FR:

   350 //       case LPX_LO:

   351 // 	break;

   352 //       case LPX_UP:

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

   354 // 	break;

   355 //       case LPX_DB:

   356 //       case LPX_FX:

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

   358 // 	break;

   359 //       default: ;

   360 // 	//FIXME error

   361 //       }

   362 //     } else {

   363 //       switch (b) {

   364 //       case LPX_FR:

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

   366 // 	break;

   367 //       case LPX_UP:

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

   369 // 	break;

   370 //       case LPX_LO:

   371 //       case LPX_DB:

   372 //       case LPX_FX:

   373 // 	if (lo==up)

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

   375 // 	else

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

   377 // 	break;

   378 //       default: ;

   379 // 	//FIXME error

   380 //       }

   381 //     }

   382 //   }

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

   385   {

   386     //Bad parameter

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

   388       //FIXME error

   389     }

   391     if (lb == -INF){

   392       if (ub == INF){

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

   394       }

   395       else{

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

   397       }

   398     }

   399     else{

   400       if (ub==INF){

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

   403       }

   404       else{

   405 	if (lb == ub){

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

   407 	}

   408 	else{

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

   410 	}

   411       }

   412     }

   414   }

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

   417   {

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

   419     lpx_set_obj_coef(lp, i, obj_coef);

   420   }

   422   void LpGlpk::_clearObj()

   423   {

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

   425       lpx_set_obj_coef(lp, i, 0);

   426     }

   427   }

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

   429 // 		       int  const * indices,

   430 // 		       Value  const * values )

   431 //   {

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

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

   434 //       new_values[i]=0;

   435 //     }

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

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

   438 //     }

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

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

   442 //     }

   443 //   }

   445   LpGlpk::SolveExitStatus LpGlpk::_solve()

   446   {

   447     int i =  lpx_simplex(lp);

   448     switch (i) {

   449     case LPX_E_OK:

   450       return SOLVED;

   451     default:

   452       return UNSOLVED;

   453     }

   454   }

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

   457   {

   458     return lpx_get_col_prim(lp,i);

   459   }

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

   462   {

   463     return lpx_get_row_dual(lp,i);

   464   }

   466   LpGlpk::Value LpGlpk::_getPrimalValue()

   467   {

   468     return lpx_get_obj_val(lp);

   469   }

   470   bool LpGlpk::_isBasicCol(int i) {

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

   472   }

   475   LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()

   476   {

   477     int stat=  lpx_get_status(lp);

   478     switch (stat) {

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

   480       return UNDEFINED;

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

   482     case LPX_INFEAS://Infeasible

   483       return INFEASIBLE;

   484     case LPX_UNBND://Unbounded

   485       return INFINITE;

   486     case LPX_FEAS://Feasible

   487       return FEASIBLE;

   488     case LPX_OPT://Feasible

   489       return OPTIMAL;

   490     default:

   491       return UNDEFINED; //to avoid gcc warning

   492       //FIXME error

   493     }

   494   }

   496   LpGlpk::SolutionStatus LpGlpk::_getDualStatus()

   497   {

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

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

   501     switch (lpx_get_dual_stat(lp)) {

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

   503       return UNDEFINED;

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

   505 //    case LPX_D_INFEAS://Infeasible

   506       return INFEASIBLE;

   507     case LPX_D_FEAS://Feasible

   508       switch (lpx_get_status(lp)) {

   509       case LPX_NOFEAS:

   510 	return INFINITE;

   511       case LPX_OPT:

   512 	return OPTIMAL;

   513       default:

   514 	return FEASIBLE;

   515       }

   516     default:

   517       return UNDEFINED; //to avoid gcc warning

   518       //FIXME error

   519     }

   520   }

   522   LpGlpk::ProblemTypes LpGlpk::_getProblemType()

   523   {

   524       //int stat=  lpx_get_status(lp);

   525     int statp=  lpx_get_prim_stat(lp);

   526     int statd=  lpx_get_dual_stat(lp);

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

   528 	return PRIMAL_DUAL_FEASIBLE;

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

   530 	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

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

   532 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;

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

   534 	return PRIMAL_DUAL_INFEASIBLE;

   535     //In all other cases

   536     return UNKNOWN;

   537   }

   539   void LpGlpk::_setMax()

   540   {

   541     lpx_set_obj_dir(lp, LPX_MAX);

   542   }

   544   void LpGlpk::_setMin()

   545   {

   546     lpx_set_obj_dir(lp, LPX_MIN);

   547   }

   550   void LpGlpk::messageLevel(int m)

   551   {

   552     lpx_set_int_parm(lp, LPX_K_MSGLEV, m);

   553   }

   555   void LpGlpk::presolver(bool b)

   556   {

   557     lpx_set_int_parm(lp, LPX_K_PRESOL, b);

   558   }

   561 } //END OF NAMESPACE LEMON

author	deba
	Wed, 29 Nov 2006 17:34:29 +0000
changeset 2315	bd09e00b64bb
parent 2253	1645f6cc9667
child 2321	e23a610bed51
permissions	-rw-r--r--