1.1 --- a/src/lemon/lp_glpk.cc Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,447 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/lemon/lp_glpk.cc - Part of LEMON, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 - *
1.10 - * Permission to use, modify and distribute this software is granted
1.11 - * provided that this copyright notice appears in all copies. For
1.12 - * precise terms see the accompanying LICENSE file.
1.13 - *
1.14 - * This software is provided "AS IS" with no warranty of any kind,
1.15 - * express or implied, and with no claim as to its suitability for any
1.16 - * purpose.
1.17 - *
1.18 - */
1.19 -
1.20 -#ifndef LEMON_LP_GLPK_CC
1.21 -#define LEMON_LP_GLPK_CC
1.22 -
1.23 -///\file
1.24 -///\brief Implementation of the LEMON-GLPK lp solver interface.
1.25 -
1.26 -#include <lemon/lp_glpk.h>
1.27 -
1.28 -namespace lemon {
1.29 -
1.30 - ///\e
1.31 -
1.32 - ///\bug Unimplemented!
1.33 - ///
1.34 - LpSolverBase &LpGlpk::_newLp()
1.35 - {
1.36 - LpSolverBase *tmp=0;
1.37 - return *tmp;
1.38 - }
1.39 -
1.40 - ///\e
1.41 -
1.42 - ///\bug Unimplemented!
1.43 - ///
1.44 - LpSolverBase &LpGlpk::_copyLp()
1.45 - {
1.46 - LpSolverBase *tmp=0;
1.47 - return *tmp;
1.48 - }
1.49 -
1.50 - LpGlpk::LpGlpk() : Parent(),
1.51 - lp(lpx_create_prob()) {
1.52 - ///\todo constrol function for this:
1.53 - lpx_set_int_parm(lp, LPX_K_DUAL, 1);
1.54 - messageLevel(0);
1.55 - }
1.56 -
1.57 - LpGlpk::~LpGlpk() {
1.58 - lpx_delete_prob(lp);
1.59 - }
1.60 -
1.61 - int LpGlpk::_addCol() {
1.62 - int i=lpx_add_cols(lp, 1);
1.63 - _setColLowerBound(i, -INF);
1.64 - _setColUpperBound(i, INF);
1.65 - return i;
1.66 - }
1.67 -
1.68 - int LpGlpk::_addRow() {
1.69 - int i=lpx_add_rows(lp, 1);
1.70 - return i;
1.71 - }
1.72 -
1.73 -
1.74 - void LpGlpk::_eraseCol(int i) {
1.75 - int cols[2];
1.76 - cols[1]=i;
1.77 - lpx_del_cols(lp, 1, cols);
1.78 - }
1.79 -
1.80 - void LpGlpk::_eraseRow(int i) {
1.81 - int rows[2];
1.82 - rows[1]=i;
1.83 - lpx_del_rows(lp, 1, rows);
1.84 - }
1.85 -
1.86 - void LpGlpk::_setRowCoeffs(int i,
1.87 - int length,
1.88 - const int * indices,
1.89 - const Value * values )
1.90 - {
1.91 - lpx_set_mat_row(lp, i, length,
1.92 - const_cast<int * >(indices) ,
1.93 - const_cast<Value * >(values));
1.94 - }
1.95 -
1.96 - void LpGlpk::_setColCoeffs(int i,
1.97 - int length,
1.98 - const int * indices,
1.99 - const Value * values)
1.100 - {
1.101 - lpx_set_mat_col(lp, i, length,
1.102 - const_cast<int * >(indices),
1.103 - const_cast<Value * >(values));
1.104 - }
1.105 -
1.106 -
1.107 - void LpGlpk::_setCoeff(int row, int col, Value value)
1.108 - {
1.109 - ///FIXME Of course this is not efficient at all, but GLPK knows not more.
1.110 - // First approach: get one row, apply changes and set it again
1.111 - //(one idea to improve this: maybe it is better to do this with 1 coloumn)
1.112 -
1.113 - int mem_length=2+lpx_get_num_cols(lp);
1.114 - int* indices = new int[mem_length];
1.115 - Value* values = new Value[mem_length];
1.116 -
1.117 -
1.118 - int length=lpx_get_mat_row(lp, row, indices, values);
1.119 -
1.120 - //The following code does not suppose that the elements of the array indices are sorted
1.121 - int i=1;
1.122 - bool found=false;
1.123 - while (i <= length && !found){
1.124 - if (indices[i]==col){
1.125 - found = true;
1.126 - values[i]=value;
1.127 - }
1.128 - ++i;
1.129 - }
1.130 - if (!found){
1.131 - ++length;
1.132 - indices[length]=col;
1.133 - values[length]=value;
1.134 - }
1.135 -
1.136 - lpx_set_mat_row(lp, row, length, indices, values);
1.137 - delete [] indices;
1.138 - delete [] values;
1.139 -
1.140 - }
1.141 -
1.142 - void LpGlpk::_setColLowerBound(int i, Value lo)
1.143 - {
1.144 - if (lo==INF) {
1.145 - //FIXME error
1.146 - }
1.147 - int b=lpx_get_col_type(lp, i);
1.148 - double up=lpx_get_col_ub(lp, i);
1.149 - if (lo==-INF) {
1.150 - switch (b) {
1.151 - case LPX_FR:
1.152 - case LPX_LO:
1.153 - lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
1.154 - break;
1.155 - case LPX_UP:
1.156 - break;
1.157 - case LPX_DB:
1.158 - case LPX_FX:
1.159 - lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
1.160 - break;
1.161 - default: ;
1.162 - //FIXME error
1.163 - }
1.164 - } else {
1.165 - switch (b) {
1.166 - case LPX_FR:
1.167 - case LPX_LO:
1.168 - lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
1.169 - break;
1.170 - case LPX_UP:
1.171 - case LPX_DB:
1.172 - case LPX_FX:
1.173 - if (lo==up)
1.174 - lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
1.175 - else
1.176 - lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
1.177 - break;
1.178 - default: ;
1.179 - //FIXME error
1.180 - }
1.181 - }
1.182 -
1.183 - }
1.184 -
1.185 - void LpGlpk::_setColUpperBound(int i, Value up)
1.186 - {
1.187 - if (up==-INF) {
1.188 - //FIXME error
1.189 - }
1.190 - int b=lpx_get_col_type(lp, i);
1.191 - double lo=lpx_get_col_lb(lp, i);
1.192 - if (up==INF) {
1.193 - switch (b) {
1.194 - case LPX_FR:
1.195 - case LPX_LO:
1.196 - break;
1.197 - case LPX_UP:
1.198 - lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
1.199 - break;
1.200 - case LPX_DB:
1.201 - case LPX_FX:
1.202 - lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
1.203 - break;
1.204 - default: ;
1.205 - //FIXME error
1.206 - }
1.207 - } else {
1.208 - switch (b) {
1.209 - case LPX_FR:
1.210 - lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
1.211 - break;
1.212 - case LPX_UP:
1.213 - lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
1.214 - break;
1.215 - case LPX_LO:
1.216 - case LPX_DB:
1.217 - case LPX_FX:
1.218 - if (lo==up)
1.219 - lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
1.220 - else
1.221 - lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
1.222 - break;
1.223 - default: ;
1.224 - //FIXME error
1.225 - }
1.226 - }
1.227 - }
1.228 -
1.229 -// void LpGlpk::_setRowLowerBound(int i, Value lo)
1.230 -// {
1.231 -// if (lo==INF) {
1.232 -// //FIXME error
1.233 -// }
1.234 -// int b=lpx_get_row_type(lp, i);
1.235 -// double up=lpx_get_row_ub(lp, i);
1.236 -// if (lo==-INF) {
1.237 -// switch (b) {
1.238 -// case LPX_FR:
1.239 -// case LPX_LO:
1.240 -// lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
1.241 -// break;
1.242 -// case LPX_UP:
1.243 -// break;
1.244 -// case LPX_DB:
1.245 -// case LPX_FX:
1.246 -// lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
1.247 -// break;
1.248 -// default: ;
1.249 -// //FIXME error
1.250 -// }
1.251 -// } else {
1.252 -// switch (b) {
1.253 -// case LPX_FR:
1.254 -// case LPX_LO:
1.255 -// lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
1.256 -// break;
1.257 -// case LPX_UP:
1.258 -// case LPX_DB:
1.259 -// case LPX_FX:
1.260 -// if (lo==up)
1.261 -// lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
1.262 -// else
1.263 -// lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
1.264 -// break;
1.265 -// default: ;
1.266 -// //FIXME error
1.267 -// }
1.268 -// }
1.269 -// }
1.270 -
1.271 -// void LpGlpk::_setRowUpperBound(int i, Value up)
1.272 -// {
1.273 -// if (up==-INF) {
1.274 -// //FIXME error
1.275 -// }
1.276 -// int b=lpx_get_row_type(lp, i);
1.277 -// double lo=lpx_get_row_lb(lp, i);
1.278 -// if (up==INF) {
1.279 -// switch (b) {
1.280 -// case LPX_FR:
1.281 -// case LPX_LO:
1.282 -// break;
1.283 -// case LPX_UP:
1.284 -// lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
1.285 -// break;
1.286 -// case LPX_DB:
1.287 -// case LPX_FX:
1.288 -// lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
1.289 -// break;
1.290 -// default: ;
1.291 -// //FIXME error
1.292 -// }
1.293 -// } else {
1.294 -// switch (b) {
1.295 -// case LPX_FR:
1.296 -// lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
1.297 -// break;
1.298 -// case LPX_UP:
1.299 -// lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
1.300 -// break;
1.301 -// case LPX_LO:
1.302 -// case LPX_DB:
1.303 -// case LPX_FX:
1.304 -// if (lo==up)
1.305 -// lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
1.306 -// else
1.307 -// lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
1.308 -// break;
1.309 -// default: ;
1.310 -// //FIXME error
1.311 -// }
1.312 -// }
1.313 -// }
1.314 -
1.315 - void LpGlpk::_setRowBounds(int i, Value lb, Value ub)
1.316 - {
1.317 - //Bad parameter
1.318 - if (lb==INF || ub==-INF) {
1.319 - //FIXME error
1.320 - }
1.321 -
1.322 - if (lb == -INF){
1.323 - if (ub == INF){
1.324 - lpx_set_row_bnds(lp, i, LPX_FR, lb, ub);
1.325 - }
1.326 - else{
1.327 - lpx_set_row_bnds(lp, i, LPX_UP, lb, ub);
1.328 - }
1.329 - }
1.330 - else{
1.331 - if (ub==INF){
1.332 - lpx_set_row_bnds(lp, i, LPX_LO, lb, ub);
1.333 -
1.334 - }
1.335 - else{
1.336 - if (lb == ub){
1.337 - lpx_set_row_bnds(lp, i, LPX_FX, lb, ub);
1.338 - }
1.339 - else{
1.340 - lpx_set_row_bnds(lp, i, LPX_DB, lb, ub);
1.341 - }
1.342 - }
1.343 - }
1.344 -
1.345 - }
1.346 -
1.347 - void LpGlpk::_setObjCoeff(int i, Value obj_coef)
1.348 - {
1.349 - //i=0 means the constant term (shift)
1.350 - lpx_set_obj_coef(lp, i, obj_coef);
1.351 - }
1.352 -
1.353 - void LpGlpk::_clearObj()
1.354 - {
1.355 - for (int i=0;i<=lpx_get_num_cols(lp);++i){
1.356 - lpx_set_obj_coef(lp, i, 0);
1.357 - }
1.358 - }
1.359 -// void LpGlpk::_setObj(int length,
1.360 -// int const * indices,
1.361 -// Value const * values )
1.362 -// {
1.363 -// Value new_values[1+lpx_num_cols()];
1.364 -// for (i=0;i<=lpx_num_cols();++i){
1.365 -// new_values[i]=0;
1.366 -// }
1.367 -// for (i=1;i<=length;++i){
1.368 -// new_values[indices[i]]=values[i];
1.369 -// }
1.370 -
1.371 -// for (i=0;i<=lpx_num_cols();++i){
1.372 -// lpx_set_obj_coef(lp, i, new_values[i]);
1.373 -// }
1.374 -// }
1.375 -
1.376 - LpGlpk::SolveExitStatus LpGlpk::_solve()
1.377 - {
1.378 - int i= lpx_simplex(lp);
1.379 - switch (i) {
1.380 - case LPX_E_OK:
1.381 - return SOLVED;
1.382 - break;
1.383 - default:
1.384 - return UNSOLVED;
1.385 - }
1.386 - }
1.387 -
1.388 - LpGlpk::Value LpGlpk::_getPrimal(int i)
1.389 - {
1.390 - return lpx_get_col_prim(lp,i);
1.391 - }
1.392 -
1.393 - LpGlpk::Value LpGlpk::_getPrimalValue()
1.394 - {
1.395 - return lpx_get_obj_val(lp);
1.396 - }
1.397 -
1.398 -
1.399 - LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()
1.400 - {
1.401 - int stat= lpx_get_status(lp);
1.402 - switch (stat) {
1.403 - case LPX_UNDEF://Undefined (no solve has been run yet)
1.404 - return UNDEFINED;
1.405 - break;
1.406 - case LPX_NOFEAS://There is no feasible solution (primal, I guess)
1.407 - case LPX_INFEAS://Infeasible
1.408 - return INFEASIBLE;
1.409 - break;
1.410 - case LPX_UNBND://Unbounded
1.411 - return INFINITE;
1.412 - break;
1.413 - case LPX_FEAS://Feasible
1.414 - return FEASIBLE;
1.415 - break;
1.416 - case LPX_OPT://Feasible
1.417 - return OPTIMAL;
1.418 - break;
1.419 - default:
1.420 - return UNDEFINED; //to avoid gcc warning
1.421 - //FIXME error
1.422 - }
1.423 - }
1.424 -
1.425 -
1.426 - void LpGlpk::_setMax()
1.427 - {
1.428 - lpx_set_obj_dir(lp, LPX_MAX);
1.429 - }
1.430 -
1.431 - void LpGlpk::_setMin()
1.432 - {
1.433 - lpx_set_obj_dir(lp, LPX_MIN);
1.434 - }
1.435 -
1.436 -
1.437 - void LpGlpk::messageLevel(int m)
1.438 - {
1.439 - lpx_set_int_parm(lp, LPX_K_MSGLEV, m);
1.440 - }
1.441 -
1.442 - void LpGlpk::presolver(bool b)
1.443 - {
1.444 - lpx_set_int_parm(lp, LPX_K_PRESOL, b);
1.445 - }
1.446 -
1.447 -
1.448 -} //END OF NAMESPACE LEMON
1.449 -
1.450 -#endif //LEMON_LP_GLPK_CC