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