lemon-0.x: lemon/lp_glpk.cc@5db4ff8d69de

     1 /* -*- C++ -*-

     2  * lemon/lp_glpk.cc - Part of LEMON, a generic C++ optimization library

     3  *

     4  * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     6  *

     7  * Permission to use, modify and distribute this software is granted

     8  * provided that this copyright notice appears in all copies. For

     9  * precise terms see the accompanying LICENSE file.

    10  *

    11  * This software is provided "AS IS" with no warranty of any kind,

    12  * express or implied, and with no claim as to its suitability for any

    13  * purpose.

    14  *

    15  */

    17 #ifndef LEMON_LP_GLPK_CC

    18 #define LEMON_LP_GLPK_CC

    20 ///\file

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

    23 #include <lemon/lp_glpk.h>

    24 //#include <iostream>

    25 namespace lemon {

    28   LpGlpk::LpGlpk() : Parent(),

    29 		     lp(lpx_create_prob()) {

    30     ///\todo constrol function for this:

    31     lpx_set_int_parm(lp, LPX_K_DUAL, 1);

    32     messageLevel(0);

    33   }

    35   LpGlpk::~LpGlpk() {

    36     lpx_delete_prob(lp);

    37   }

    39   int LpGlpk::_addCol() {

    40     int i=lpx_add_cols(lp, 1);

    41     _setColLowerBound(i, -INF);

    42     _setColUpperBound(i, INF);

    43     return i;

    44   }

    46   ///\e

    49   LpSolverBase &LpGlpk::_newLp()

    50   {

    51     LpGlpk* newlp=new LpGlpk();

    52     return *newlp;

    53   }

    55   ///\e

    57   LpSolverBase &LpGlpk::_copyLp()

    58   {

    59     LpGlpk* newlp=new LpGlpk();

    61     //Coefficient matrix, row bounds

    62     lpx_add_rows(newlp->lp, lpx_get_num_rows(lp));

    63     lpx_add_cols(newlp->lp, lpx_get_num_cols(lp));

    64     int len;

    65     int ind[1+lpx_get_num_cols(lp)];

    66     Value val[1+lpx_get_num_cols(lp)];

    67     for (int i=1;i<=lpx_get_num_rows(lp);++i){

    68       len=lpx_get_mat_row(lp,i,ind,val);

    69       lpx_set_mat_row(newlp->lp, i,len,ind,val);

    70       lpx_set_row_bnds(newlp->lp,i,lpx_get_row_type(lp,i),

    71 		       lpx_get_row_lb(lp,i),lpx_get_row_ub(lp,i));

    72     }

    74     //Objective function, coloumn bounds

    75     lpx_set_obj_dir(newlp->lp, lpx_get_obj_dir(lp));

    76     //Objectif function's constant term treated separately

    77     lpx_set_obj_coef(newlp->lp,0,lpx_get_obj_coef(lp,0));

    78     for (int i=1;i<=lpx_get_num_cols(lp);++i){

    79       lpx_set_obj_coef(newlp->lp,i,lpx_get_obj_coef(lp,i));

    80       lpx_set_col_bnds(newlp->lp,i,lpx_get_col_type(lp,i),

    81 		       lpx_get_col_lb(lp,i),lpx_get_col_ub(lp,i));

    84     }

    86     return *newlp;

    87   }

    89   int LpGlpk::_addRow() {

    90     int i=lpx_add_rows(lp, 1);

    91     return i;

    92   }

    95   void LpGlpk::_eraseCol(int i) {

    96     int cols[2];

    97     cols[1]=i;

    98     lpx_del_cols(lp, 1, cols);

    99   }

   101   void LpGlpk::_eraseRow(int i) {

   102     int rows[2];

   103     rows[1]=i;

   104     lpx_del_rows(lp, 1, rows);

   105   }

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

   108   {

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

   111     name = n?n:"";

   112   }

   115   void LpGlpk::_setColName(int col, const std::string & name)

   116   {

   117     lpx_set_col_name(lp,col,const_cast<char*>(name.c_str()));

   118   }

   120   void LpGlpk::_setRowCoeffs(int i,

   121 			     int length,

   122 			     const int   * indices,

   123 			     const Value   * values )

   124   {

   125     lpx_set_mat_row(lp, i, length,

   126 		    const_cast<int * >(indices) ,

   127 		    const_cast<Value * >(values));

   128   }

   130   void LpGlpk::_setColCoeffs(int i,

   131 			     int length,

   132 			     const int   * indices,

   133 			     const Value   * values)

   134   {

   135     lpx_set_mat_col(lp, i, length,

   136 		    const_cast<int * >(indices),

   137 		    const_cast<Value * >(values));

   138   }

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

   142   {

   143     ///FIXME Of course this is not efficient at all, but GLPK knows not more.

   144     // First approach: get one row, apply changes and set it again

   145     //(one idea to improve this: maybe it is better to do this with 1 coloumn)

   147     int mem_length=2+lpx_get_num_cols(lp);

   148     int* indices = new int[mem_length];

   149     Value* values = new Value[mem_length];

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

   154     //The following code does not suppose that the elements of the array indices are sorted

   155     int i=1;

   156     bool found=false;

   157     while (i <= length && !found){

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

   159 	found = true;

   160 	values[i]=value;

   161       }

   162       ++i;

   163     }

   164     if (!found){

   165       ++length;

   166       indices[length]=col;

   167       values[length]=value;

   168     }

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

   171     delete [] indices;

   172     delete [] values;

   174   }

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

   177   {

   178     if (lo==INF) {

   179       //FIXME error

   180     }

   181     int b=lpx_get_col_type(lp, i);

   182     double up=lpx_get_col_ub(lp, i);

   183     if (lo==-INF) {

   184       switch (b) {

   185       case LPX_FR:

   186       case LPX_LO:

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

   188 	break;

   189       case LPX_UP:

   190 	break;

   191       case LPX_DB:

   192       case LPX_FX:

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

   194 	break;

   195       default: ;

   196 	//FIXME error

   197       }

   198     } else {

   199       switch (b) {

   200       case LPX_FR:

   201       case LPX_LO:

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

   203 	break;

   204       case LPX_UP:

   205       case LPX_DB:

   206       case LPX_FX:

   207 	if (lo==up)

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

   209 	else

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

   211 	break;

   212       default: ;

   213 	//FIXME error

   214       }

   215     }

   217   }

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

   220   {

   221     if (up==-INF) {

   222       //FIXME error

   223     }

   224     int b=lpx_get_col_type(lp, i);

   225     double lo=lpx_get_col_lb(lp, i);

   226     if (up==INF) {

   227       switch (b) {

   228       case LPX_FR:

   229       case LPX_LO:

   230 	break;

   231       case LPX_UP:

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

   233 	break;

   234       case LPX_DB:

   235       case LPX_FX:

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

   237 	break;

   238       default: ;

   239 	//FIXME error

   240       }

   241     } else {

   242       switch (b) {

   243       case LPX_FR:

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

   245 	break;

   246       case LPX_UP:

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

   248 	break;

   249       case LPX_LO:

   250       case LPX_DB:

   251       case LPX_FX:

   252 	if (lo==up)

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

   254 	else

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

   256 	break;

   257       default: ;

   258 	//FIXME error

   259       }

   260     }

   261   }

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

   264 //   {

   265 //     if (lo==INF) {

   266 //       //FIXME error

   267 //     }

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

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

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

   271 //       switch (b) {

   272 //       case LPX_FR:

   273 //       case LPX_LO:

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

   275 // 	break;

   276 //       case LPX_UP:

   277 // 	break;

   278 //       case LPX_DB:

   279 //       case LPX_FX:

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

   281 // 	break;

   282 //       default: ;

   283 // 	//FIXME error

   284 //       }

   285 //     } else {

   286 //       switch (b) {

   287 //       case LPX_FR:

   288 //       case LPX_LO:

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

   290 // 	break;

   291 //       case LPX_UP:

   292 //       case LPX_DB:

   293 //       case LPX_FX:

   294 // 	if (lo==up)

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

   296 // 	else

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

   298 // 	break;

   299 //       default: ;

   300 // 	//FIXME error

   301 //       }

   302 //     }

   303 //   }

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

   306 //   {

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

   308 //       //FIXME error

   309 //     }

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

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

   312 //     if (up==INF) {

   313 //       switch (b) {

   314 //       case LPX_FR:

   315 //       case LPX_LO:

   316 // 	break;

   317 //       case LPX_UP:

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

   319 // 	break;

   320 //       case LPX_DB:

   321 //       case LPX_FX:

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

   323 // 	break;

   324 //       default: ;

   325 // 	//FIXME error

   326 //       }

   327 //     } else {

   328 //       switch (b) {

   329 //       case LPX_FR:

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

   331 // 	break;

   332 //       case LPX_UP:

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

   334 // 	break;

   335 //       case LPX_LO:

   336 //       case LPX_DB:

   337 //       case LPX_FX:

   338 // 	if (lo==up)

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

   340 // 	else

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

   342 // 	break;

   343 //       default: ;

   344 // 	//FIXME error

   345 //       }

   346 //     }

   347 //   }

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

   350   {

   351     //Bad parameter

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

   353       //FIXME error

   354     }

   356     if (lb == -INF){

   357       if (ub == INF){

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

   359       }

   360       else{

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

   362       }

   363     }

   364     else{

   365       if (ub==INF){

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

   368       }

   369       else{

   370 	if (lb == ub){

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

   372 	}

   373 	else{

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

   375 	}

   376       }

   377     }

   379   }

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

   382   {

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

   384     lpx_set_obj_coef(lp, i, obj_coef);

   385   }

   387   void LpGlpk::_clearObj()

   388   {

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

   390       lpx_set_obj_coef(lp, i, 0);

   391     }

   392   }

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

   394 // 		       int  const * indices,

   395 // 		       Value  const * values )

   396 //   {

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

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

   399 //       new_values[i]=0;

   400 //     }

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

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

   403 //     }

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

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

   407 //     }

   408 //   }

   410   LpGlpk::SolveExitStatus LpGlpk::_solve()

   411   {

   412     int i =  lpx_simplex(lp);

   413     switch (i) {

   414     case LPX_E_OK:

   415       return SOLVED;

   416     default:

   417       return UNSOLVED;

   418     }

   419   }

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

   422   {

   423     return lpx_get_col_prim(lp,i);

   424   }

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

   427   {

   428     return lpx_get_row_dual(lp,i);

   429   }

   431   LpGlpk::Value LpGlpk::_getPrimalValue()

   432   {

   433     return lpx_get_obj_val(lp);

   434   }

   435   bool LpGlpk::_isBasicCol(int i) {

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

   437   }

   440   LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()

   441   {

   442     int stat=  lpx_get_status(lp);

   443     switch (stat) {

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

   445       return UNDEFINED;

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

   447     case LPX_INFEAS://Infeasible

   448       return INFEASIBLE;

   449     case LPX_UNBND://Unbounded

   450       return INFINITE;

   451     case LPX_FEAS://Feasible

   452       return FEASIBLE;

   453     case LPX_OPT://Feasible

   454       return OPTIMAL;

   455     default:

   456       return UNDEFINED; //to avoid gcc warning

   457       //FIXME error

   458     }

   459   }

   461   LpGlpk::SolutionStatus LpGlpk::_getDualStatus()

   462   {

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

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

   466     switch (lpx_get_dual_stat(lp)) {

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

   468       return UNDEFINED;

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

   470 //    case LPX_D_INFEAS://Infeasible

   471       return INFEASIBLE;

   472     case LPX_D_FEAS://Feasible

   473       switch (lpx_get_status(lp)) {

   474       case LPX_NOFEAS:

   475 	return INFINITE;

   476       case LPX_OPT:

   477 	return OPTIMAL;

   478       default:

   479 	return FEASIBLE;

   480       }

   481     default:

   482       return UNDEFINED; //to avoid gcc warning

   483       //FIXME error

   484     }

   485   }

   487   LpGlpk::ProblemTypes LpGlpk::_getProblemType()

   488   {

   489       //int stat=  lpx_get_status(lp);

   490     int statp=  lpx_get_prim_stat(lp);

   491     int statd=  lpx_get_dual_stat(lp);

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

   493 	return PRIMAL_DUAL_FEASIBLE;

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

   495 	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

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

   497 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;

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

   499 	return PRIMAL_DUAL_INFEASIBLE;

   500     //In all other cases

   501     return UNKNOWN;

   502   }

   504   void LpGlpk::_setMax()

   505   {

   506     lpx_set_obj_dir(lp, LPX_MAX);

   507   }

   509   void LpGlpk::_setMin()

   510   {

   511     lpx_set_obj_dir(lp, LPX_MIN);

   512   }

   515   void LpGlpk::messageLevel(int m)

   516   {

   517     lpx_set_int_parm(lp, LPX_K_MSGLEV, m);

   518   }

   520   void LpGlpk::presolver(bool b)

   521   {

   522     lpx_set_int_parm(lp, LPX_K_PRESOL, b);

   523   }

   526 } //END OF NAMESPACE LEMON

   528 #endif //LEMON_LP_GLPK_CC

author	alpar
	Fri, 03 Feb 2006 09:18:17 +0000
changeset 1949	5db4ff8d69de
parent 1875	98698b69a902
child 1956	a055123339d5
permissions	-rw-r--r--