lemon-0.x: lemon/lp_glpk.cc@507232469f5e

     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,

   120 			     int length,

   121 			     const int   * indices,

   122 			     const Value   * values )

   123   {

   124     lpx_set_mat_row(lp, i, length,

   125 		    const_cast<int * >(indices) ,

   126 		    const_cast<Value * >(values));

   127   }

   129   void LpGlpk::_setColCoeffs(int i,

   130 			     int length,

   131 			     const int   * indices,

   132 			     const Value   * values)

   133   {

   134     lpx_set_mat_col(lp, i, length,

   135 		    const_cast<int * >(indices),

   136 		    const_cast<Value * >(values));

   137   }

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

   141   {

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

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

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

   146     int mem_length=2+lpx_get_num_cols(lp);

   147     int* indices = new int[mem_length];

   148     Value* values = new Value[mem_length];

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

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

   154     int i=1;

   155     bool found=false;

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

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

   158 	found = true;

   159 	values[i]=value;

   160       }

   161       ++i;

   162     }

   163     if (!found){

   164       ++length;

   165       indices[length]=col;

   166       values[length]=value;

   167     }

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

   170     delete [] indices;

   171     delete [] values;

   173   }

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

   176   {

   177     if (lo==INF) {

   178       //FIXME error

   179     }

   180     int b=lpx_get_col_type(lp, i);

   181     double up=lpx_get_col_ub(lp, i);

   182     if (lo==-INF) {

   183       switch (b) {

   184       case LPX_FR:

   185       case LPX_LO:

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

   187 	break;

   188       case LPX_UP:

   189 	break;

   190       case LPX_DB:

   191       case LPX_FX:

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

   193 	break;

   194       default: ;

   195 	//FIXME error

   196       }

   197     } else {

   198       switch (b) {

   199       case LPX_FR:

   200       case LPX_LO:

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

   202 	break;

   203       case LPX_UP:

   204       case LPX_DB:

   205       case LPX_FX:

   206 	if (lo==up)

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

   208 	else

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

   210 	break;

   211       default: ;

   212 	//FIXME error

   213       }

   214     }

   216   }

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

   219   {

   220     if (up==-INF) {

   221       //FIXME error

   222     }

   223     int b=lpx_get_col_type(lp, i);

   224     double lo=lpx_get_col_lb(lp, i);

   225     if (up==INF) {

   226       switch (b) {

   227       case LPX_FR:

   228       case LPX_LO:

   229 	break;

   230       case LPX_UP:

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

   232 	break;

   233       case LPX_DB:

   234       case LPX_FX:

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

   236 	break;

   237       default: ;

   238 	//FIXME error

   239       }

   240     } else {

   241       switch (b) {

   242       case LPX_FR:

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

   244 	break;

   245       case LPX_UP:

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

   247 	break;

   248       case LPX_LO:

   249       case LPX_DB:

   250       case LPX_FX:

   251 	if (lo==up)

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

   253 	else

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

   255 	break;

   256       default: ;

   257 	//FIXME error

   258       }

   259     }

   260   }

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

   263 //   {

   264 //     if (lo==INF) {

   265 //       //FIXME error

   266 //     }

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

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

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

   270 //       switch (b) {

   271 //       case LPX_FR:

   272 //       case LPX_LO:

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

   274 // 	break;

   275 //       case LPX_UP:

   276 // 	break;

   277 //       case LPX_DB:

   278 //       case LPX_FX:

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

   280 // 	break;

   281 //       default: ;

   282 // 	//FIXME error

   283 //       }

   284 //     } else {

   285 //       switch (b) {

   286 //       case LPX_FR:

   287 //       case LPX_LO:

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

   289 // 	break;

   290 //       case LPX_UP:

   291 //       case LPX_DB:

   292 //       case LPX_FX:

   293 // 	if (lo==up)

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

   295 // 	else

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

   297 // 	break;

   298 //       default: ;

   299 // 	//FIXME error

   300 //       }

   301 //     }

   302 //   }

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

   305 //   {

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

   307 //       //FIXME error

   308 //     }

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

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

   311 //     if (up==INF) {

   312 //       switch (b) {

   313 //       case LPX_FR:

   314 //       case LPX_LO:

   315 // 	break;

   316 //       case LPX_UP:

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

   318 // 	break;

   319 //       case LPX_DB:

   320 //       case LPX_FX:

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

   322 // 	break;

   323 //       default: ;

   324 // 	//FIXME error

   325 //       }

   326 //     } else {

   327 //       switch (b) {

   328 //       case LPX_FR:

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

   330 // 	break;

   331 //       case LPX_UP:

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

   333 // 	break;

   334 //       case LPX_LO:

   335 //       case LPX_DB:

   336 //       case LPX_FX:

   337 // 	if (lo==up)

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

   339 // 	else

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

   341 // 	break;

   342 //       default: ;

   343 // 	//FIXME error

   344 //       }

   345 //     }

   346 //   }

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

   349   {

   350     //Bad parameter

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

   352       //FIXME error

   353     }

   355     if (lb == -INF){

   356       if (ub == INF){

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

   358       }

   359       else{

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

   361       }

   362     }

   363     else{

   364       if (ub==INF){

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

   367       }

   368       else{

   369 	if (lb == ub){

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

   371 	}

   372 	else{

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

   374 	}

   375       }

   376     }

   378   }

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

   381   {

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

   383     lpx_set_obj_coef(lp, i, obj_coef);

   384   }

   386   void LpGlpk::_clearObj()

   387   {

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

   389       lpx_set_obj_coef(lp, i, 0);

   390     }

   391   }

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

   393 // 		       int  const * indices,

   394 // 		       Value  const * values )

   395 //   {

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

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

   398 //       new_values[i]=0;

   399 //     }

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

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

   402 //     }

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

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

   406 //     }

   407 //   }

   409   LpGlpk::SolveExitStatus LpGlpk::_solve()

   410   {

   411     int i =  lpx_simplex(lp);

   412     switch (i) {

   413     case LPX_E_OK:

   414       return SOLVED;

   415     default:

   416       return UNSOLVED;

   417     }

   418   }

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

   421   {

   422     return lpx_get_col_prim(lp,i);

   423   }

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

   426   {

   427     return lpx_get_row_dual(lp,i);

   428   }

   430   LpGlpk::Value LpGlpk::_getPrimalValue()

   431   {

   432     return lpx_get_obj_val(lp);

   433   }

   434   bool LpGlpk::_isBasicCol(int i) {

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

   436   }

   439   LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()

   440   {

   441     int stat=  lpx_get_status(lp);

   442     switch (stat) {

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

   444       return UNDEFINED;

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

   446     case LPX_INFEAS://Infeasible

   447       return INFEASIBLE;

   448     case LPX_UNBND://Unbounded

   449       return INFINITE;

   450     case LPX_FEAS://Feasible

   451       return FEASIBLE;

   452     case LPX_OPT://Feasible

   453       return OPTIMAL;

   454     default:

   455       return UNDEFINED; //to avoid gcc warning

   456       //FIXME error

   457     }

   458   }

   460   LpGlpk::SolutionStatus LpGlpk::_getDualStatus()

   461   {

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

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

   465     switch (lpx_get_dual_stat(lp)) {

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

   467       return UNDEFINED;

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

   469 //    case LPX_D_INFEAS://Infeasible

   470       return INFEASIBLE;

   471     case LPX_D_FEAS://Feasible

   472       switch (lpx_get_status(lp)) {

   473       case LPX_NOFEAS:

   474 	return INFINITE;

   475       case LPX_OPT:

   476 	return OPTIMAL;

   477       default:

   478 	return FEASIBLE;

   479       }

   480     default:

   481       return UNDEFINED; //to avoid gcc warning

   482       //FIXME error

   483     }

   484   }

   486   LpGlpk::ProblemTypes LpGlpk::_getProblemType()

   487   {

   488       //int stat=  lpx_get_status(lp);

   489     int statp=  lpx_get_prim_stat(lp);

   490     int statd=  lpx_get_dual_stat(lp);

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

   492 	return PRIMAL_DUAL_FEASIBLE;

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

   494 	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

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

   496 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;

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

   498 	return PRIMAL_DUAL_INFEASIBLE;

   499     //In all other cases

   500     return UNKNOWN;

   501   }

   503   void LpGlpk::_setMax()

   504   {

   505     lpx_set_obj_dir(lp, LPX_MAX);

   506   }

   508   void LpGlpk::_setMin()

   509   {

   510     lpx_set_obj_dir(lp, LPX_MIN);

   511   }

   514   void LpGlpk::messageLevel(int m)

   515   {

   516     lpx_set_int_parm(lp, LPX_K_MSGLEV, m);

   517   }

   519   void LpGlpk::presolver(bool b)

   520   {

   521     lpx_set_int_parm(lp, LPX_K_PRESOL, b);

   522   }

   525 } //END OF NAMESPACE LEMON

author	athos
	Mon, 30 Oct 2006 16:12:44 +0000
changeset 2273	507232469f5e
parent 1956	a055123339d5
child 2312	07e46cbb7d85
permissions	-rw-r--r--