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

     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 row, int col)

   217   {

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

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

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

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

   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;

   235   }

   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     }

   279   }

   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   }

   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   }

   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   }

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

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

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

   438   {

   439     //Bad parameter

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

   441       //FIXME error

   442     }

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

   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     }

   467   }

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

   470   {

   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     }

   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     }

   491   }

   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   }

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

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

   501     return lpx_get_obj_coef(lp, i);

   502   }

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

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

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

   524 //     }

   525 //   }

   527   LpGlpk::SolveExitStatus LpGlpk::_solve()

   528   {

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

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

   532     int i =  lpx_simplex(lp);

   533     switch (i) {

   534     case LPX_E_OK:

   535       return SOLVED;

   536     default:

   537       return UNSOLVED;

   538     }

   539   }

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

   542   {

   543     return lpx_get_col_prim(lp,i);

   544   }

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

   547   {

   548     return lpx_get_row_dual(lp,i);

   549   }

   551   LpGlpk::Value LpGlpk::_getPrimalValue()

   552   {

   553     return lpx_get_obj_val(lp);

   554   }

   555   bool LpGlpk::_isBasicCol(int i) {

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

   557   }

   560   LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()

   561   {

   562     int stat=  lpx_get_status(lp);

   563     switch (stat) {

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

   565       return UNDEFINED;

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

   567     case LPX_INFEAS://Infeasible

   568       return INFEASIBLE;

   569     case LPX_UNBND://Unbounded

   570       return INFINITE;

   571     case LPX_FEAS://Feasible

   572       return FEASIBLE;

   573     case LPX_OPT://Feasible

   574       return OPTIMAL;

   575     default:

   576       return UNDEFINED; //to avoid gcc warning

   577       //FIXME error

   578     }

   579   }

   581   LpGlpk::SolutionStatus LpGlpk::_getDualStatus()

   582   {

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

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

   586     switch (lpx_get_dual_stat(lp)) {

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

   588       return UNDEFINED;

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

   590 //    case LPX_D_INFEAS://Infeasible

   591       return INFEASIBLE;

   592     case LPX_D_FEAS://Feasible

   593       switch (lpx_get_status(lp)) {

   594       case LPX_NOFEAS:

   595 	return INFINITE;

   596       case LPX_OPT:

   597 	return OPTIMAL;

   598       default:

   599 	return FEASIBLE;

   600       }

   601     default:

   602       return UNDEFINED; //to avoid gcc warning

   603       //FIXME error

   604     }

   605   }

   607   LpGlpk::ProblemTypes LpGlpk::_getProblemType()

   608   {

   609       //int stat=  lpx_get_status(lp);

   610     int statp=  lpx_get_prim_stat(lp);

   611     int statd=  lpx_get_dual_stat(lp);

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

   613 	return PRIMAL_DUAL_FEASIBLE;

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

   615 	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

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

   617 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;

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

   619 	return PRIMAL_DUAL_INFEASIBLE;

   620     //In all other cases

   621     return UNKNOWN;

   622   }

   624   void LpGlpk::_setMax()

   625   {

   626     lpx_set_obj_dir(lp, LPX_MAX);

   627   }

   629   void LpGlpk::_setMin()

   630   {

   631     lpx_set_obj_dir(lp, LPX_MIN);

   632   }

   634   bool LpGlpk::_isMax()

   635   {

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

   637   }

   641   void LpGlpk::messageLevel(int m)

   642   {

   643     lpx_set_int_parm(lp, LPX_K_MSGLEV, m);

   644   }

   646   void LpGlpk::presolver(bool b)

   647   {

   648     lpx_set_int_parm(lp, LPX_K_PRESOL, b);

   649   }

   652 } //END OF NAMESPACE LEMON

author	alpar
	Fri, 19 Jan 2007 17:15:15 +0000
changeset 2346	c06a956a92fa
parent 2328	b4931ae52069
child 2349	c945f577a66d
permissions	-rw-r--r--