lemon/lp_glpk.cc
author deba
Tue, 06 Mar 2007 17:04:16 +0000
changeset 2395 fe5966d8acfc
parent 2386 81b47fc5c444
child 2441 d8d6ab871608
permissions -rw-r--r--
Correction of urls and email addresses
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2007
     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  */
    18 
    19 ///\file
    20 ///\brief Implementation of the LEMON-GLPK lp solver interface.
    21 
    22 #include <lemon/lp_glpk.h>
    23 //#include <iostream>
    24 namespace lemon {
    25 
    26 
    27   LpGlpk::LpGlpk() : Parent() {
    28     rows = _lp_bits::LpId(1);
    29     cols = _lp_bits::LpId(1);
    30     lp = lpx_create_prob();
    31     lpx_create_index(lp);
    32     ///\todo control function for this:
    33     lpx_set_int_parm(lp, LPX_K_DUAL, 1);
    34     messageLevel(0);
    35   }
    36   
    37   LpGlpk::LpGlpk(const LpGlpk &glp) : Parent() {
    38     rows = _lp_bits::LpId(1);
    39     cols = _lp_bits::LpId(1);
    40     lp = lpx_create_prob();
    41     lpx_create_index(lp);
    42     ///\todo control function for this:
    43     lpx_set_int_parm(lp, LPX_K_DUAL, 1);
    44     messageLevel(0);
    45     //Coefficient matrix, row bounds
    46     lpx_add_rows(lp, lpx_get_num_rows(glp.lp));
    47     lpx_add_cols(lp, lpx_get_num_cols(glp.lp));
    48     int len;
    49     int ind[1+lpx_get_num_cols(glp.lp)];
    50     Value val[1+lpx_get_num_cols(glp.lp)];
    51     for (int i=1;i<=lpx_get_num_rows(glp.lp);++i)
    52       {
    53 	len=lpx_get_mat_row(glp.lp,i,ind,val);
    54 	lpx_set_mat_row(lp, i,len,ind,val);
    55 	lpx_set_row_bnds(lp,i,lpx_get_row_type(glp.lp,i),
    56 			 lpx_get_row_lb(glp.lp,i),lpx_get_row_ub(glp.lp,i));
    57       }
    58 
    59     //Objective function, coloumn bounds
    60     lpx_set_obj_dir(lp, lpx_get_obj_dir(glp.lp));
    61     //Objectif function's constant term treated separately
    62     lpx_set_obj_coef(lp,0,lpx_get_obj_coef(glp.lp,0));
    63     for (int i=1;i<=lpx_get_num_cols(glp.lp);++i)
    64       {
    65 	lpx_set_obj_coef(lp,i,lpx_get_obj_coef(glp.lp,i));
    66 	lpx_set_col_bnds(lp,i,lpx_get_col_type(glp.lp,i),
    67 			 lpx_get_col_lb(glp.lp,i),lpx_get_col_ub(glp.lp,i));
    68       }
    69   }
    70   
    71   LpGlpk::~LpGlpk() {
    72     lpx_delete_prob(lp);
    73   }
    74   
    75   int LpGlpk::_addCol() { 
    76     int i=lpx_add_cols(lp, 1);
    77     _setColLowerBound(i, -INF);
    78     _setColUpperBound(i, INF);
    79     return i;
    80   }
    81 
    82   ///\e
    83 
    84 
    85   LpSolverBase &LpGlpk::_newLp()
    86   {
    87     LpGlpk* newlp=new LpGlpk;
    88     return *newlp;
    89   }
    90   
    91   ///\e
    92 
    93   LpSolverBase &LpGlpk::_copyLp()
    94   {
    95     LpGlpk* newlp=new LpGlpk(*this);
    96     return *newlp;
    97   }
    98 
    99   int LpGlpk::_addRow() { 
   100     int i=lpx_add_rows(lp, 1);
   101     return i;
   102   }
   103 
   104   
   105   void LpGlpk::_eraseCol(int i) {
   106     int ca[2];
   107     ca[1]=i;
   108     lpx_del_cols(lp, 1, ca);
   109   }
   110   
   111   void LpGlpk::_eraseRow(int i) {
   112     int ra[2];
   113     ra[1]=i;
   114     lpx_del_rows(lp, 1, ra);
   115   }
   116 
   117   void LpGlpk::_getColName(int c, std::string & name) const
   118   {
   119     
   120     char *n = lpx_get_col_name(lp,c);
   121     name = n?n:"";
   122   }
   123   
   124   
   125   void LpGlpk::_setColName(int c, const std::string & name)
   126   {
   127     lpx_set_col_name(lp,c,const_cast<char*>(name.c_str()));
   128 
   129   }
   130 
   131   int LpGlpk::_colByName(const std::string& name) const
   132   {
   133     int k = lpx_find_col(lp, const_cast<char*>(name.c_str()));
   134     return k > 0 ? k : -1; 
   135   }
   136 
   137   
   138   void LpGlpk::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e) 
   139   {
   140     std::vector<int> indices;
   141     std::vector<Value> values;
   142 
   143     indices.push_back(0);
   144     values.push_back(0);
   145 
   146     for(ConstRowIterator it=b; it!=e; ++it) {
   147       indices.push_back(it->first);
   148       values.push_back(it->second);
   149     }
   150 
   151     lpx_set_mat_row(lp, i, values.size() - 1, &indices[0], &values[0]);
   152   }
   153 
   154   void LpGlpk::_getRowCoeffs(int ix, RowIterator b) const
   155   {
   156     int length = lpx_get_mat_row(lp, ix, 0, 0);
   157     
   158     std::vector<int> indices(length + 1);
   159     std::vector<Value> values(length + 1);
   160     
   161     lpx_get_mat_row(lp, ix, &indices[0], &values[0]);
   162     
   163     for (int i = 1; i <= length; ++i) {
   164       *b = std::make_pair(indices[i], values[i]);
   165       ++b;
   166     }
   167   }
   168   
   169   void LpGlpk::_setColCoeffs(int ix, ConstColIterator b, ConstColIterator e) {
   170 
   171     std::vector<int> indices;
   172     std::vector<Value> values;
   173 
   174     indices.push_back(0);
   175     values.push_back(0);
   176 
   177     for(ConstColIterator it=b; it!=e; ++it) {
   178       indices.push_back(it->first);
   179       values.push_back(it->second);
   180     }
   181     
   182     lpx_set_mat_col(lp, ix, values.size() - 1, &indices[0], &values[0]);
   183   }
   184 
   185   void LpGlpk::_getColCoeffs(int ix, ColIterator b) const
   186   {
   187     int length = lpx_get_mat_col(lp, ix, 0, 0);
   188     
   189     std::vector<int> indices(length + 1);
   190     std::vector<Value> values(length + 1);
   191     
   192     lpx_get_mat_col(lp, ix, &indices[0], &values[0]);
   193     
   194     for (int i = 1; i <= length; ++i) {
   195       *b = std::make_pair(indices[i], values[i]);
   196       ++b;
   197     }
   198   }
   199 
   200   void LpGlpk::_setCoeff(int ix, int jx, Value value) 
   201   {
   202 
   203     if (lpx_get_num_cols(lp) < lpx_get_num_rows(lp)) {
   204 
   205       int length=lpx_get_mat_row(lp, ix, 0, 0);
   206       
   207       std::vector<int> indices(length + 2);
   208       std::vector<Value> values(length + 2);
   209       
   210       lpx_get_mat_row(lp, ix, &indices[0], &values[0]);
   211       
   212       //The following code does not suppose that the elements of the
   213       //array indices are sorted
   214       bool found=false;
   215       for (int i = 1; i <= length; ++i) {
   216         if (indices[i]==jx){
   217           found=true;
   218           values[i]=value;
   219           break;
   220         }
   221       }
   222       if (!found){
   223         ++length;
   224         indices[length]=jx;
   225         values[length]=value;
   226       }
   227     
   228       lpx_set_mat_row(lp, ix, length, &indices[0], &values[0]);
   229 
   230     } else {
   231 
   232       int length=lpx_get_mat_col(lp, jx, 0, 0);
   233       
   234       std::vector<int> indices(length + 2);
   235       std::vector<Value> values(length + 2);
   236       
   237       lpx_get_mat_col(lp, jx, &indices[0], &values[0]);
   238       
   239       //The following code does not suppose that the elements of the
   240       //array indices are sorted
   241       bool found=false;
   242       for (int i = 1; i <= length; ++i) {
   243         if (indices[i]==jx){
   244           found=true;
   245           values[i]=value;
   246           break;
   247         }
   248       }
   249       if (!found){
   250         ++length;
   251         indices[length]=ix;
   252         values[length]=value;
   253       }
   254     
   255       lpx_set_mat_col(lp, jx, length, &indices[0], &values[0]);
   256     }
   257   }
   258 
   259   LpGlpk::Value LpGlpk::_getCoeff(int ix, int jx) const
   260   {
   261 
   262     int length=lpx_get_mat_row(lp, ix, 0, 0);
   263     
   264     std::vector<int> indices(length + 1);
   265     std::vector<Value> values(length + 1);
   266     
   267     lpx_get_mat_row(lp, ix, &indices[0], &values[0]);
   268     
   269     //The following code does not suppose that the elements of the
   270     //array indices are sorted
   271     for (int i = 1; i <= length; ++i) {
   272       if (indices[i]==jx){
   273 	return values[i];
   274       }
   275     }
   276     return 0;
   277 
   278   }
   279 
   280 
   281   void LpGlpk::_setColLowerBound(int i, Value lo)
   282   {
   283     if (lo==INF) {
   284       //FIXME error
   285     }
   286     int b=lpx_get_col_type(lp, i);
   287     double up=lpx_get_col_ub(lp, i);	
   288     if (lo==-INF) {
   289       switch (b) {
   290       case LPX_FR:
   291       case LPX_LO:
   292 	lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
   293 	break;
   294       case LPX_UP:
   295 	break;
   296       case LPX_DB:
   297       case LPX_FX:
   298 	lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
   299 	break;
   300       default: ;
   301 	//FIXME error
   302       }
   303     } else {
   304       switch (b) {
   305       case LPX_FR:
   306       case LPX_LO:
   307 	lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
   308 	break;
   309       case LPX_UP:	  
   310       case LPX_DB:
   311       case LPX_FX:
   312 	if (lo==up) 
   313 	  lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
   314 	else 
   315 	  lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
   316 	break;
   317       default: ;
   318 	//FIXME error
   319       }
   320     }
   321 
   322   }
   323 
   324   LpGlpk::Value LpGlpk::_getColLowerBound(int i) const
   325   {
   326     int b=lpx_get_col_type(lp, i);
   327       switch (b) {
   328       case LPX_LO:
   329       case LPX_DB:
   330       case LPX_FX:
   331 	return lpx_get_col_lb(lp, i);	
   332       default: ;
   333 	return -INF;
   334       }
   335   }
   336   
   337   void LpGlpk::_setColUpperBound(int i, Value up)
   338   {
   339     if (up==-INF) {
   340       //FIXME error
   341     }
   342     int b=lpx_get_col_type(lp, i);
   343     double lo=lpx_get_col_lb(lp, i);
   344     if (up==INF) {
   345       switch (b) {
   346       case LPX_FR:
   347       case LPX_LO:
   348 	break;
   349       case LPX_UP:
   350 	lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
   351 	break;
   352       case LPX_DB:
   353       case LPX_FX:
   354 	lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
   355 	break;
   356       default: ;
   357 	//FIXME error
   358       }
   359     } else {
   360       switch (b) {
   361       case LPX_FR:
   362 	lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
   363 	break;
   364       case LPX_UP:
   365 	lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
   366 	break;
   367       case LPX_LO:
   368       case LPX_DB:
   369       case LPX_FX:
   370 	if (lo==up) 
   371 	  lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
   372 	else 
   373 	  lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
   374 	break;
   375       default: ;
   376 	//FIXME error
   377       }
   378     }
   379   }
   380 
   381   LpGlpk::Value LpGlpk::_getColUpperBound(int i) const
   382   {
   383     int b=lpx_get_col_type(lp, i);
   384       switch (b) {
   385       case LPX_UP:
   386       case LPX_DB:
   387       case LPX_FX:
   388 	return lpx_get_col_ub(lp, i);	
   389       default: ;
   390 	return INF;
   391       }
   392   }
   393   
   394   void LpGlpk::_setRowBounds(int i, Value lb, Value ub)
   395   {
   396     //Bad parameter
   397     if (lb==INF || ub==-INF) {
   398       //FIXME error
   399     }
   400 
   401     if (lb == -INF){
   402       if (ub == INF){
   403 	lpx_set_row_bnds(lp, i, LPX_FR, lb, ub);
   404       }
   405       else{
   406 	lpx_set_row_bnds(lp, i, LPX_UP, lb, ub);
   407       }
   408     }
   409     else{
   410       if (ub==INF){
   411 	lpx_set_row_bnds(lp, i, LPX_LO, lb, ub);
   412 
   413       }
   414       else{
   415 	if (lb == ub){
   416 	  lpx_set_row_bnds(lp, i, LPX_FX, lb, ub);
   417 	}
   418 	else{
   419 	  lpx_set_row_bnds(lp, i, LPX_DB, lb, ub);
   420 	}
   421       }
   422     }
   423 
   424   }
   425 
   426   void LpGlpk::_getRowBounds(int i, Value &lb, Value &ub) const
   427   {
   428 
   429     int b=lpx_get_row_type(lp, i);
   430     switch (b) {
   431     case LPX_FR:
   432     case LPX_UP:
   433       lb = -INF;
   434 	break;
   435     default: 
   436       lb=lpx_get_row_lb(lp, i);
   437     }
   438 
   439     switch (b) {
   440     case LPX_FR:
   441     case LPX_LO:
   442       ub = INF;
   443 	break;
   444     default: 
   445       ub=lpx_get_row_ub(lp, i);
   446     }
   447     
   448   }
   449   
   450   void LpGlpk::_setObjCoeff(int i, Value obj_coef)
   451   {
   452     //i=0 means the constant term (shift)
   453     lpx_set_obj_coef(lp, i, obj_coef);
   454   }
   455 
   456   LpGlpk::Value LpGlpk::_getObjCoeff(int i) const {
   457     //i=0 means the constant term (shift)
   458     return lpx_get_obj_coef(lp, i);
   459   }
   460 
   461   void LpGlpk::_clearObj()
   462   {
   463     for (int i=0;i<=lpx_get_num_cols(lp);++i){
   464       lpx_set_obj_coef(lp, i, 0);
   465     }
   466   }
   467 
   468   LpGlpk::SolveExitStatus LpGlpk::_solve()
   469   {
   470     // A way to check the problem to be solved
   471     //lpx_write_cpxlp(lp,"naittvan.cpx");    
   472 
   473     lpx_std_basis(lp);
   474     int i =  lpx_simplex(lp);
   475     
   476     switch (i) {
   477     case LPX_E_OK: 
   478       return SOLVED;
   479     default:
   480       return UNSOLVED;
   481     }
   482   }
   483 
   484   LpGlpk::Value LpGlpk::_getPrimal(int i) const
   485   {
   486     return lpx_get_col_prim(lp,i);
   487   }
   488 
   489   LpGlpk::Value LpGlpk::_getDual(int i) const
   490   {
   491     return lpx_get_row_dual(lp,i);
   492   }
   493   
   494   LpGlpk::Value LpGlpk::_getPrimalValue() const
   495   {
   496     return lpx_get_obj_val(lp);
   497   }
   498   bool LpGlpk::_isBasicCol(int i) const
   499   {
   500     return (lpx_get_col_stat(lp, i)==LPX_BS);
   501   }
   502   
   503  
   504   LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus() const
   505   {
   506     int stat=  lpx_get_status(lp);
   507     switch (stat) {
   508     case LPX_UNDEF://Undefined (no solve has been run yet)
   509       return UNDEFINED;
   510     case LPX_NOFEAS://There is no feasible solution (primal, I guess)
   511     case LPX_INFEAS://Infeasible 
   512       return INFEASIBLE;
   513     case LPX_UNBND://Unbounded
   514       return INFINITE;
   515     case LPX_FEAS://Feasible
   516       return FEASIBLE;
   517     case LPX_OPT://Feasible
   518       return OPTIMAL;
   519     default:
   520       return UNDEFINED; //to avoid gcc warning
   521       //FIXME error
   522     }
   523   }
   524 
   525   LpGlpk::SolutionStatus LpGlpk::_getDualStatus() const
   526   {
   527     switch (lpx_get_dual_stat(lp)) {
   528     case LPX_D_UNDEF://Undefined (no solve has been run yet)
   529       return UNDEFINED;
   530     case LPX_D_NOFEAS://There is no dual feasible solution 
   531 //    case LPX_D_INFEAS://Infeasible 
   532       return INFEASIBLE;
   533     case LPX_D_FEAS://Feasible    
   534       switch (lpx_get_status(lp)) {
   535       case LPX_NOFEAS:
   536 	return INFINITE;
   537       case LPX_OPT:
   538 	return OPTIMAL;
   539       default:
   540 	return FEASIBLE;
   541       }
   542     default:
   543       return UNDEFINED; //to avoid gcc warning
   544       //FIXME error
   545     }
   546   }
   547 
   548   LpGlpk::ProblemTypes LpGlpk::_getProblemType() const
   549   {
   550       //int stat=  lpx_get_status(lp);
   551     int statp=  lpx_get_prim_stat(lp);
   552     int statd=  lpx_get_dual_stat(lp);
   553     if (statp==LPX_P_FEAS && statd==LPX_D_FEAS)
   554 	return PRIMAL_DUAL_FEASIBLE;
   555     if (statp==LPX_P_FEAS && statd==LPX_D_NOFEAS)
   556 	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
   557     if (statp==LPX_P_NOFEAS && statd==LPX_D_FEAS)
   558 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
   559     if (statp==LPX_P_NOFEAS && statd==LPX_D_NOFEAS)
   560 	return PRIMAL_DUAL_INFEASIBLE;
   561     //In all other cases
   562     return UNKNOWN;
   563   }
   564 
   565   void LpGlpk::_setMax()
   566   {
   567     lpx_set_obj_dir(lp, LPX_MAX);
   568   }
   569 
   570   void LpGlpk::_setMin()
   571   {
   572     lpx_set_obj_dir(lp, LPX_MIN);
   573   }
   574 
   575   bool LpGlpk::_isMax() const
   576   {
   577     return (lpx_get_obj_dir(lp)==LPX_MAX);
   578   }
   579 
   580  
   581 
   582   void LpGlpk::messageLevel(int m)
   583   {
   584     lpx_set_int_parm(lp, LPX_K_MSGLEV, m);
   585   }
   586 
   587   void LpGlpk::presolver(bool b)
   588   {
   589     lpx_set_int_parm(lp, LPX_K_PRESOL, b);
   590   }
   591 
   592  
   593 } //END OF NAMESPACE LEMON