lemon-0.x: src/lemon/lp_glpk.cc@ad44b1dd8013

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

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

     3  *

     4  * Copyright (C) 2005 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>

    25 namespace lemon {

    27   ///\e

    29   ///\bug Unimplemented!

    30   ///

    31   LpSolverBase &LpGlpk::_newLp()

    32   {

    33     LpSolverBase *tmp=0;

    34     return *tmp;

    35   }

    37   ///\e

    39   ///\bug Unimplemented!

    40   ///

    41   LpSolverBase &LpGlpk::_copyLp()

    42   {

    43     LpSolverBase *tmp=0;

    44     return *tmp;

    45   }

    47   LpGlpk::LpGlpk() : Parent(),

    48 		     lp(lpx_create_prob()) {

    49     ///\todo constrol function for this:

    50     lpx_set_int_parm(lp, LPX_K_DUAL, 1);

    51     messageLevel(0);

    52   }

    54   LpGlpk::~LpGlpk() {

    55     lpx_delete_prob(lp);

    56   }

    58   int LpGlpk::_addCol() {

    59     int i=lpx_add_cols(lp, 1);

    60     _setColLowerBound(i, -INF);

    61     _setColUpperBound(i, INF);

    62     return i;

    63   }

    65   int LpGlpk::_addRow() {

    66     int i=lpx_add_rows(lp, 1);

    67     return i;

    68   }

    71   void LpGlpk::_setRowCoeffs(int i,

    72 			     int length,

    73 			     const int   * indices,

    74 			     const Value   * values )

    75   {

    76     lpx_set_mat_row(lp, i, length,

    77 		    const_cast<int * >(indices) ,

    78 		    const_cast<Value * >(values));

    79   }

    81   void LpGlpk::_setColCoeffs(int i,

    82 			     int length,

    83 			     const int   * indices,

    84 			     const Value   * values)

    85   {

    86     lpx_set_mat_col(lp, i, length,

    87 		    const_cast<int * >(indices),

    88 		    const_cast<Value * >(values));

    89   }

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

    93   {

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

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

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

    98     int mem_length=2+lpx_get_num_cols(lp);

    99     int* indices = new int[mem_length];

   100     Value* values = new Value[mem_length];

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

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

   106     int i=1;

   107     bool found=false;

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

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

   110 	found = true;

   111 	values[i]=value;

   112       }

   113       ++i;

   114     }

   115     if (!found){

   116       ++length;

   117       indices[length]=col;

   118       values[length]=value;

   119     }

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

   122     delete [] indices;

   123     delete [] values;

   125   }

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

   128   {

   129     if (lo==INF) {

   130       //FIXME error

   131     }

   132     int b=lpx_get_col_type(lp, i);

   133     double up=lpx_get_col_ub(lp, i);

   134     if (lo==-INF) {

   135       switch (b) {

   136       case LPX_FR:

   137       case LPX_LO:

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

   139 	break;

   140       case LPX_UP:

   141 	break;

   142       case LPX_DB:

   143       case LPX_FX:

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

   145 	break;

   146       default: ;

   147 	//FIXME error

   148       }

   149     } else {

   150       switch (b) {

   151       case LPX_FR:

   152       case LPX_LO:

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

   154 	break;

   155       case LPX_UP:

   156       case LPX_DB:

   157       case LPX_FX:

   158 	if (lo==up)

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

   160 	else

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

   162 	break;

   163       default: ;

   164 	//FIXME error

   165       }

   166     }

   168   }

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

   171   {

   172     if (up==-INF) {

   173       //FIXME error

   174     }

   175     int b=lpx_get_col_type(lp, i);

   176     double lo=lpx_get_col_lb(lp, i);

   177     if (up==INF) {

   178       switch (b) {

   179       case LPX_FR:

   180       case LPX_LO:

   181 	break;

   182       case LPX_UP:

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

   184 	break;

   185       case LPX_DB:

   186       case LPX_FX:

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

   188 	break;

   189       default: ;

   190 	//FIXME error

   191       }

   192     } else {

   193       switch (b) {

   194       case LPX_FR:

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

   196 	break;

   197       case LPX_UP:

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

   199 	break;

   200       case LPX_LO:

   201       case LPX_DB:

   202       case LPX_FX:

   203 	if (lo==up)

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

   205 	else

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

   207 	break;

   208       default: ;

   209 	//FIXME error

   210       }

   211     }

   212   }

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

   215 //   {

   216 //     if (lo==INF) {

   217 //       //FIXME error

   218 //     }

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

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

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

   222 //       switch (b) {

   223 //       case LPX_FR:

   224 //       case LPX_LO:

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

   226 // 	break;

   227 //       case LPX_UP:

   228 // 	break;

   229 //       case LPX_DB:

   230 //       case LPX_FX:

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

   232 // 	break;

   233 //       default: ;

   234 // 	//FIXME error

   235 //       }

   236 //     } else {

   237 //       switch (b) {

   238 //       case LPX_FR:

   239 //       case LPX_LO:

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

   241 // 	break;

   242 //       case LPX_UP:

   243 //       case LPX_DB:

   244 //       case LPX_FX:

   245 // 	if (lo==up)

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

   247 // 	else

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

   249 // 	break;

   250 //       default: ;

   251 // 	//FIXME error

   252 //       }

   253 //     }

   254 //   }

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

   257 //   {

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

   259 //       //FIXME error

   260 //     }

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

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

   263 //     if (up==INF) {

   264 //       switch (b) {

   265 //       case LPX_FR:

   266 //       case LPX_LO:

   267 // 	break;

   268 //       case LPX_UP:

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

   270 // 	break;

   271 //       case LPX_DB:

   272 //       case LPX_FX:

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

   274 // 	break;

   275 //       default: ;

   276 // 	//FIXME error

   277 //       }

   278 //     } else {

   279 //       switch (b) {

   280 //       case LPX_FR:

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

   282 // 	break;

   283 //       case LPX_UP:

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

   285 // 	break;

   286 //       case LPX_LO:

   287 //       case LPX_DB:

   288 //       case LPX_FX:

   289 // 	if (lo==up)

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

   291 // 	else

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

   293 // 	break;

   294 //       default: ;

   295 // 	//FIXME error

   296 //       }

   297 //     }

   298 //   }

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

   301   {

   302     //Bad parameter

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

   304       //FIXME error

   305     }

   307     if (lb == -INF){

   308       if (ub == INF){

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

   310       }

   311       else{

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

   313       }

   314     }

   315     else{

   316       if (ub==INF){

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

   319       }

   320       else{

   321 	if (lb == ub){

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

   323 	}

   324 	else{

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

   326 	}

   327       }

   328     }

   330   }

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

   333   {

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

   335     lpx_set_obj_coef(lp, i, obj_coef);

   336   }

   338   void LpGlpk::_clearObj()

   339   {

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

   341       lpx_set_obj_coef(lp, i, 0);

   342     }

   343   }

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

   345 // 		       int  const * indices,

   346 // 		       Value  const * values )

   347 //   {

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

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

   350 //       new_values[i]=0;

   351 //     }

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

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

   354 //     }

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

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

   358 //     }

   359 //   }

   361   LpGlpk::SolveExitStatus LpGlpk::_solve()

   362   {

   363     int i=  lpx_simplex(lp);

   364     switch (i) {

   365     case LPX_E_OK:

   366       return SOLVED;

   367       break;

   368     default:

   369       return UNSOLVED;

   370     }

   371   }

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

   374   {

   375     return lpx_get_col_prim(lp,i);

   376   }

   378   LpGlpk::Value LpGlpk::_getPrimalValue()

   379   {

   380     return lpx_get_obj_val(lp);

   381   }

   384   LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()

   385   {

   386     int stat=  lpx_get_status(lp);

   387     switch (stat) {

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

   389       return UNDEFINED;

   390       break;

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

   392     case LPX_INFEAS://Infeasible

   393       return INFEASIBLE;

   394       break;

   395     case LPX_UNBND://Unbounded

   396       return INFINITE;

   397       break;

   398     case LPX_FEAS://Feasible

   399       return FEASIBLE;

   400       break;

   401     case LPX_OPT://Feasible

   402       return OPTIMAL;

   403       break;

   404     default:

   405       return UNDEFINED; //to avoid gcc warning

   406       //FIXME error

   407     }

   408   }

   411   void LpGlpk::_setMax()

   412   {

   413     lpx_set_obj_dir(lp, LPX_MAX);

   414   }

   416   void LpGlpk::_setMin()

   417   {

   418     lpx_set_obj_dir(lp, LPX_MIN);

   419   }

   422   void LpGlpk::messageLevel(int m)

   423   {

   424     lpx_set_int_parm(lp, LPX_K_MSGLEV, m);

   425   }

   427   void LpGlpk::presolver(bool b)

   428   {

   429     lpx_set_int_parm(lp, LPX_K_PRESOL, b);

   430   }

   433 } //END OF NAMESPACE LEMON

   435 #endif //LEMON_LP_GLPK_CC

author	athos
	Fri, 20 May 2005 09:31:25 +0000
changeset 1431	ad44b1dd8013
parent 1405	3626c7f10f14
child 1432	46b088b01f88
permissions	-rw-r--r--