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

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

    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   }

    65   LpGlpk::~LpGlpk() {

    66     lpx_delete_prob(lp);

    67   }

    69   int LpGlpk::_addCol() {

    70     int i=lpx_add_cols(lp, 1);

    71     _setColLowerBound(i, -INF);

    72     _setColUpperBound(i, INF);

    73     return i;

    74   }

    76   ///\e

    79   LpSolverBase &LpGlpk::_newLp()

    80   {

    81     LpGlpk* newlp=new LpGlpk;

    82     return *newlp;

    83   }

    85   ///\e

    87   LpSolverBase &LpGlpk::_copyLp()

    88   {

    89     LpGlpk* newlp=new LpGlpk(*this);

    90     return *newlp;

    91   }

    93   int LpGlpk::_addRow() {

    94     int i=lpx_add_rows(lp, 1);

    95     return i;

    96   }

    99   void LpGlpk::_eraseCol(int i) {

   100     int cols[2];

   101     cols[1]=i;

   102     lpx_del_cols(lp, 1, cols);

   103   }

   105   void LpGlpk::_eraseRow(int i) {

   106     int rows[2];

   107     rows[1]=i;

   108     lpx_del_rows(lp, 1, rows);

   109   }

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

   112   {

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

   115     name = n?n:"";

   116   }

   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   }

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

   125   {

   126     std::vector<int> indices;

   127     std::vector<Value> values;

   129     indices.push_back(0);

   130     values.push_back(0);

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

   133       indices.push_back(it->first);

   134       values.push_back(it->second);

   135     }

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

   138   }

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

   142     std::vector<int> indices;

   143     std::vector<Value> values;

   145     indices.push_back(0);

   146     values.push_back(0);

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

   149       indices.push_back(it->first);

   150       values.push_back(it->second);

   151     }

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

   154   }

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

   158   {

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

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

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

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

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

   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       }

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

   187     } else {

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

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

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

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

   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       }

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

   213     }

   214   }

   216   LpGlpk::Value LpGlpk::_getCoeff(int, int)

   217   {

   218     ///\todo This is not yet implemented!!!

   219     return 0;

   220   }

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

   224   {

   225     if (lo==INF) {

   226       //FIXME error

   227     }

   228     int b=lpx_get_col_type(lp, i);

   229     double up=lpx_get_col_ub(lp, i);

   230     if (lo==-INF) {

   231       switch (b) {

   232       case LPX_FR:

   233       case LPX_LO:

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

   235 	break;

   236       case LPX_UP:

   237 	break;

   238       case LPX_DB:

   239       case LPX_FX:

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

   241 	break;

   242       default: ;

   243 	//FIXME error

   244       }

   245     } else {

   246       switch (b) {

   247       case LPX_FR:

   248       case LPX_LO:

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

   250 	break;

   251       case LPX_UP:

   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     }

   264   }

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

   267   {

   268     if (up==-INF) {

   269       //FIXME error

   270     }

   271     int b=lpx_get_col_type(lp, i);

   272     double lo=lpx_get_col_lb(lp, i);

   273     if (up==INF) {

   274       switch (b) {

   275       case LPX_FR:

   276       case LPX_LO:

   277 	break;

   278       case LPX_UP:

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

   280 	break;

   281       case LPX_DB:

   282       case LPX_FX:

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

   284 	break;

   285       default: ;

   286 	//FIXME error

   287       }

   288     } else {

   289       switch (b) {

   290       case LPX_FR:

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

   292 	break;

   293       case LPX_UP:

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

   295 	break;

   296       case LPX_LO:

   297       case LPX_DB:

   298       case LPX_FX:

   299 	if (lo==up)

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

   301 	else

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

   303 	break;

   304       default: ;

   305 	//FIXME error

   306       }

   307     }

   308   }

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

   311 //   {

   312 //     if (lo==INF) {

   313 //       //FIXME error

   314 //     }

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

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

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

   318 //       switch (b) {

   319 //       case LPX_FR:

   320 //       case LPX_LO:

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

   322 // 	break;

   323 //       case LPX_UP:

   324 // 	break;

   325 //       case LPX_DB:

   326 //       case LPX_FX:

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

   328 // 	break;

   329 //       default: ;

   330 // 	//FIXME error

   331 //       }

   332 //     } else {

   333 //       switch (b) {

   334 //       case LPX_FR:

   335 //       case LPX_LO:

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

   337 // 	break;

   338 //       case LPX_UP:

   339 //       case LPX_DB:

   340 //       case LPX_FX:

   341 // 	if (lo==up)

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

   343 // 	else

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

   345 // 	break;

   346 //       default: ;

   347 // 	//FIXME error

   348 //       }

   349 //     }

   350 //   }

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

   353 //   {

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

   355 //       //FIXME error

   356 //     }

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

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

   359 //     if (up==INF) {

   360 //       switch (b) {

   361 //       case LPX_FR:

   362 //       case LPX_LO:

   363 // 	break;

   364 //       case LPX_UP:

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

   366 // 	break;

   367 //       case LPX_DB:

   368 //       case LPX_FX:

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

   370 // 	break;

   371 //       default: ;

   372 // 	//FIXME error

   373 //       }

   374 //     } else {

   375 //       switch (b) {

   376 //       case LPX_FR:

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

   378 // 	break;

   379 //       case LPX_UP:

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

   381 // 	break;

   382 //       case LPX_LO:

   383 //       case LPX_DB:

   384 //       case LPX_FX:

   385 // 	if (lo==up)

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

   387 // 	else

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

   389 // 	break;

   390 //       default: ;

   391 // 	//FIXME error

   392 //       }

   393 //     }

   394 //   }

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

   397   {

   398     //Bad parameter

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

   400       //FIXME error

   401     }

   403     if (lb == -INF){

   404       if (ub == INF){

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

   406       }

   407       else{

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

   409       }

   410     }

   411     else{

   412       if (ub==INF){

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

   415       }

   416       else{

   417 	if (lb == ub){

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

   419 	}

   420 	else{

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

   422 	}

   423       }

   424     }

   426   }

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

   429   {

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

   431     lpx_set_obj_coef(lp, i, obj_coef);

   432   }

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

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

   436     return lpx_get_obj_coef(lp, i);

   437   }

   439   void LpGlpk::_clearObj()

   440   {

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

   442       lpx_set_obj_coef(lp, i, 0);

   443     }

   444   }

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

   446 // 		       int  const * indices,

   447 // 		       Value  const * values )

   448 //   {

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

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

   451 //       new_values[i]=0;

   452 //     }

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

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

   455 //     }

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

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

   459 //     }

   460 //   }

   462   LpGlpk::SolveExitStatus LpGlpk::_solve()

   463   {

   464     int i =  lpx_simplex(lp);

   465     switch (i) {

   466     case LPX_E_OK:

   467       return SOLVED;

   468     default:

   469       return UNSOLVED;

   470     }

   471   }

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

   474   {

   475     return lpx_get_col_prim(lp,i);

   476   }

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

   479   {

   480     return lpx_get_row_dual(lp,i);

   481   }

   483   LpGlpk::Value LpGlpk::_getPrimalValue()

   484   {

   485     return lpx_get_obj_val(lp);

   486   }

   487   bool LpGlpk::_isBasicCol(int i) {

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

   489   }

   492   LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()

   493   {

   494     int stat=  lpx_get_status(lp);

   495     switch (stat) {

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

   497       return UNDEFINED;

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

   499     case LPX_INFEAS://Infeasible

   500       return INFEASIBLE;

   501     case LPX_UNBND://Unbounded

   502       return INFINITE;

   503     case LPX_FEAS://Feasible

   504       return FEASIBLE;

   505     case LPX_OPT://Feasible

   506       return OPTIMAL;

   507     default:

   508       return UNDEFINED; //to avoid gcc warning

   509       //FIXME error

   510     }

   511   }

   513   LpGlpk::SolutionStatus LpGlpk::_getDualStatus()

   514   {

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

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

   518     switch (lpx_get_dual_stat(lp)) {

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

   520       return UNDEFINED;

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

   522 //    case LPX_D_INFEAS://Infeasible

   523       return INFEASIBLE;

   524     case LPX_D_FEAS://Feasible

   525       switch (lpx_get_status(lp)) {

   526       case LPX_NOFEAS:

   527 	return INFINITE;

   528       case LPX_OPT:

   529 	return OPTIMAL;

   530       default:

   531 	return FEASIBLE;

   532       }

   533     default:

   534       return UNDEFINED; //to avoid gcc warning

   535       //FIXME error

   536     }

   537   }

   539   LpGlpk::ProblemTypes LpGlpk::_getProblemType()

   540   {

   541       //int stat=  lpx_get_status(lp);

   542     int statp=  lpx_get_prim_stat(lp);

   543     int statd=  lpx_get_dual_stat(lp);

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

   545 	return PRIMAL_DUAL_FEASIBLE;

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

   547 	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

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

   549 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;

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

   551 	return PRIMAL_DUAL_INFEASIBLE;

   552     //In all other cases

   553     return UNKNOWN;

   554   }

   556   void LpGlpk::_setMax()

   557   {

   558     lpx_set_obj_dir(lp, LPX_MAX);

   559   }

   561   void LpGlpk::_setMin()

   562   {

   563     lpx_set_obj_dir(lp, LPX_MIN);

   564   }

   566   bool LpGlpk::_isMax()

   567   {

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

   569   }

   573   void LpGlpk::messageLevel(int m)

   574   {

   575     lpx_set_int_parm(lp, LPX_K_MSGLEV, m);

   576   }

   578   void LpGlpk::presolver(bool b)

   579   {

   580     lpx_set_int_parm(lp, LPX_K_PRESOL, b);

   581   }

   584 } //END OF NAMESPACE LEMON

author	alpar
	Mon, 04 Dec 2006 18:08:30 +0000
changeset 2326	af8c695372be
parent 2324	18fc834761d9
child 2328	b4931ae52069
permissions	-rw-r--r--