deba@458: /* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@458:  *
deba@458:  * This file is a part of LEMON, a generic C++ optimization library.
deba@458:  *
deba@458:  * Copyright (C) 2003-2008
deba@458:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@458:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@458:  *
deba@458:  * Permission to use, modify and distribute this software is granted
deba@458:  * provided that this copyright notice appears in all copies. For
deba@458:  * precise terms see the accompanying LICENSE file.
deba@458:  *
deba@458:  * This software is provided "AS IS" with no warranty of any kind,
deba@458:  * express or implied, and with no claim as to its suitability for any
deba@458:  * purpose.
deba@458:  *
deba@458:  */
deba@458: 
deba@458: ///\file
deba@459: ///\brief Implementation of the LEMON GLPK LP and MIP solver interface.
deba@458: 
deba@458: #include <lemon/lp_glpk.h>
deba@459: #include <glpk.h>
deba@458: 
deba@459: #include <lemon/assert.h>
deba@458: 
deba@458: namespace lemon {
deba@458: 
deba@459:   // GlpkBase members
deba@459: 
deba@459:   GlpkBase::GlpkBase() : LpBase() {
deba@459:     lp = glp_create_prob();
deba@459:     glp_create_index(lp);
deba@458:   }
deba@458: 
deba@459:   GlpkBase::GlpkBase(const GlpkBase &other) : LpBase() {
deba@459:     lp = glp_create_prob();
deba@459:     glp_copy_prob(lp, other.lp, GLP_ON);
deba@459:     glp_create_index(lp);
deba@459:     rows = other.rows;
deba@459:     cols = other.cols;
deba@458:   }
deba@458: 
deba@459:   GlpkBase::~GlpkBase() {
deba@459:     glp_delete_prob(lp);
deba@458:   }
deba@458: 
deba@459:   int GlpkBase::_addCol() {
deba@459:     int i = glp_add_cols(lp, 1);
deba@459:     glp_set_col_bnds(lp, i, GLP_FR, 0.0, 0.0);
deba@458:     return i;
deba@458:   }
deba@458: 
deba@459:   int GlpkBase::_addRow() {
deba@459:     int i = glp_add_rows(lp, 1);
deba@459:     glp_set_row_bnds(lp, i, GLP_FR, 0.0, 0.0);
deba@458:     return i;
deba@458:   }
deba@458: 
deba@459:   void GlpkBase::_eraseCol(int i) {
deba@458:     int ca[2];
deba@459:     ca[1] = i;
deba@459:     glp_del_cols(lp, 1, ca);
deba@458:   }
deba@458: 
deba@459:   void GlpkBase::_eraseRow(int i) {
deba@458:     int ra[2];
deba@459:     ra[1] = i;
deba@459:     glp_del_rows(lp, 1, ra);
deba@458:   }
deba@458: 
deba@459:   void GlpkBase::_eraseColId(int i) {
deba@459:     cols.eraseIndex(i);
deba@459:     cols.shiftIndices(i);
deba@458:   }
deba@458: 
deba@459:   void GlpkBase::_eraseRowId(int i) {
deba@459:     rows.eraseIndex(i);
deba@459:     rows.shiftIndices(i);
deba@459:   }
deba@458: 
deba@459:   void GlpkBase::_getColName(int c, std::string& name) const {
deba@459:     const char *str = glp_get_col_name(lp, c);
deba@459:     if (str) name = str;
deba@459:     else name.clear();
deba@459:   }
deba@459: 
deba@459:   void GlpkBase::_setColName(int c, const std::string & name) {
deba@459:     glp_set_col_name(lp, c, const_cast<char*>(name.c_str()));
deba@458: 
deba@458:   }
deba@458: 
deba@459:   int GlpkBase::_colByName(const std::string& name) const {
deba@459:     int k = glp_find_col(lp, const_cast<char*>(name.c_str()));
deba@458:     return k > 0 ? k : -1;
deba@458:   }
deba@458: 
deba@459:   void GlpkBase::_getRowName(int r, std::string& name) const {
deba@459:     const char *str = glp_get_row_name(lp, r);
deba@459:     if (str) name = str;
deba@459:     else name.clear();
deba@459:   }
deba@458: 
deba@459:   void GlpkBase::_setRowName(int r, const std::string & name) {
deba@459:     glp_set_row_name(lp, r, const_cast<char*>(name.c_str()));
deba@459: 
deba@459:   }
deba@459: 
deba@459:   int GlpkBase::_rowByName(const std::string& name) const {
deba@459:     int k = glp_find_row(lp, const_cast<char*>(name.c_str()));
deba@459:     return k > 0 ? k : -1;
deba@459:   }
deba@459: 
deba@459:   void GlpkBase::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
deba@459:     std::vector<int> indexes;
deba@458:     std::vector<Value> values;
deba@458: 
deba@459:     indexes.push_back(0);
deba@458:     values.push_back(0);
deba@458: 
deba@459:     for(ExprIterator it = b; it != e; ++it) {
deba@459:       indexes.push_back(it->first);
deba@458:       values.push_back(it->second);
deba@458:     }
deba@458: 
deba@459:     glp_set_mat_row(lp, i, values.size() - 1,
deba@459:                     &indexes.front(), &values.front());
deba@458:   }
deba@458: 
deba@459:   void GlpkBase::_getRowCoeffs(int ix, InsertIterator b) const {
deba@459:     int length = glp_get_mat_row(lp, ix, 0, 0);
deba@458: 
deba@459:     std::vector<int> indexes(length + 1);
deba@458:     std::vector<Value> values(length + 1);
deba@458: 
deba@459:     glp_get_mat_row(lp, ix, &indexes.front(), &values.front());
deba@458: 
deba@458:     for (int i = 1; i <= length; ++i) {
deba@459:       *b = std::make_pair(indexes[i], values[i]);
deba@458:       ++b;
deba@458:     }
deba@458:   }
deba@458: 
deba@459:   void GlpkBase::_setColCoeffs(int ix, ExprIterator b,
deba@459:                                      ExprIterator e) {
deba@458: 
deba@459:     std::vector<int> indexes;
deba@458:     std::vector<Value> values;
deba@458: 
deba@459:     indexes.push_back(0);
deba@458:     values.push_back(0);
deba@458: 
deba@459:     for(ExprIterator it = b; it != e; ++it) {
deba@459:       indexes.push_back(it->first);
deba@458:       values.push_back(it->second);
deba@458:     }
deba@458: 
deba@459:     glp_set_mat_col(lp, ix, values.size() - 1,
deba@459:                     &indexes.front(), &values.front());
deba@458:   }
deba@458: 
deba@459:   void GlpkBase::_getColCoeffs(int ix, InsertIterator b) const {
deba@459:     int length = glp_get_mat_col(lp, ix, 0, 0);
deba@458: 
deba@459:     std::vector<int> indexes(length + 1);
deba@458:     std::vector<Value> values(length + 1);
deba@458: 
deba@459:     glp_get_mat_col(lp, ix, &indexes.front(), &values.front());
deba@458: 
deba@459:     for (int i = 1; i  <= length; ++i) {
deba@459:       *b = std::make_pair(indexes[i], values[i]);
deba@458:       ++b;
deba@458:     }
deba@458:   }
deba@458: 
deba@459:   void GlpkBase::_setCoeff(int ix, int jx, Value value) {
deba@458: 
deba@459:     if (glp_get_num_cols(lp) < glp_get_num_rows(lp)) {
deba@458: 
deba@459:       int length = glp_get_mat_row(lp, ix, 0, 0);
deba@458: 
deba@459:       std::vector<int> indexes(length + 2);
deba@458:       std::vector<Value> values(length + 2);
deba@458: 
deba@459:       glp_get_mat_row(lp, ix, &indexes.front(), &values.front());
deba@458: 
deba@458:       //The following code does not suppose that the elements of the
deba@459:       //array indexes are sorted
deba@459:       bool found = false;
deba@459:       for (int i = 1; i  <= length; ++i) {
deba@459:         if (indexes[i] == jx) {
deba@459:           found = true;
deba@459:           values[i] = value;
deba@458:           break;
deba@458:         }
deba@458:       }
deba@459:       if (!found) {
deba@458:         ++length;
deba@459:         indexes[length] = jx;
deba@459:         values[length] = value;
deba@458:       }
deba@458: 
deba@459:       glp_set_mat_row(lp, ix, length, &indexes.front(), &values.front());
deba@458: 
deba@458:     } else {
deba@458: 
deba@459:       int length = glp_get_mat_col(lp, jx, 0, 0);
deba@458: 
deba@459:       std::vector<int> indexes(length + 2);
deba@458:       std::vector<Value> values(length + 2);
deba@458: 
deba@459:       glp_get_mat_col(lp, jx, &indexes.front(), &values.front());
deba@458: 
deba@458:       //The following code does not suppose that the elements of the
deba@459:       //array indexes are sorted
deba@459:       bool found = false;
deba@458:       for (int i = 1; i <= length; ++i) {
deba@459:         if (indexes[i] == ix) {
deba@459:           found = true;
deba@459:           values[i] = value;
deba@458:           break;
deba@458:         }
deba@458:       }
deba@459:       if (!found) {
deba@458:         ++length;
deba@459:         indexes[length] = ix;
deba@459:         values[length] = value;
deba@458:       }
deba@458: 
deba@459:       glp_set_mat_col(lp, jx, length, &indexes.front(), &values.front());
deba@458:     }
deba@458: 
deba@458:   }
deba@458: 
deba@459:   GlpkBase::Value GlpkBase::_getCoeff(int ix, int jx) const {
deba@458: 
deba@459:     int length = glp_get_mat_row(lp, ix, 0, 0);
deba@458: 
deba@459:     std::vector<int> indexes(length + 1);
deba@458:     std::vector<Value> values(length + 1);
deba@458: 
deba@459:     glp_get_mat_row(lp, ix, &indexes.front(), &values.front());
deba@458: 
deba@459:     for (int i = 1; i  <= length; ++i) {
deba@459:       if (indexes[i] == jx) {
deba@458:         return values[i];
deba@458:       }
deba@458:     }
deba@459: 
deba@458:     return 0;
deba@459:   }
deba@459: 
deba@459:   void GlpkBase::_setColLowerBound(int i, Value lo) {
deba@459:     LEMON_ASSERT(lo != INF, "Invalid bound");
deba@459: 
deba@459:     int b = glp_get_col_type(lp, i);
deba@459:     double up = glp_get_col_ub(lp, i);
deba@459:     if (lo == -INF) {
deba@459:       switch (b) {
deba@459:       case GLP_FR:
deba@459:       case GLP_LO:
deba@459:         glp_set_col_bnds(lp, i, GLP_FR, lo, up);
deba@459:         break;
deba@459:       case GLP_UP:
deba@459:         break;
deba@459:       case GLP_DB:
deba@459:       case GLP_FX:
deba@459:         glp_set_col_bnds(lp, i, GLP_UP, lo, up);
deba@459:         break;
deba@459:       default:
deba@459:         break;
deba@459:       }
deba@459:     } else {
deba@459:       switch (b) {
deba@459:       case GLP_FR:
deba@459:       case GLP_LO:
deba@459:         glp_set_col_bnds(lp, i, GLP_LO, lo, up);
deba@459:         break;
deba@459:       case GLP_UP:
deba@459:       case GLP_DB:
deba@459:       case GLP_FX:
deba@459:         if (lo == up)
deba@459:           glp_set_col_bnds(lp, i, GLP_FX, lo, up);
deba@459:         else
deba@459:           glp_set_col_bnds(lp, i, GLP_DB, lo, up);
deba@459:         break;
deba@459:       default:
deba@459:         break;
deba@459:       }
deba@459:     }
deba@459:   }
deba@459: 
deba@459:   GlpkBase::Value GlpkBase::_getColLowerBound(int i) const {
deba@459:     int b = glp_get_col_type(lp, i);
deba@459:     switch (b) {
deba@459:     case GLP_LO:
deba@459:     case GLP_DB:
deba@459:     case GLP_FX:
deba@459:       return glp_get_col_lb(lp, i);
deba@459:     default:
deba@459:       return -INF;
deba@459:     }
deba@459:   }
deba@459: 
deba@459:   void GlpkBase::_setColUpperBound(int i, Value up) {
deba@459:     LEMON_ASSERT(up != -INF, "Invalid bound");
deba@459: 
deba@459:     int b = glp_get_col_type(lp, i);
deba@459:     double lo = glp_get_col_lb(lp, i);
deba@459:     if (up == INF) {
deba@459:       switch (b) {
deba@459:       case GLP_FR:
deba@459:       case GLP_LO:
deba@459:         break;
deba@459:       case GLP_UP:
deba@459:         glp_set_col_bnds(lp, i, GLP_FR, lo, up);
deba@459:         break;
deba@459:       case GLP_DB:
deba@459:       case GLP_FX:
deba@459:         glp_set_col_bnds(lp, i, GLP_LO, lo, up);
deba@459:         break;
deba@459:       default:
deba@459:         break;
deba@459:       }
deba@459:     } else {
deba@459:       switch (b) {
deba@459:       case GLP_FR:
deba@459:         glp_set_col_bnds(lp, i, GLP_UP, lo, up);
deba@459:         break;
deba@459:       case GLP_UP:
deba@459:         glp_set_col_bnds(lp, i, GLP_UP, lo, up);
deba@459:         break;
deba@459:       case GLP_LO:
deba@459:       case GLP_DB:
deba@459:       case GLP_FX:
deba@459:         if (lo == up)
deba@459:           glp_set_col_bnds(lp, i, GLP_FX, lo, up);
deba@459:         else
deba@459:           glp_set_col_bnds(lp, i, GLP_DB, lo, up);
deba@459:         break;
deba@459:       default:
deba@459:         break;
deba@459:       }
deba@459:     }
deba@458: 
deba@458:   }
deba@458: 
deba@459:   GlpkBase::Value GlpkBase::_getColUpperBound(int i) const {
deba@459:     int b = glp_get_col_type(lp, i);
deba@458:       switch (b) {
deba@459:       case GLP_UP:
deba@459:       case GLP_DB:
deba@459:       case GLP_FX:
deba@459:         return glp_get_col_ub(lp, i);
deba@459:       default:
deba@458:         return INF;
deba@458:       }
deba@458:   }
deba@458: 
deba@459:   void GlpkBase::_setRowLowerBound(int i, Value lo) {
deba@459:     LEMON_ASSERT(lo != INF, "Invalid bound");
deba@458: 
deba@459:     int b = glp_get_row_type(lp, i);
deba@459:     double up = glp_get_row_ub(lp, i);
deba@459:     if (lo == -INF) {
deba@459:       switch (b) {
deba@459:       case GLP_FR:
deba@459:       case GLP_LO:
deba@459:         glp_set_row_bnds(lp, i, GLP_FR, lo, up);
deba@459:         break;
deba@459:       case GLP_UP:
deba@459:         break;
deba@459:       case GLP_DB:
deba@459:       case GLP_FX:
deba@459:         glp_set_row_bnds(lp, i, GLP_UP, lo, up);
deba@459:         break;
deba@459:       default:
deba@459:         break;
deba@458:       }
deba@459:     } else {
deba@459:       switch (b) {
deba@459:       case GLP_FR:
deba@459:       case GLP_LO:
deba@459:         glp_set_row_bnds(lp, i, GLP_LO, lo, up);
deba@459:         break;
deba@459:       case GLP_UP:
deba@459:       case GLP_DB:
deba@459:       case GLP_FX:
deba@459:         if (lo == up)
deba@459:           glp_set_row_bnds(lp, i, GLP_FX, lo, up);
deba@459:         else
deba@459:           glp_set_row_bnds(lp, i, GLP_DB, lo, up);
deba@459:         break;
deba@459:       default:
deba@459:         break;
deba@458:       }
deba@458:     }
deba@458: 
deba@458:   }
deba@458: 
deba@459:   GlpkBase::Value GlpkBase::_getRowLowerBound(int i) const {
deba@459:     int b = glp_get_row_type(lp, i);
deba@459:     switch (b) {
deba@459:     case GLP_LO:
deba@459:     case GLP_DB:
deba@459:     case GLP_FX:
deba@459:       return glp_get_row_lb(lp, i);
deba@458:     default:
deba@459:       return -INF;
deba@458:     }
deba@458:   }
deba@458: 
deba@459:   void GlpkBase::_setRowUpperBound(int i, Value up) {
deba@459:     LEMON_ASSERT(up != -INF, "Invalid bound");
deba@458: 
deba@459:     int b = glp_get_row_type(lp, i);
deba@459:     double lo = glp_get_row_lb(lp, i);
deba@459:     if (up == INF) {
deba@459:       switch (b) {
deba@459:       case GLP_FR:
deba@459:       case GLP_LO:
deba@459:         break;
deba@459:       case GLP_UP:
deba@459:         glp_set_row_bnds(lp, i, GLP_FR, lo, up);
deba@459:         break;
deba@459:       case GLP_DB:
deba@459:       case GLP_FX:
deba@459:         glp_set_row_bnds(lp, i, GLP_LO, lo, up);
deba@459:         break;
deba@459:       default:
deba@459:         break;
deba@459:       }
deba@459:     } else {
deba@459:       switch (b) {
deba@459:       case GLP_FR:
deba@459:         glp_set_row_bnds(lp, i, GLP_UP, lo, up);
deba@459:         break;
deba@459:       case GLP_UP:
deba@459:         glp_set_row_bnds(lp, i, GLP_UP, lo, up);
deba@459:         break;
deba@459:       case GLP_LO:
deba@459:       case GLP_DB:
deba@459:       case GLP_FX:
deba@459:         if (lo == up)
deba@459:           glp_set_row_bnds(lp, i, GLP_FX, lo, up);
deba@459:         else
deba@459:           glp_set_row_bnds(lp, i, GLP_DB, lo, up);
deba@459:         break;
deba@459:       default:
deba@459:         break;
deba@459:       }
deba@458:     }
deba@458:   }
deba@458: 
deba@459:   GlpkBase::Value GlpkBase::_getRowUpperBound(int i) const {
deba@459:     int b = glp_get_row_type(lp, i);
deba@459:     switch (b) {
deba@459:     case GLP_UP:
deba@459:     case GLP_DB:
deba@459:     case GLP_FX:
deba@459:       return glp_get_row_ub(lp, i);
deba@458:     default:
deba@459:       return INF;
deba@458:     }
deba@458:   }
deba@458: 
deba@459:   void GlpkBase::_setObjCoeffs(ExprIterator b, ExprIterator e) {
deba@459:     for (int i = 1; i <= glp_get_num_cols(lp); ++i) {
deba@459:       glp_set_obj_coef(lp, i, 0.0);
deba@459:     }
deba@459:     for (ExprIterator it = b; it != e; ++it) {
deba@459:       glp_set_obj_coef(lp, it->first, it->second);
deba@459:     }
deba@458:   }
deba@458: 
deba@459:   void GlpkBase::_getObjCoeffs(InsertIterator b) const {
deba@459:     for (int i = 1; i <= glp_get_num_cols(lp); ++i) {
deba@459:       Value val = glp_get_obj_coef(lp, i);
deba@459:       if (val != 0.0) {
deba@459:         *b = std::make_pair(i, val);
deba@459:         ++b;
deba@459:       }
deba@459:     }
deba@458:   }
deba@458: 
deba@459:   void GlpkBase::_setObjCoeff(int i, Value obj_coef) {
deba@459:     //i = 0 means the constant term (shift)
deba@459:     glp_set_obj_coef(lp, i, obj_coef);
deba@458:   }
deba@458: 
deba@459:   GlpkBase::Value GlpkBase::_getObjCoeff(int i) const {
deba@459:     //i = 0 means the constant term (shift)
deba@459:     return glp_get_obj_coef(lp, i);
deba@458:   }
deba@458: 
deba@459:   void GlpkBase::_setSense(GlpkBase::Sense sense) {
deba@459:     switch (sense) {
deba@459:     case MIN:
deba@459:       glp_set_obj_dir(lp, GLP_MIN);
deba@459:       break;
deba@459:     case MAX:
deba@459:       glp_set_obj_dir(lp, GLP_MAX);
deba@459:       break;
deba@459:     }
deba@458:   }
deba@458: 
deba@459:   GlpkBase::Sense GlpkBase::_getSense() const {
deba@459:     switch(glp_get_obj_dir(lp)) {
deba@459:     case GLP_MIN:
deba@459:       return MIN;
deba@459:     case GLP_MAX:
deba@459:       return MAX;
deba@459:     default:
deba@459:       LEMON_ASSERT(false, "Wrong sense");
deba@459:       return GlpkBase::Sense();
deba@459:     }
deba@458:   }
deba@458: 
deba@459:   void GlpkBase::_clear() {
deba@459:     glp_erase_prob(lp);
deba@459:     rows.clear();
deba@459:     cols.clear();
deba@459:   }
deba@459: 
deba@459:   // LpGlpk members
deba@459: 
deba@459:   LpGlpk::LpGlpk()
deba@459:     : LpBase(), GlpkBase(), LpSolver() {
deba@459:     messageLevel(MESSAGE_NO_OUTPUT);
deba@459:   }
deba@459: 
deba@459:   LpGlpk::LpGlpk(const LpGlpk& other)
deba@459:     : LpBase(other), GlpkBase(other), LpSolver(other) {
deba@459:     messageLevel(MESSAGE_NO_OUTPUT);
deba@459:   }
deba@459: 
deba@459:   LpGlpk* LpGlpk::_newSolver() const { return new LpGlpk; }
deba@459:   LpGlpk* LpGlpk::_cloneSolver() const { return new LpGlpk(*this); }
deba@459: 
deba@459:   const char* LpGlpk::_solverName() const { return "LpGlpk"; }
deba@459: 
deba@459:   void LpGlpk::_clear_temporals() {
deba@459:     _primal_ray.clear();
deba@459:     _dual_ray.clear();
deba@459:   }
deba@459: 
deba@459:   LpGlpk::SolveExitStatus LpGlpk::_solve() {
deba@459:     return solvePrimal();
deba@459:   }
deba@459: 
deba@459:   LpGlpk::SolveExitStatus LpGlpk::solvePrimal() {
deba@459:     _clear_temporals();
deba@459: 
deba@459:     glp_smcp smcp;
deba@459:     glp_init_smcp(&smcp);
deba@459: 
deba@459:     switch (_message_level) {
deba@459:     case MESSAGE_NO_OUTPUT:
deba@459:       smcp.msg_lev = GLP_MSG_OFF;
deba@459:       break;
deba@459:     case MESSAGE_ERROR_MESSAGE:
deba@459:       smcp.msg_lev = GLP_MSG_ERR;
deba@459:       break;
deba@459:     case MESSAGE_NORMAL_OUTPUT:
deba@459:       smcp.msg_lev = GLP_MSG_ON;
deba@459:       break;
deba@459:     case MESSAGE_FULL_OUTPUT:
deba@459:       smcp.msg_lev = GLP_MSG_ALL;
deba@459:       break;
deba@459:     }
deba@459: 
deba@459:     if (glp_simplex(lp, &smcp) != 0) return UNSOLVED;
deba@459:     return SOLVED;
deba@459:   }
deba@459: 
deba@459:   LpGlpk::SolveExitStatus LpGlpk::solveDual() {
deba@459:     _clear_temporals();
deba@459: 
deba@459:     glp_smcp smcp;
deba@459:     glp_init_smcp(&smcp);
deba@459: 
deba@459:     switch (_message_level) {
deba@459:     case MESSAGE_NO_OUTPUT:
deba@459:       smcp.msg_lev = GLP_MSG_OFF;
deba@459:       break;
deba@459:     case MESSAGE_ERROR_MESSAGE:
deba@459:       smcp.msg_lev = GLP_MSG_ERR;
deba@459:       break;
deba@459:     case MESSAGE_NORMAL_OUTPUT:
deba@459:       smcp.msg_lev = GLP_MSG_ON;
deba@459:       break;
deba@459:     case MESSAGE_FULL_OUTPUT:
deba@459:       smcp.msg_lev = GLP_MSG_ALL;
deba@459:       break;
deba@459:     }
deba@459:     smcp.meth = GLP_DUAL;
deba@459: 
deba@459:     if (glp_simplex(lp, &smcp) != 0) return UNSOLVED;
deba@459:     return SOLVED;
deba@459:   }
deba@459: 
deba@459:   LpGlpk::Value LpGlpk::_getPrimal(int i) const {
deba@459:     return glp_get_col_prim(lp, i);
deba@459:   }
deba@459: 
deba@459:   LpGlpk::Value LpGlpk::_getDual(int i) const {
deba@459:     return glp_get_row_dual(lp, i);
deba@459:   }
deba@459: 
deba@459:   LpGlpk::Value LpGlpk::_getPrimalValue() const {
deba@459:     return glp_get_obj_val(lp);
deba@459:   }
deba@459: 
deba@459:   LpGlpk::VarStatus LpGlpk::_getColStatus(int i) const {
deba@459:     switch (glp_get_col_stat(lp, i)) {
deba@459:     case GLP_BS:
deba@459:       return BASIC;
deba@459:     case GLP_UP:
deba@459:       return UPPER;
deba@459:     case GLP_LO:
deba@459:       return LOWER;
deba@459:     case GLP_NF:
deba@459:       return FREE;
deba@459:     case GLP_NS:
deba@459:       return FIXED;
deba@459:     default:
deba@459:       LEMON_ASSERT(false, "Wrong column status");
deba@459:       return LpGlpk::VarStatus();
deba@459:     }
deba@459:   }
deba@459: 
deba@459:   LpGlpk::VarStatus LpGlpk::_getRowStatus(int i) const {
deba@459:     switch (glp_get_row_stat(lp, i)) {
deba@459:     case GLP_BS:
deba@459:       return BASIC;
deba@459:     case GLP_UP:
deba@459:       return UPPER;
deba@459:     case GLP_LO:
deba@459:       return LOWER;
deba@459:     case GLP_NF:
deba@459:       return FREE;
deba@459:     case GLP_NS:
deba@459:       return FIXED;
deba@459:     default:
deba@459:       LEMON_ASSERT(false, "Wrong row status");
deba@459:       return LpGlpk::VarStatus();
deba@459:     }
deba@459:   }
deba@459: 
deba@459:   LpGlpk::Value LpGlpk::_getPrimalRay(int i) const {
deba@459:     if (_primal_ray.empty()) {
deba@459:       int row_num = glp_get_num_rows(lp);
deba@459:       int col_num = glp_get_num_cols(lp);
deba@459: 
deba@459:       _primal_ray.resize(col_num + 1, 0.0);
deba@459: 
deba@459:       int index = glp_get_unbnd_ray(lp);
deba@459:       if (index != 0) {
deba@459:         // The primal ray is found in primal simplex second phase
deba@459:         LEMON_ASSERT((index <= row_num ? glp_get_row_stat(lp, index) :
deba@459:                       glp_get_col_stat(lp, index - row_num)) != GLP_BS,
deba@459:                      "Wrong primal ray");
deba@459: 
deba@459:         bool negate = glp_get_obj_dir(lp) == GLP_MAX;
deba@459: 
deba@459:         if (index > row_num) {
deba@459:           _primal_ray[index - row_num] = 1.0;
deba@459:           if (glp_get_col_dual(lp, index - row_num) > 0) {
deba@459:             negate = !negate;
deba@459:           }
deba@459:         } else {
deba@459:           if (glp_get_row_dual(lp, index) > 0) {
deba@459:             negate = !negate;
deba@459:           }
deba@459:         }
deba@459: 
deba@459:         std::vector<int> ray_indexes(row_num + 1);
deba@459:         std::vector<Value> ray_values(row_num + 1);
deba@459:         int ray_length = glp_eval_tab_col(lp, index, &ray_indexes.front(),
deba@459:                                           &ray_values.front());
deba@459: 
deba@459:         for (int i = 1; i <= ray_length; ++i) {
deba@459:           if (ray_indexes[i] > row_num) {
deba@459:             _primal_ray[ray_indexes[i] - row_num] = ray_values[i];
deba@459:           }
deba@459:         }
deba@459: 
deba@459:         if (negate) {
deba@459:           for (int i = 1; i <= col_num; ++i) {
deba@459:             _primal_ray[i] = - _primal_ray[i];
deba@459:           }
deba@459:         }
deba@459:       } else {
deba@459:         for (int i = 1; i <= col_num; ++i) {
deba@459:           _primal_ray[i] = glp_get_col_prim(lp, i);
deba@459:         }
deba@459:       }
deba@459:     }
deba@459:     return _primal_ray[i];
deba@459:   }
deba@459: 
deba@459:   LpGlpk::Value LpGlpk::_getDualRay(int i) const {
deba@459:     if (_dual_ray.empty()) {
deba@459:       int row_num = glp_get_num_rows(lp);
deba@459: 
deba@459:       _dual_ray.resize(row_num + 1, 0.0);
deba@459: 
deba@459:       int index = glp_get_unbnd_ray(lp);
deba@459:       if (index != 0) {
deba@459:         // The dual ray is found in dual simplex second phase
deba@459:         LEMON_ASSERT((index <= row_num ? glp_get_row_stat(lp, index) :
deba@459:                       glp_get_col_stat(lp, index - row_num)) == GLP_BS,
deba@459: 
deba@459:                      "Wrong dual ray");
deba@459: 
deba@459:         int idx;
deba@459:         bool negate = false;
deba@459: 
deba@459:         if (index > row_num) {
deba@459:           idx = glp_get_col_bind(lp, index - row_num);
deba@459:           if (glp_get_col_prim(lp, index - row_num) >
deba@459:               glp_get_col_ub(lp, index - row_num)) {
deba@459:             negate = true;
deba@459:           }
deba@459:         } else {
deba@459:           idx = glp_get_row_bind(lp, index);
deba@459:           if (glp_get_row_prim(lp, index) > glp_get_row_ub(lp, index)) {
deba@459:             negate = true;
deba@459:           }
deba@459:         }
deba@459: 
deba@459:         _dual_ray[idx] = negate ?  - 1.0 : 1.0;
deba@459: 
deba@459:         glp_btran(lp, &_dual_ray.front());
deba@459:       } else {
deba@459:         double eps = 1e-7;
deba@459:         // The dual ray is found in primal simplex first phase
deba@459:         // We assume that the glpk minimizes the slack to get feasible solution
deba@459:         for (int i = 1; i <= row_num; ++i) {
deba@459:           int index = glp_get_bhead(lp, i);
deba@459:           if (index <= row_num) {
deba@459:             double res = glp_get_row_prim(lp, index);
deba@459:             if (res > glp_get_row_ub(lp, index) + eps) {
deba@459:               _dual_ray[i] = -1;
deba@459:             } else if (res < glp_get_row_lb(lp, index) - eps) {
deba@459:               _dual_ray[i] = 1;
deba@459:             } else {
deba@459:               _dual_ray[i] = 0;
deba@459:             }
deba@459:             _dual_ray[i] *= glp_get_rii(lp, index);
deba@459:           } else {
deba@459:             double res = glp_get_col_prim(lp, index - row_num);
deba@459:             if (res > glp_get_col_ub(lp, index - row_num) + eps) {
deba@459:               _dual_ray[i] = -1;
deba@459:             } else if (res < glp_get_col_lb(lp, index - row_num) - eps) {
deba@459:               _dual_ray[i] = 1;
deba@459:             } else {
deba@459:               _dual_ray[i] = 0;
deba@459:             }
deba@459:             _dual_ray[i] /= glp_get_sjj(lp, index - row_num);
deba@459:           }
deba@459:         }
deba@459: 
deba@459:         glp_btran(lp, &_dual_ray.front());
deba@459: 
deba@459:         for (int i = 1; i <= row_num; ++i) {
deba@459:           _dual_ray[i] /= glp_get_rii(lp, i);
deba@459:         }
deba@459:       }
deba@459:     }
deba@459:     return _dual_ray[i];
deba@459:   }
deba@459: 
deba@459:   LpGlpk::ProblemType LpGlpk::_getPrimalType() const {
deba@459:     if (glp_get_status(lp) == GLP_OPT)
deba@459:       return OPTIMAL;
deba@459:     switch (glp_get_prim_stat(lp)) {
deba@459:     case GLP_UNDEF:
deba@459:       return UNDEFINED;
deba@459:     case GLP_FEAS:
deba@459:     case GLP_INFEAS:
deba@459:       if (glp_get_dual_stat(lp) == GLP_NOFEAS) {
deba@459:         return UNBOUNDED;
deba@459:       } else {
deba@459:         return UNDEFINED;
deba@459:       }
deba@459:     case GLP_NOFEAS:
deba@459:       return INFEASIBLE;
deba@459:     default:
deba@459:       LEMON_ASSERT(false, "Wrong primal type");
deba@459:       return  LpGlpk::ProblemType();
deba@459:     }
deba@459:   }
deba@459: 
deba@459:   LpGlpk::ProblemType LpGlpk::_getDualType() const {
deba@459:     if (glp_get_status(lp) == GLP_OPT)
deba@459:       return OPTIMAL;
deba@459:     switch (glp_get_dual_stat(lp)) {
deba@459:     case GLP_UNDEF:
deba@459:       return UNDEFINED;
deba@459:     case GLP_FEAS:
deba@459:     case GLP_INFEAS:
deba@459:       if (glp_get_prim_stat(lp) == GLP_NOFEAS) {
deba@459:         return UNBOUNDED;
deba@459:       } else {
deba@459:         return UNDEFINED;
deba@459:       }
deba@459:     case GLP_NOFEAS:
deba@459:       return INFEASIBLE;
deba@459:     default:
deba@459:       LEMON_ASSERT(false, "Wrong primal type");
deba@459:       return  LpGlpk::ProblemType();
deba@459:     }
deba@459:   }
deba@459: 
deba@459:   void LpGlpk::presolver(bool b) {
deba@459:     lpx_set_int_parm(lp, LPX_K_PRESOL, b ? 1 : 0);
deba@459:   }
deba@459: 
deba@459:   void LpGlpk::messageLevel(MessageLevel m) {
deba@459:     _message_level = m;
deba@459:   }
deba@459: 
deba@459:   // MipGlpk members
deba@459: 
deba@459:   MipGlpk::MipGlpk()
deba@459:     : LpBase(), GlpkBase(), MipSolver() {
deba@459:     messageLevel(MESSAGE_NO_OUTPUT);
deba@459:   }
deba@459: 
deba@459:   MipGlpk::MipGlpk(const MipGlpk& other)
deba@459:     : LpBase(), GlpkBase(other), MipSolver() {
deba@459:     messageLevel(MESSAGE_NO_OUTPUT);
deba@459:   }
deba@459: 
deba@459:   void MipGlpk::_setColType(int i, MipGlpk::ColTypes col_type) {
deba@459:     switch (col_type) {
deba@459:     case INTEGER:
deba@459:       glp_set_col_kind(lp, i, GLP_IV);
deba@459:       break;
deba@459:     case REAL:
deba@459:       glp_set_col_kind(lp, i, GLP_CV);
deba@459:       break;
deba@459:     }
deba@459:   }
deba@459: 
deba@459:   MipGlpk::ColTypes MipGlpk::_getColType(int i) const {
deba@459:     switch (glp_get_col_kind(lp, i)) {
deba@459:     case GLP_IV:
deba@459:     case GLP_BV:
deba@459:       return INTEGER;
deba@459:     default:
deba@459:       return REAL;
deba@459:     }
deba@459: 
deba@459:   }
deba@459: 
deba@459:   MipGlpk::SolveExitStatus MipGlpk::_solve() {
deba@459:     glp_smcp smcp;
deba@459:     glp_init_smcp(&smcp);
deba@459: 
deba@459:     switch (_message_level) {
deba@459:     case MESSAGE_NO_OUTPUT:
deba@459:       smcp.msg_lev = GLP_MSG_OFF;
deba@459:       break;
deba@459:     case MESSAGE_ERROR_MESSAGE:
deba@459:       smcp.msg_lev = GLP_MSG_ERR;
deba@459:       break;
deba@459:     case MESSAGE_NORMAL_OUTPUT:
deba@459:       smcp.msg_lev = GLP_MSG_ON;
deba@459:       break;
deba@459:     case MESSAGE_FULL_OUTPUT:
deba@459:       smcp.msg_lev = GLP_MSG_ALL;
deba@459:       break;
deba@459:     }
deba@459:     smcp.meth = GLP_DUAL;
deba@459: 
deba@459:     if (glp_simplex(lp, &smcp) != 0) return UNSOLVED;
deba@459:     if (glp_get_status(lp) != GLP_OPT) return SOLVED;
deba@459: 
deba@459:     glp_iocp iocp;
deba@459:     glp_init_iocp(&iocp);
deba@459: 
deba@459:     switch (_message_level) {
deba@459:     case MESSAGE_NO_OUTPUT:
deba@459:       iocp.msg_lev = GLP_MSG_OFF;
deba@459:       break;
deba@459:     case MESSAGE_ERROR_MESSAGE:
deba@459:       iocp.msg_lev = GLP_MSG_ERR;
deba@459:       break;
deba@459:     case MESSAGE_NORMAL_OUTPUT:
deba@459:       iocp.msg_lev = GLP_MSG_ON;
deba@459:       break;
deba@459:     case MESSAGE_FULL_OUTPUT:
deba@459:       iocp.msg_lev = GLP_MSG_ALL;
deba@459:       break;
deba@459:     }
deba@459: 
deba@459:     if (glp_intopt(lp, &iocp) != 0) return UNSOLVED;
deba@459:     return SOLVED;
deba@459:   }
deba@459: 
deba@459: 
deba@459:   MipGlpk::ProblemType MipGlpk::_getType() const {
deba@459:     switch (glp_get_status(lp)) {
deba@459:     case GLP_OPT:
deba@459:       switch (glp_mip_status(lp)) {
deba@459:       case GLP_UNDEF:
deba@459:         return UNDEFINED;
deba@459:       case GLP_NOFEAS:
deba@459:         return INFEASIBLE;
deba@459:       case GLP_FEAS:
deba@459:         return FEASIBLE;
deba@459:       case GLP_OPT:
deba@459:         return OPTIMAL;
deba@459:       default:
deba@459:         LEMON_ASSERT(false, "Wrong problem type.");
deba@459:         return MipGlpk::ProblemType();
deba@459:       }
deba@459:     case GLP_NOFEAS:
deba@459:       return INFEASIBLE;
deba@459:     case GLP_INFEAS:
deba@459:     case GLP_FEAS:
deba@459:       if (glp_get_dual_stat(lp) == GLP_NOFEAS) {
deba@459:         return UNBOUNDED;
deba@459:       } else {
deba@459:         return UNDEFINED;
deba@459:       }
deba@459:     default:
deba@459:       LEMON_ASSERT(false, "Wrong problem type.");
deba@459:       return MipGlpk::ProblemType();
deba@459:     }
deba@459:   }
deba@459: 
deba@459:   MipGlpk::Value MipGlpk::_getSol(int i) const {
deba@459:     return glp_mip_col_val(lp, i);
deba@459:   }
deba@459: 
deba@459:   MipGlpk::Value MipGlpk::_getSolValue() const {
deba@459:     return glp_mip_obj_val(lp);
deba@459:   }
deba@459: 
deba@459:   MipGlpk* MipGlpk::_newSolver() const { return new MipGlpk; }
deba@459:   MipGlpk* MipGlpk::_cloneSolver() const {return new MipGlpk(*this); }
deba@459: 
deba@459:   const char* MipGlpk::_solverName() const { return "MipGlpk"; }
deba@459: 
deba@459:   void MipGlpk::messageLevel(MessageLevel m) {
deba@459:     _message_level = m;
deba@459:   }
deba@458: 
deba@458: } //END OF NAMESPACE LEMON