lemon-0.x: lemon/lp_glpk.cc@72c7075ad5ba

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

   123   }

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

   126   {

   127     std::vector<int> indices;

   128     std::vector<Value> values;

   130     indices.push_back(0);

   131     values.push_back(0);

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

   134       indices.push_back(it->first);

   135       values.push_back(it->second);

   136     }

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

   139   }

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

   143     std::vector<int> indices;

   144     std::vector<Value> values;

   146     indices.push_back(0);

   147     values.push_back(0);

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

   150       indices.push_back(it->first);

   151       values.push_back(it->second);

   152     }

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

   155   }

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

   159   {

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

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

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

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

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

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

   171       //array indices are sorted

   172       bool found=false;

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

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

   175           found=true;

   176           values[i]=value;

   177           break;

   178         }

   179       }

   180       if (!found){

   181         ++length;

   182         indices[length]=col;

   183         values[length]=value;

   184       }

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

   188     } else {

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

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

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

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

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

   198       //array indices are sorted

   199       bool found=false;

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

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

   202           found=true;

   203           values[i]=value;

   204           break;

   205         }

   206       }

   207       if (!found){

   208         ++length;

   209         indices[length]=row;

   210         values[length]=value;

   211       }

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

   214     }

   215   }

   217   LpGlpk::Value LpGlpk::_getCoeff(int row, int col)

   218   {

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

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

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

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

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

   228     //array indices are sorted

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

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

   231 	return values[i];

   232       }

   233     }

   234     return 0;

   236   }

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

   240   {

   241     if (lo==INF) {

   242       //FIXME error

   243     }

   244     int b=lpx_get_col_type(lp, i);

   245     double up=lpx_get_col_ub(lp, i);

   246     if (lo==-INF) {

   247       switch (b) {

   248       case LPX_FR:

   249       case LPX_LO:

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

   251 	break;

   252       case LPX_UP:

   253 	break;

   254       case LPX_DB:

   255       case LPX_FX:

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

   257 	break;

   258       default: ;

   259 	//FIXME error

   260       }

   261     } else {

   262       switch (b) {

   263       case LPX_FR:

   264       case LPX_LO:

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

   266 	break;

   267       case LPX_UP:

   268       case LPX_DB:

   269       case LPX_FX:

   270 	if (lo==up)

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

   272 	else

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

   274 	break;

   275       default: ;

   276 	//FIXME error

   277       }

   278     }

   280   }

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

   283   {

   284     int b=lpx_get_col_type(lp, i);

   285       switch (b) {

   286       case LPX_LO:

   287       case LPX_DB:

   288       case LPX_FX:

   289 	return lpx_get_col_lb(lp, i);

   290       default: ;

   291 	return -INF;

   292       }

   293   }

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

   296   {

   297     if (up==-INF) {

   298       //FIXME error

   299     }

   300     int b=lpx_get_col_type(lp, i);

   301     double lo=lpx_get_col_lb(lp, i);

   302     if (up==INF) {

   303       switch (b) {

   304       case LPX_FR:

   305       case LPX_LO:

   306 	break;

   307       case LPX_UP:

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

   309 	break;

   310       case LPX_DB:

   311       case LPX_FX:

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

   313 	break;

   314       default: ;

   315 	//FIXME error

   316       }

   317     } else {

   318       switch (b) {

   319       case LPX_FR:

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

   321 	break;

   322       case LPX_UP:

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

   324 	break;

   325       case LPX_LO:

   326       case LPX_DB:

   327       case LPX_FX:

   328 	if (lo==up)

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

   330 	else

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

   332 	break;

   333       default: ;

   334 	//FIXME error

   335       }

   336     }

   337   }

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

   340   {

   341     int b=lpx_get_col_type(lp, i);

   342       switch (b) {

   343       case LPX_UP:

   344       case LPX_DB:

   345       case LPX_FX:

   346 	return lpx_get_col_ub(lp, i);

   347       default: ;

   348 	return INF;

   349       }

   350   }

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

   353 //   {

   354 //     if (lo==INF) {

   355 //       //FIXME error

   356 //     }

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

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

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

   360 //       switch (b) {

   361 //       case LPX_FR:

   362 //       case LPX_LO:

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

   364 // 	break;

   365 //       case LPX_UP:

   366 // 	break;

   367 //       case LPX_DB:

   368 //       case LPX_FX:

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

   370 // 	break;

   371 //       default: ;

   372 // 	//FIXME error

   373 //       }

   374 //     } else {

   375 //       switch (b) {

   376 //       case LPX_FR:

   377 //       case LPX_LO:

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

   379 // 	break;

   380 //       case LPX_UP:

   381 //       case LPX_DB:

   382 //       case LPX_FX:

   383 // 	if (lo==up)

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

   385 // 	else

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

   387 // 	break;

   388 //       default: ;

   389 // 	//FIXME error

   390 //       }

   391 //     }

   392 //   }

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

   395 //   {

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

   397 //       //FIXME error

   398 //     }

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

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

   401 //     if (up==INF) {

   402 //       switch (b) {

   403 //       case LPX_FR:

   404 //       case LPX_LO:

   405 // 	break;

   406 //       case LPX_UP:

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

   408 // 	break;

   409 //       case LPX_DB:

   410 //       case LPX_FX:

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

   412 // 	break;

   413 //       default: ;

   414 // 	//FIXME error

   415 //       }

   416 //     } else {

   417 //       switch (b) {

   418 //       case LPX_FR:

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

   420 // 	break;

   421 //       case LPX_UP:

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

   423 // 	break;

   424 //       case LPX_LO:

   425 //       case LPX_DB:

   426 //       case LPX_FX:

   427 // 	if (lo==up)

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

   429 // 	else

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

   431 // 	break;

   432 //       default: ;

   433 // 	//FIXME error

   434 //       }

   435 //     }

   436 //   }

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

   439   {

   440     //Bad parameter

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

   442       //FIXME error

   443     }

   445     if (lb == -INF){

   446       if (ub == INF){

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

   448       }

   449       else{

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

   451       }

   452     }

   453     else{

   454       if (ub==INF){

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

   457       }

   458       else{

   459 	if (lb == ub){

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

   461 	}

   462 	else{

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

   464 	}

   465       }

   466     }

   468   }

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

   471   {

   473     int b=lpx_get_row_type(lp, i);

   474     switch (b) {

   475     case LPX_FR:

   476     case LPX_UP:

   477       lb = -INF;

   478 	break;

   479     default:

   480       lb=lpx_get_row_lb(lp, i);

   481     }

   483     switch (b) {

   484     case LPX_FR:

   485     case LPX_LO:

   486       ub = INF;

   487 	break;

   488     default:

   489       ub=lpx_get_row_ub(lp, i);

   490     }

   492   }

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

   495   {

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

   497     lpx_set_obj_coef(lp, i, obj_coef);

   498   }

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

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

   502     return lpx_get_obj_coef(lp, i);

   503   }

   505   void LpGlpk::_clearObj()

   506   {

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

   508       lpx_set_obj_coef(lp, i, 0);

   509     }

   510   }

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

   512 // 		       int  const * indices,

   513 // 		       Value  const * values )

   514 //   {

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

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

   517 //       new_values[i]=0;

   518 //     }

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

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

   521 //     }

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

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

   525 //     }

   526 //   }

   528   LpGlpk::SolveExitStatus LpGlpk::_solve()

   529   {

   530     // A way to check the problem to be solved

   531     //lpx_write_cpxlp(lp,"naittvan.cpx");

   533     int i =  lpx_simplex(lp);

   534     switch (i) {

   535     case LPX_E_OK:

   536       return SOLVED;

   537     default:

   538       return UNSOLVED;

   539     }

   540   }

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

   543   {

   544     return lpx_get_col_prim(lp,i);

   545   }

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

   548   {

   549     return lpx_get_row_dual(lp,i);

   550   }

   552   LpGlpk::Value LpGlpk::_getPrimalValue()

   553   {

   554     return lpx_get_obj_val(lp);

   555   }

   556   bool LpGlpk::_isBasicCol(int i) {

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

   558   }

   561   LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()

   562   {

   563     int stat=  lpx_get_status(lp);

   564     switch (stat) {

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

   566       return UNDEFINED;

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

   568     case LPX_INFEAS://Infeasible

   569       return INFEASIBLE;

   570     case LPX_UNBND://Unbounded

   571       return INFINITE;

   572     case LPX_FEAS://Feasible

   573       return FEASIBLE;

   574     case LPX_OPT://Feasible

   575       return OPTIMAL;

   576     default:

   577       return UNDEFINED; //to avoid gcc warning

   578       //FIXME error

   579     }

   580   }

   582   LpGlpk::SolutionStatus LpGlpk::_getDualStatus()

   583   {

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

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

   587     switch (lpx_get_dual_stat(lp)) {

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

   589       return UNDEFINED;

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

   591 //    case LPX_D_INFEAS://Infeasible

   592       return INFEASIBLE;

   593     case LPX_D_FEAS://Feasible

   594       switch (lpx_get_status(lp)) {

   595       case LPX_NOFEAS:

   596 	return INFINITE;

   597       case LPX_OPT:

   598 	return OPTIMAL;

   599       default:

   600 	return FEASIBLE;

   601       }

   602     default:

   603       return UNDEFINED; //to avoid gcc warning

   604       //FIXME error

   605     }

   606   }

   608   LpGlpk::ProblemTypes LpGlpk::_getProblemType()

   609   {

   610       //int stat=  lpx_get_status(lp);

   611     int statp=  lpx_get_prim_stat(lp);

   612     int statd=  lpx_get_dual_stat(lp);

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

   614 	return PRIMAL_DUAL_FEASIBLE;

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

   616 	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

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

   618 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;

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

   620 	return PRIMAL_DUAL_INFEASIBLE;

   621     //In all other cases

   622     return UNKNOWN;

   623   }

   625   void LpGlpk::_setMax()

   626   {

   627     lpx_set_obj_dir(lp, LPX_MAX);

   628   }

   630   void LpGlpk::_setMin()

   631   {

   632     lpx_set_obj_dir(lp, LPX_MIN);

   633   }

   635   bool LpGlpk::_isMax()

   636   {

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

   638   }

   642   void LpGlpk::messageLevel(int m)

   643   {

   644     lpx_set_int_parm(lp, LPX_K_MSGLEV, m);

   645   }

   647   void LpGlpk::presolver(bool b)

   648   {

   649     lpx_set_int_parm(lp, LPX_K_PRESOL, b);

   650   }

   653 } //END OF NAMESPACE LEMON

author	alpar
	Mon, 12 Feb 2007 17:54:36 +0000
changeset 2360	72c7075ad5ba
parent 2345	bfcaad2b84e8
child 2363	2aabce558574
permissions	-rw-r--r--