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