lemon-0.x: src/lemon/lp_glpk.cc@46b088b01f88

     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::_eraseCol(int i) {

    72     int cols[2];

    73     cols[1]=i;

    74     lpx_del_cols(lp, 1, cols);

    75   }

    77   void LpGlpk::_eraseRow(int i) {

    78     int rows[2];

    79     rows[1]=i;

    80     lpx_del_rows(lp, 1, rows);

    81   }

    83   void LpGlpk::_setRowCoeffs(int i,

    84 			     int length,

    85 			     const int   * indices,

    86 			     const Value   * values )

    87   {

    88     lpx_set_mat_row(lp, i, length,

    89 		    const_cast<int * >(indices) ,

    90 		    const_cast<Value * >(values));

    91   }

    93   void LpGlpk::_setColCoeffs(int i,

    94 			     int length,

    95 			     const int   * indices,

    96 			     const Value   * values)

    97   {

    98     lpx_set_mat_col(lp, i, length,

    99 		    const_cast<int * >(indices),

   100 		    const_cast<Value * >(values));

   101   }

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

   105   {

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

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

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

   110     int mem_length=2+lpx_get_num_cols(lp);

   111     int* indices = new int[mem_length];

   112     Value* values = new Value[mem_length];

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

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

   118     int i=1;

   119     bool found=false;

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

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

   122 	found = true;

   123 	values[i]=value;

   124       }

   125       ++i;

   126     }

   127     if (!found){

   128       ++length;

   129       indices[length]=col;

   130       values[length]=value;

   131     }

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

   134     delete [] indices;

   135     delete [] values;

   137   }

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

   140   {

   141     if (lo==INF) {

   142       //FIXME error

   143     }

   144     int b=lpx_get_col_type(lp, i);

   145     double up=lpx_get_col_ub(lp, i);

   146     if (lo==-INF) {

   147       switch (b) {

   148       case LPX_FR:

   149       case LPX_LO:

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

   151 	break;

   152       case LPX_UP:

   153 	break;

   154       case LPX_DB:

   155       case LPX_FX:

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

   157 	break;

   158       default: ;

   159 	//FIXME error

   160       }

   161     } else {

   162       switch (b) {

   163       case LPX_FR:

   164       case LPX_LO:

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

   166 	break;

   167       case LPX_UP:

   168       case LPX_DB:

   169       case LPX_FX:

   170 	if (lo==up)

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

   172 	else

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

   174 	break;

   175       default: ;

   176 	//FIXME error

   177       }

   178     }

   180   }

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

   183   {

   184     if (up==-INF) {

   185       //FIXME error

   186     }

   187     int b=lpx_get_col_type(lp, i);

   188     double lo=lpx_get_col_lb(lp, i);

   189     if (up==INF) {

   190       switch (b) {

   191       case LPX_FR:

   192       case LPX_LO:

   193 	break;

   194       case LPX_UP:

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

   196 	break;

   197       case LPX_DB:

   198       case LPX_FX:

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

   200 	break;

   201       default: ;

   202 	//FIXME error

   203       }

   204     } else {

   205       switch (b) {

   206       case LPX_FR:

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

   208 	break;

   209       case LPX_UP:

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

   211 	break;

   212       case LPX_LO:

   213       case LPX_DB:

   214       case LPX_FX:

   215 	if (lo==up)

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

   217 	else

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

   219 	break;

   220       default: ;

   221 	//FIXME error

   222       }

   223     }

   224   }

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

   227 //   {

   228 //     if (lo==INF) {

   229 //       //FIXME error

   230 //     }

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

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

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

   234 //       switch (b) {

   235 //       case LPX_FR:

   236 //       case LPX_LO:

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

   238 // 	break;

   239 //       case LPX_UP:

   240 // 	break;

   241 //       case LPX_DB:

   242 //       case LPX_FX:

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

   244 // 	break;

   245 //       default: ;

   246 // 	//FIXME error

   247 //       }

   248 //     } else {

   249 //       switch (b) {

   250 //       case LPX_FR:

   251 //       case LPX_LO:

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

   253 // 	break;

   254 //       case LPX_UP:

   255 //       case LPX_DB:

   256 //       case LPX_FX:

   257 // 	if (lo==up)

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

   259 // 	else

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

   261 // 	break;

   262 //       default: ;

   263 // 	//FIXME error

   264 //       }

   265 //     }

   266 //   }

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

   269 //   {

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

   271 //       //FIXME error

   272 //     }

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

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

   275 //     if (up==INF) {

   276 //       switch (b) {

   277 //       case LPX_FR:

   278 //       case LPX_LO:

   279 // 	break;

   280 //       case LPX_UP:

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

   282 // 	break;

   283 //       case LPX_DB:

   284 //       case LPX_FX:

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

   286 // 	break;

   287 //       default: ;

   288 // 	//FIXME error

   289 //       }

   290 //     } else {

   291 //       switch (b) {

   292 //       case LPX_FR:

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

   294 // 	break;

   295 //       case LPX_UP:

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

   297 // 	break;

   298 //       case LPX_LO:

   299 //       case LPX_DB:

   300 //       case LPX_FX:

   301 // 	if (lo==up)

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

   303 // 	else

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

   305 // 	break;

   306 //       default: ;

   307 // 	//FIXME error

   308 //       }

   309 //     }

   310 //   }

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

   313   {

   314     //Bad parameter

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

   316       //FIXME error

   317     }

   319     if (lb == -INF){

   320       if (ub == INF){

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

   322       }

   323       else{

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

   325       }

   326     }

   327     else{

   328       if (ub==INF){

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

   331       }

   332       else{

   333 	if (lb == ub){

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

   335 	}

   336 	else{

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

   338 	}

   339       }

   340     }

   342   }

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

   345   {

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

   347     lpx_set_obj_coef(lp, i, obj_coef);

   348   }

   350   void LpGlpk::_clearObj()

   351   {

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

   353       lpx_set_obj_coef(lp, i, 0);

   354     }

   355   }

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

   357 // 		       int  const * indices,

   358 // 		       Value  const * values )

   359 //   {

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

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

   362 //       new_values[i]=0;

   363 //     }

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

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

   366 //     }

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

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

   370 //     }

   371 //   }

   373   LpGlpk::SolveExitStatus LpGlpk::_solve()

   374   {

   375     int i=  lpx_simplex(lp);

   376     switch (i) {

   377     case LPX_E_OK:

   378       return SOLVED;

   379       break;

   380     default:

   381       return UNSOLVED;

   382     }

   383   }

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

   386   {

   387     return lpx_get_col_prim(lp,i);

   388   }

   390   LpGlpk::Value LpGlpk::_getPrimalValue()

   391   {

   392     return lpx_get_obj_val(lp);

   393   }

   396   LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()

   397   {

   398     int stat=  lpx_get_status(lp);

   399     switch (stat) {

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

   401       return UNDEFINED;

   402       break;

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

   404     case LPX_INFEAS://Infeasible

   405       return INFEASIBLE;

   406       break;

   407     case LPX_UNBND://Unbounded

   408       return INFINITE;

   409       break;

   410     case LPX_FEAS://Feasible

   411       return FEASIBLE;

   412       break;

   413     case LPX_OPT://Feasible

   414       return OPTIMAL;

   415       break;

   416     default:

   417       return UNDEFINED; //to avoid gcc warning

   418       //FIXME error

   419     }

   420   }

   423   void LpGlpk::_setMax()

   424   {

   425     lpx_set_obj_dir(lp, LPX_MAX);

   426   }

   428   void LpGlpk::_setMin()

   429   {

   430     lpx_set_obj_dir(lp, LPX_MIN);

   431   }

   434   void LpGlpk::messageLevel(int m)

   435   {

   436     lpx_set_int_parm(lp, LPX_K_MSGLEV, m);

   437   }

   439   void LpGlpk::presolver(bool b)

   440   {

   441     lpx_set_int_parm(lp, LPX_K_PRESOL, b);

   442   }

   445 } //END OF NAMESPACE LEMON

   447 #endif //LEMON_LP_GLPK_CC

author	athos
	Fri, 20 May 2005 09:43:40 +0000
changeset 1432	46b088b01f88
parent 1431	ad44b1dd8013
permissions	-rw-r--r--