lemon/glpk.cc
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 30 Mar 2009 16:46:37 +0100
changeset 561 6e0525ec5355
parent 542 fc6c7aab4b8d
child 565 7ab97e2a0c33
permissions -rw-r--r--
Accept negative values as unbounded capacity in dimacs readers (#243)
and some doc improvements.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     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 and MIP solver interface.
    21 
    22 #include <lemon/glpk.h>
    23 #include <glpk.h>
    24 
    25 #include <lemon/assert.h>
    26 
    27 namespace lemon {
    28 
    29   // GlpkBase members
    30 
    31   GlpkBase::GlpkBase() : LpBase() {
    32     lp = glp_create_prob();
    33     glp_create_index(lp);
    34   }
    35 
    36   GlpkBase::GlpkBase(const GlpkBase &other) : LpBase() {
    37     lp = glp_create_prob();
    38     glp_copy_prob(lp, other.lp, GLP_ON);
    39     glp_create_index(lp);
    40     rows = other.rows;
    41     cols = other.cols;
    42   }
    43 
    44   GlpkBase::~GlpkBase() {
    45     glp_delete_prob(lp);
    46   }
    47 
    48   int GlpkBase::_addCol() {
    49     int i = glp_add_cols(lp, 1);
    50     glp_set_col_bnds(lp, i, GLP_FR, 0.0, 0.0);
    51     return i;
    52   }
    53 
    54   int GlpkBase::_addRow() {
    55     int i = glp_add_rows(lp, 1);
    56     glp_set_row_bnds(lp, i, GLP_FR, 0.0, 0.0);
    57     return i;
    58   }
    59 
    60   void GlpkBase::_eraseCol(int i) {
    61     int ca[2];
    62     ca[1] = i;
    63     glp_del_cols(lp, 1, ca);
    64   }
    65 
    66   void GlpkBase::_eraseRow(int i) {
    67     int ra[2];
    68     ra[1] = i;
    69     glp_del_rows(lp, 1, ra);
    70   }
    71 
    72   void GlpkBase::_eraseColId(int i) {
    73     cols.eraseIndex(i);
    74     cols.shiftIndices(i);
    75   }
    76 
    77   void GlpkBase::_eraseRowId(int i) {
    78     rows.eraseIndex(i);
    79     rows.shiftIndices(i);
    80   }
    81 
    82   void GlpkBase::_getColName(int c, std::string& name) const {
    83     const char *str = glp_get_col_name(lp, c);
    84     if (str) name = str;
    85     else name.clear();
    86   }
    87 
    88   void GlpkBase::_setColName(int c, const std::string & name) {
    89     glp_set_col_name(lp, c, const_cast<char*>(name.c_str()));
    90 
    91   }
    92 
    93   int GlpkBase::_colByName(const std::string& name) const {
    94     int k = glp_find_col(lp, const_cast<char*>(name.c_str()));
    95     return k > 0 ? k : -1;
    96   }
    97 
    98   void GlpkBase::_getRowName(int r, std::string& name) const {
    99     const char *str = glp_get_row_name(lp, r);
   100     if (str) name = str;
   101     else name.clear();
   102   }
   103 
   104   void GlpkBase::_setRowName(int r, const std::string & name) {
   105     glp_set_row_name(lp, r, const_cast<char*>(name.c_str()));
   106 
   107   }
   108 
   109   int GlpkBase::_rowByName(const std::string& name) const {
   110     int k = glp_find_row(lp, const_cast<char*>(name.c_str()));
   111     return k > 0 ? k : -1;
   112   }
   113 
   114   void GlpkBase::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
   115     std::vector<int> indexes;
   116     std::vector<Value> values;
   117 
   118     indexes.push_back(0);
   119     values.push_back(0);
   120 
   121     for(ExprIterator it = b; it != e; ++it) {
   122       indexes.push_back(it->first);
   123       values.push_back(it->second);
   124     }
   125 
   126     glp_set_mat_row(lp, i, values.size() - 1,
   127                     &indexes.front(), &values.front());
   128   }
   129 
   130   void GlpkBase::_getRowCoeffs(int ix, InsertIterator b) const {
   131     int length = glp_get_mat_row(lp, ix, 0, 0);
   132 
   133     std::vector<int> indexes(length + 1);
   134     std::vector<Value> values(length + 1);
   135 
   136     glp_get_mat_row(lp, ix, &indexes.front(), &values.front());
   137 
   138     for (int i = 1; i <= length; ++i) {
   139       *b = std::make_pair(indexes[i], values[i]);
   140       ++b;
   141     }
   142   }
   143 
   144   void GlpkBase::_setColCoeffs(int ix, ExprIterator b,
   145                                      ExprIterator e) {
   146 
   147     std::vector<int> indexes;
   148     std::vector<Value> values;
   149 
   150     indexes.push_back(0);
   151     values.push_back(0);
   152 
   153     for(ExprIterator it = b; it != e; ++it) {
   154       indexes.push_back(it->first);
   155       values.push_back(it->second);
   156     }
   157 
   158     glp_set_mat_col(lp, ix, values.size() - 1,
   159                     &indexes.front(), &values.front());
   160   }
   161 
   162   void GlpkBase::_getColCoeffs(int ix, InsertIterator b) const {
   163     int length = glp_get_mat_col(lp, ix, 0, 0);
   164 
   165     std::vector<int> indexes(length + 1);
   166     std::vector<Value> values(length + 1);
   167 
   168     glp_get_mat_col(lp, ix, &indexes.front(), &values.front());
   169 
   170     for (int i = 1; i  <= length; ++i) {
   171       *b = std::make_pair(indexes[i], values[i]);
   172       ++b;
   173     }
   174   }
   175 
   176   void GlpkBase::_setCoeff(int ix, int jx, Value value) {
   177 
   178     if (glp_get_num_cols(lp) < glp_get_num_rows(lp)) {
   179 
   180       int length = glp_get_mat_row(lp, ix, 0, 0);
   181 
   182       std::vector<int> indexes(length + 2);
   183       std::vector<Value> values(length + 2);
   184 
   185       glp_get_mat_row(lp, ix, &indexes.front(), &values.front());
   186 
   187       //The following code does not suppose that the elements of the
   188       //array indexes are sorted
   189       bool found = false;
   190       for (int i = 1; i  <= length; ++i) {
   191         if (indexes[i] == jx) {
   192           found = true;
   193           values[i] = value;
   194           break;
   195         }
   196       }
   197       if (!found) {
   198         ++length;
   199         indexes[length] = jx;
   200         values[length] = value;
   201       }
   202 
   203       glp_set_mat_row(lp, ix, length, &indexes.front(), &values.front());
   204 
   205     } else {
   206 
   207       int length = glp_get_mat_col(lp, jx, 0, 0);
   208 
   209       std::vector<int> indexes(length + 2);
   210       std::vector<Value> values(length + 2);
   211 
   212       glp_get_mat_col(lp, jx, &indexes.front(), &values.front());
   213 
   214       //The following code does not suppose that the elements of the
   215       //array indexes are sorted
   216       bool found = false;
   217       for (int i = 1; i <= length; ++i) {
   218         if (indexes[i] == ix) {
   219           found = true;
   220           values[i] = value;
   221           break;
   222         }
   223       }
   224       if (!found) {
   225         ++length;
   226         indexes[length] = ix;
   227         values[length] = value;
   228       }
   229 
   230       glp_set_mat_col(lp, jx, length, &indexes.front(), &values.front());
   231     }
   232 
   233   }
   234 
   235   GlpkBase::Value GlpkBase::_getCoeff(int ix, int jx) const {
   236 
   237     int length = glp_get_mat_row(lp, ix, 0, 0);
   238 
   239     std::vector<int> indexes(length + 1);
   240     std::vector<Value> values(length + 1);
   241 
   242     glp_get_mat_row(lp, ix, &indexes.front(), &values.front());
   243 
   244     for (int i = 1; i  <= length; ++i) {
   245       if (indexes[i] == jx) {
   246         return values[i];
   247       }
   248     }
   249 
   250     return 0;
   251   }
   252 
   253   void GlpkBase::_setColLowerBound(int i, Value lo) {
   254     LEMON_ASSERT(lo != INF, "Invalid bound");
   255 
   256     int b = glp_get_col_type(lp, i);
   257     double up = glp_get_col_ub(lp, i);
   258     if (lo == -INF) {
   259       switch (b) {
   260       case GLP_FR:
   261       case GLP_LO:
   262         glp_set_col_bnds(lp, i, GLP_FR, lo, up);
   263         break;
   264       case GLP_UP:
   265         break;
   266       case GLP_DB:
   267       case GLP_FX:
   268         glp_set_col_bnds(lp, i, GLP_UP, lo, up);
   269         break;
   270       default:
   271         break;
   272       }
   273     } else {
   274       switch (b) {
   275       case GLP_FR:
   276       case GLP_LO:
   277         glp_set_col_bnds(lp, i, GLP_LO, lo, up);
   278         break;
   279       case GLP_UP:
   280       case GLP_DB:
   281       case GLP_FX:
   282         if (lo == up)
   283           glp_set_col_bnds(lp, i, GLP_FX, lo, up);
   284         else
   285           glp_set_col_bnds(lp, i, GLP_DB, lo, up);
   286         break;
   287       default:
   288         break;
   289       }
   290     }
   291   }
   292 
   293   GlpkBase::Value GlpkBase::_getColLowerBound(int i) const {
   294     int b = glp_get_col_type(lp, i);
   295     switch (b) {
   296     case GLP_LO:
   297     case GLP_DB:
   298     case GLP_FX:
   299       return glp_get_col_lb(lp, i);
   300     default:
   301       return -INF;
   302     }
   303   }
   304 
   305   void GlpkBase::_setColUpperBound(int i, Value up) {
   306     LEMON_ASSERT(up != -INF, "Invalid bound");
   307 
   308     int b = glp_get_col_type(lp, i);
   309     double lo = glp_get_col_lb(lp, i);
   310     if (up == INF) {
   311       switch (b) {
   312       case GLP_FR:
   313       case GLP_LO:
   314         break;
   315       case GLP_UP:
   316         glp_set_col_bnds(lp, i, GLP_FR, lo, up);
   317         break;
   318       case GLP_DB:
   319       case GLP_FX:
   320         glp_set_col_bnds(lp, i, GLP_LO, lo, up);
   321         break;
   322       default:
   323         break;
   324       }
   325     } else {
   326       switch (b) {
   327       case GLP_FR:
   328         glp_set_col_bnds(lp, i, GLP_UP, lo, up);
   329         break;
   330       case GLP_UP:
   331         glp_set_col_bnds(lp, i, GLP_UP, lo, up);
   332         break;
   333       case GLP_LO:
   334       case GLP_DB:
   335       case GLP_FX:
   336         if (lo == up)
   337           glp_set_col_bnds(lp, i, GLP_FX, lo, up);
   338         else
   339           glp_set_col_bnds(lp, i, GLP_DB, lo, up);
   340         break;
   341       default:
   342         break;
   343       }
   344     }
   345 
   346   }
   347 
   348   GlpkBase::Value GlpkBase::_getColUpperBound(int i) const {
   349     int b = glp_get_col_type(lp, i);
   350       switch (b) {
   351       case GLP_UP:
   352       case GLP_DB:
   353       case GLP_FX:
   354         return glp_get_col_ub(lp, i);
   355       default:
   356         return INF;
   357       }
   358   }
   359 
   360   void GlpkBase::_setRowLowerBound(int i, Value lo) {
   361     LEMON_ASSERT(lo != INF, "Invalid bound");
   362 
   363     int b = glp_get_row_type(lp, i);
   364     double up = glp_get_row_ub(lp, i);
   365     if (lo == -INF) {
   366       switch (b) {
   367       case GLP_FR:
   368       case GLP_LO:
   369         glp_set_row_bnds(lp, i, GLP_FR, lo, up);
   370         break;
   371       case GLP_UP:
   372         break;
   373       case GLP_DB:
   374       case GLP_FX:
   375         glp_set_row_bnds(lp, i, GLP_UP, lo, up);
   376         break;
   377       default:
   378         break;
   379       }
   380     } else {
   381       switch (b) {
   382       case GLP_FR:
   383       case GLP_LO:
   384         glp_set_row_bnds(lp, i, GLP_LO, lo, up);
   385         break;
   386       case GLP_UP:
   387       case GLP_DB:
   388       case GLP_FX:
   389         if (lo == up)
   390           glp_set_row_bnds(lp, i, GLP_FX, lo, up);
   391         else
   392           glp_set_row_bnds(lp, i, GLP_DB, lo, up);
   393         break;
   394       default:
   395         break;
   396       }
   397     }
   398 
   399   }
   400 
   401   GlpkBase::Value GlpkBase::_getRowLowerBound(int i) const {
   402     int b = glp_get_row_type(lp, i);
   403     switch (b) {
   404     case GLP_LO:
   405     case GLP_DB:
   406     case GLP_FX:
   407       return glp_get_row_lb(lp, i);
   408     default:
   409       return -INF;
   410     }
   411   }
   412 
   413   void GlpkBase::_setRowUpperBound(int i, Value up) {
   414     LEMON_ASSERT(up != -INF, "Invalid bound");
   415 
   416     int b = glp_get_row_type(lp, i);
   417     double lo = glp_get_row_lb(lp, i);
   418     if (up == INF) {
   419       switch (b) {
   420       case GLP_FR:
   421       case GLP_LO:
   422         break;
   423       case GLP_UP:
   424         glp_set_row_bnds(lp, i, GLP_FR, lo, up);
   425         break;
   426       case GLP_DB:
   427       case GLP_FX:
   428         glp_set_row_bnds(lp, i, GLP_LO, lo, up);
   429         break;
   430       default:
   431         break;
   432       }
   433     } else {
   434       switch (b) {
   435       case GLP_FR:
   436         glp_set_row_bnds(lp, i, GLP_UP, lo, up);
   437         break;
   438       case GLP_UP:
   439         glp_set_row_bnds(lp, i, GLP_UP, lo, up);
   440         break;
   441       case GLP_LO:
   442       case GLP_DB:
   443       case GLP_FX:
   444         if (lo == up)
   445           glp_set_row_bnds(lp, i, GLP_FX, lo, up);
   446         else
   447           glp_set_row_bnds(lp, i, GLP_DB, lo, up);
   448         break;
   449       default:
   450         break;
   451       }
   452     }
   453   }
   454 
   455   GlpkBase::Value GlpkBase::_getRowUpperBound(int i) const {
   456     int b = glp_get_row_type(lp, i);
   457     switch (b) {
   458     case GLP_UP:
   459     case GLP_DB:
   460     case GLP_FX:
   461       return glp_get_row_ub(lp, i);
   462     default:
   463       return INF;
   464     }
   465   }
   466 
   467   void GlpkBase::_setObjCoeffs(ExprIterator b, ExprIterator e) {
   468     for (int i = 1; i <= glp_get_num_cols(lp); ++i) {
   469       glp_set_obj_coef(lp, i, 0.0);
   470     }
   471     for (ExprIterator it = b; it != e; ++it) {
   472       glp_set_obj_coef(lp, it->first, it->second);
   473     }
   474   }
   475 
   476   void GlpkBase::_getObjCoeffs(InsertIterator b) const {
   477     for (int i = 1; i <= glp_get_num_cols(lp); ++i) {
   478       Value val = glp_get_obj_coef(lp, i);
   479       if (val != 0.0) {
   480         *b = std::make_pair(i, val);
   481         ++b;
   482       }
   483     }
   484   }
   485 
   486   void GlpkBase::_setObjCoeff(int i, Value obj_coef) {
   487     //i = 0 means the constant term (shift)
   488     glp_set_obj_coef(lp, i, obj_coef);
   489   }
   490 
   491   GlpkBase::Value GlpkBase::_getObjCoeff(int i) const {
   492     //i = 0 means the constant term (shift)
   493     return glp_get_obj_coef(lp, i);
   494   }
   495 
   496   void GlpkBase::_setSense(GlpkBase::Sense sense) {
   497     switch (sense) {
   498     case MIN:
   499       glp_set_obj_dir(lp, GLP_MIN);
   500       break;
   501     case MAX:
   502       glp_set_obj_dir(lp, GLP_MAX);
   503       break;
   504     }
   505   }
   506 
   507   GlpkBase::Sense GlpkBase::_getSense() const {
   508     switch(glp_get_obj_dir(lp)) {
   509     case GLP_MIN:
   510       return MIN;
   511     case GLP_MAX:
   512       return MAX;
   513     default:
   514       LEMON_ASSERT(false, "Wrong sense");
   515       return GlpkBase::Sense();
   516     }
   517   }
   518 
   519   void GlpkBase::_clear() {
   520     glp_erase_prob(lp);
   521     rows.clear();
   522     cols.clear();
   523   }
   524 
   525   void GlpkBase::freeEnv() {
   526     glp_free_env();
   527   }
   528 
   529   GlpkBase::FreeEnvHelper GlpkBase::freeEnvHelper;
   530 
   531   // GlpkLp members
   532 
   533   GlpkLp::GlpkLp()
   534     : LpBase(), LpSolver(), GlpkBase() {
   535     messageLevel(MESSAGE_NO_OUTPUT);
   536   }
   537 
   538   GlpkLp::GlpkLp(const GlpkLp& other)
   539     : LpBase(other), LpSolver(other), GlpkBase(other) {
   540     messageLevel(MESSAGE_NO_OUTPUT);
   541   }
   542 
   543   GlpkLp* GlpkLp::newSolver() const { return new GlpkLp; }
   544   GlpkLp* GlpkLp::cloneSolver() const { return new GlpkLp(*this); }
   545 
   546   const char* GlpkLp::_solverName() const { return "GlpkLp"; }
   547 
   548   void GlpkLp::_clear_temporals() {
   549     _primal_ray.clear();
   550     _dual_ray.clear();
   551   }
   552 
   553   GlpkLp::SolveExitStatus GlpkLp::_solve() {
   554     return solvePrimal();
   555   }
   556 
   557   GlpkLp::SolveExitStatus GlpkLp::solvePrimal() {
   558     _clear_temporals();
   559 
   560     glp_smcp smcp;
   561     glp_init_smcp(&smcp);
   562 
   563     switch (_message_level) {
   564     case MESSAGE_NO_OUTPUT:
   565       smcp.msg_lev = GLP_MSG_OFF;
   566       break;
   567     case MESSAGE_ERROR_MESSAGE:
   568       smcp.msg_lev = GLP_MSG_ERR;
   569       break;
   570     case MESSAGE_NORMAL_OUTPUT:
   571       smcp.msg_lev = GLP_MSG_ON;
   572       break;
   573     case MESSAGE_FULL_OUTPUT:
   574       smcp.msg_lev = GLP_MSG_ALL;
   575       break;
   576     }
   577 
   578     if (glp_simplex(lp, &smcp) != 0) return UNSOLVED;
   579     return SOLVED;
   580   }
   581 
   582   GlpkLp::SolveExitStatus GlpkLp::solveDual() {
   583     _clear_temporals();
   584 
   585     glp_smcp smcp;
   586     glp_init_smcp(&smcp);
   587 
   588     switch (_message_level) {
   589     case MESSAGE_NO_OUTPUT:
   590       smcp.msg_lev = GLP_MSG_OFF;
   591       break;
   592     case MESSAGE_ERROR_MESSAGE:
   593       smcp.msg_lev = GLP_MSG_ERR;
   594       break;
   595     case MESSAGE_NORMAL_OUTPUT:
   596       smcp.msg_lev = GLP_MSG_ON;
   597       break;
   598     case MESSAGE_FULL_OUTPUT:
   599       smcp.msg_lev = GLP_MSG_ALL;
   600       break;
   601     }
   602     smcp.meth = GLP_DUAL;
   603 
   604     if (glp_simplex(lp, &smcp) != 0) return UNSOLVED;
   605     return SOLVED;
   606   }
   607 
   608   GlpkLp::Value GlpkLp::_getPrimal(int i) const {
   609     return glp_get_col_prim(lp, i);
   610   }
   611 
   612   GlpkLp::Value GlpkLp::_getDual(int i) const {
   613     return glp_get_row_dual(lp, i);
   614   }
   615 
   616   GlpkLp::Value GlpkLp::_getPrimalValue() const {
   617     return glp_get_obj_val(lp);
   618   }
   619 
   620   GlpkLp::VarStatus GlpkLp::_getColStatus(int i) const {
   621     switch (glp_get_col_stat(lp, i)) {
   622     case GLP_BS:
   623       return BASIC;
   624     case GLP_UP:
   625       return UPPER;
   626     case GLP_LO:
   627       return LOWER;
   628     case GLP_NF:
   629       return FREE;
   630     case GLP_NS:
   631       return FIXED;
   632     default:
   633       LEMON_ASSERT(false, "Wrong column status");
   634       return GlpkLp::VarStatus();
   635     }
   636   }
   637 
   638   GlpkLp::VarStatus GlpkLp::_getRowStatus(int i) const {
   639     switch (glp_get_row_stat(lp, i)) {
   640     case GLP_BS:
   641       return BASIC;
   642     case GLP_UP:
   643       return UPPER;
   644     case GLP_LO:
   645       return LOWER;
   646     case GLP_NF:
   647       return FREE;
   648     case GLP_NS:
   649       return FIXED;
   650     default:
   651       LEMON_ASSERT(false, "Wrong row status");
   652       return GlpkLp::VarStatus();
   653     }
   654   }
   655 
   656   GlpkLp::Value GlpkLp::_getPrimalRay(int i) const {
   657     if (_primal_ray.empty()) {
   658       int row_num = glp_get_num_rows(lp);
   659       int col_num = glp_get_num_cols(lp);
   660 
   661       _primal_ray.resize(col_num + 1, 0.0);
   662 
   663       int index = glp_get_unbnd_ray(lp);
   664       if (index != 0) {
   665         // The primal ray is found in primal simplex second phase
   666         LEMON_ASSERT((index <= row_num ? glp_get_row_stat(lp, index) :
   667                       glp_get_col_stat(lp, index - row_num)) != GLP_BS,
   668                      "Wrong primal ray");
   669 
   670         bool negate = glp_get_obj_dir(lp) == GLP_MAX;
   671 
   672         if (index > row_num) {
   673           _primal_ray[index - row_num] = 1.0;
   674           if (glp_get_col_dual(lp, index - row_num) > 0) {
   675             negate = !negate;
   676           }
   677         } else {
   678           if (glp_get_row_dual(lp, index) > 0) {
   679             negate = !negate;
   680           }
   681         }
   682 
   683         std::vector<int> ray_indexes(row_num + 1);
   684         std::vector<Value> ray_values(row_num + 1);
   685         int ray_length = glp_eval_tab_col(lp, index, &ray_indexes.front(),
   686                                           &ray_values.front());
   687 
   688         for (int i = 1; i <= ray_length; ++i) {
   689           if (ray_indexes[i] > row_num) {
   690             _primal_ray[ray_indexes[i] - row_num] = ray_values[i];
   691           }
   692         }
   693 
   694         if (negate) {
   695           for (int i = 1; i <= col_num; ++i) {
   696             _primal_ray[i] = - _primal_ray[i];
   697           }
   698         }
   699       } else {
   700         for (int i = 1; i <= col_num; ++i) {
   701           _primal_ray[i] = glp_get_col_prim(lp, i);
   702         }
   703       }
   704     }
   705     return _primal_ray[i];
   706   }
   707 
   708   GlpkLp::Value GlpkLp::_getDualRay(int i) const {
   709     if (_dual_ray.empty()) {
   710       int row_num = glp_get_num_rows(lp);
   711 
   712       _dual_ray.resize(row_num + 1, 0.0);
   713 
   714       int index = glp_get_unbnd_ray(lp);
   715       if (index != 0) {
   716         // The dual ray is found in dual simplex second phase
   717         LEMON_ASSERT((index <= row_num ? glp_get_row_stat(lp, index) :
   718                       glp_get_col_stat(lp, index - row_num)) == GLP_BS,
   719 
   720                      "Wrong dual ray");
   721 
   722         int idx;
   723         bool negate = false;
   724 
   725         if (index > row_num) {
   726           idx = glp_get_col_bind(lp, index - row_num);
   727           if (glp_get_col_prim(lp, index - row_num) >
   728               glp_get_col_ub(lp, index - row_num)) {
   729             negate = true;
   730           }
   731         } else {
   732           idx = glp_get_row_bind(lp, index);
   733           if (glp_get_row_prim(lp, index) > glp_get_row_ub(lp, index)) {
   734             negate = true;
   735           }
   736         }
   737 
   738         _dual_ray[idx] = negate ?  - 1.0 : 1.0;
   739 
   740         glp_btran(lp, &_dual_ray.front());
   741       } else {
   742         double eps = 1e-7;
   743         // The dual ray is found in primal simplex first phase
   744         // We assume that the glpk minimizes the slack to get feasible solution
   745         for (int i = 1; i <= row_num; ++i) {
   746           int index = glp_get_bhead(lp, i);
   747           if (index <= row_num) {
   748             double res = glp_get_row_prim(lp, index);
   749             if (res > glp_get_row_ub(lp, index) + eps) {
   750               _dual_ray[i] = -1;
   751             } else if (res < glp_get_row_lb(lp, index) - eps) {
   752               _dual_ray[i] = 1;
   753             } else {
   754               _dual_ray[i] = 0;
   755             }
   756             _dual_ray[i] *= glp_get_rii(lp, index);
   757           } else {
   758             double res = glp_get_col_prim(lp, index - row_num);
   759             if (res > glp_get_col_ub(lp, index - row_num) + eps) {
   760               _dual_ray[i] = -1;
   761             } else if (res < glp_get_col_lb(lp, index - row_num) - eps) {
   762               _dual_ray[i] = 1;
   763             } else {
   764               _dual_ray[i] = 0;
   765             }
   766             _dual_ray[i] /= glp_get_sjj(lp, index - row_num);
   767           }
   768         }
   769 
   770         glp_btran(lp, &_dual_ray.front());
   771 
   772         for (int i = 1; i <= row_num; ++i) {
   773           _dual_ray[i] /= glp_get_rii(lp, i);
   774         }
   775       }
   776     }
   777     return _dual_ray[i];
   778   }
   779 
   780   GlpkLp::ProblemType GlpkLp::_getPrimalType() const {
   781     if (glp_get_status(lp) == GLP_OPT)
   782       return OPTIMAL;
   783     switch (glp_get_prim_stat(lp)) {
   784     case GLP_UNDEF:
   785       return UNDEFINED;
   786     case GLP_FEAS:
   787     case GLP_INFEAS:
   788       if (glp_get_dual_stat(lp) == GLP_NOFEAS) {
   789         return UNBOUNDED;
   790       } else {
   791         return UNDEFINED;
   792       }
   793     case GLP_NOFEAS:
   794       return INFEASIBLE;
   795     default:
   796       LEMON_ASSERT(false, "Wrong primal type");
   797       return  GlpkLp::ProblemType();
   798     }
   799   }
   800 
   801   GlpkLp::ProblemType GlpkLp::_getDualType() const {
   802     if (glp_get_status(lp) == GLP_OPT)
   803       return OPTIMAL;
   804     switch (glp_get_dual_stat(lp)) {
   805     case GLP_UNDEF:
   806       return UNDEFINED;
   807     case GLP_FEAS:
   808     case GLP_INFEAS:
   809       if (glp_get_prim_stat(lp) == GLP_NOFEAS) {
   810         return UNBOUNDED;
   811       } else {
   812         return UNDEFINED;
   813       }
   814     case GLP_NOFEAS:
   815       return INFEASIBLE;
   816     default:
   817       LEMON_ASSERT(false, "Wrong primal type");
   818       return  GlpkLp::ProblemType();
   819     }
   820   }
   821 
   822   void GlpkLp::presolver(bool b) {
   823     lpx_set_int_parm(lp, LPX_K_PRESOL, b ? 1 : 0);
   824   }
   825 
   826   void GlpkLp::messageLevel(MessageLevel m) {
   827     _message_level = m;
   828   }
   829 
   830   // GlpkMip members
   831 
   832   GlpkMip::GlpkMip()
   833     : LpBase(), MipSolver(), GlpkBase() {
   834     messageLevel(MESSAGE_NO_OUTPUT);
   835   }
   836 
   837   GlpkMip::GlpkMip(const GlpkMip& other)
   838     : LpBase(), MipSolver(), GlpkBase(other) {
   839     messageLevel(MESSAGE_NO_OUTPUT);
   840   }
   841 
   842   void GlpkMip::_setColType(int i, GlpkMip::ColTypes col_type) {
   843     switch (col_type) {
   844     case INTEGER:
   845       glp_set_col_kind(lp, i, GLP_IV);
   846       break;
   847     case REAL:
   848       glp_set_col_kind(lp, i, GLP_CV);
   849       break;
   850     }
   851   }
   852 
   853   GlpkMip::ColTypes GlpkMip::_getColType(int i) const {
   854     switch (glp_get_col_kind(lp, i)) {
   855     case GLP_IV:
   856     case GLP_BV:
   857       return INTEGER;
   858     default:
   859       return REAL;
   860     }
   861 
   862   }
   863 
   864   GlpkMip::SolveExitStatus GlpkMip::_solve() {
   865     glp_smcp smcp;
   866     glp_init_smcp(&smcp);
   867 
   868     switch (_message_level) {
   869     case MESSAGE_NO_OUTPUT:
   870       smcp.msg_lev = GLP_MSG_OFF;
   871       break;
   872     case MESSAGE_ERROR_MESSAGE:
   873       smcp.msg_lev = GLP_MSG_ERR;
   874       break;
   875     case MESSAGE_NORMAL_OUTPUT:
   876       smcp.msg_lev = GLP_MSG_ON;
   877       break;
   878     case MESSAGE_FULL_OUTPUT:
   879       smcp.msg_lev = GLP_MSG_ALL;
   880       break;
   881     }
   882     smcp.meth = GLP_DUAL;
   883 
   884     if (glp_simplex(lp, &smcp) != 0) return UNSOLVED;
   885     if (glp_get_status(lp) != GLP_OPT) return SOLVED;
   886 
   887     glp_iocp iocp;
   888     glp_init_iocp(&iocp);
   889 
   890     switch (_message_level) {
   891     case MESSAGE_NO_OUTPUT:
   892       iocp.msg_lev = GLP_MSG_OFF;
   893       break;
   894     case MESSAGE_ERROR_MESSAGE:
   895       iocp.msg_lev = GLP_MSG_ERR;
   896       break;
   897     case MESSAGE_NORMAL_OUTPUT:
   898       iocp.msg_lev = GLP_MSG_ON;
   899       break;
   900     case MESSAGE_FULL_OUTPUT:
   901       iocp.msg_lev = GLP_MSG_ALL;
   902       break;
   903     }
   904 
   905     if (glp_intopt(lp, &iocp) != 0) return UNSOLVED;
   906     return SOLVED;
   907   }
   908 
   909 
   910   GlpkMip::ProblemType GlpkMip::_getType() const {
   911     switch (glp_get_status(lp)) {
   912     case GLP_OPT:
   913       switch (glp_mip_status(lp)) {
   914       case GLP_UNDEF:
   915         return UNDEFINED;
   916       case GLP_NOFEAS:
   917         return INFEASIBLE;
   918       case GLP_FEAS:
   919         return FEASIBLE;
   920       case GLP_OPT:
   921         return OPTIMAL;
   922       default:
   923         LEMON_ASSERT(false, "Wrong problem type.");
   924         return GlpkMip::ProblemType();
   925       }
   926     case GLP_NOFEAS:
   927       return INFEASIBLE;
   928     case GLP_INFEAS:
   929     case GLP_FEAS:
   930       if (glp_get_dual_stat(lp) == GLP_NOFEAS) {
   931         return UNBOUNDED;
   932       } else {
   933         return UNDEFINED;
   934       }
   935     default:
   936       LEMON_ASSERT(false, "Wrong problem type.");
   937       return GlpkMip::ProblemType();
   938     }
   939   }
   940 
   941   GlpkMip::Value GlpkMip::_getSol(int i) const {
   942     return glp_mip_col_val(lp, i);
   943   }
   944 
   945   GlpkMip::Value GlpkMip::_getSolValue() const {
   946     return glp_mip_obj_val(lp);
   947   }
   948 
   949   GlpkMip* GlpkMip::newSolver() const { return new GlpkMip; }
   950   GlpkMip* GlpkMip::cloneSolver() const {return new GlpkMip(*this); }
   951 
   952   const char* GlpkMip::_solverName() const { return "GlpkMip"; }
   953 
   954   void GlpkMip::messageLevel(MessageLevel m) {
   955     _message_level = m;
   956   }
   957 
   958 } //END OF NAMESPACE LEMON