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