athos@1261: /* -*- C++ -*- athos@1261: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@1956: * Copyright (C) 2003-2006 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1359: * (Egervary Research Group on Combinatorial Optimization, EGRES). athos@1261: * athos@1261: * Permission to use, modify and distribute this software is granted athos@1261: * provided that this copyright notice appears in all copies. For athos@1261: * precise terms see the accompanying LICENSE file. athos@1261: * athos@1261: * This software is provided "AS IS" with no warranty of any kind, athos@1261: * express or implied, and with no claim as to its suitability for any athos@1261: * purpose. athos@1261: * athos@1261: */ athos@1261: athos@1261: ///\file athos@1261: ///\brief Implementation of the LEMON-GLPK lp solver interface. athos@1261: ladanyi@1305: #include athos@1473: //#include athos@1261: namespace lemon { athos@1261: alpar@1364: alpar@1321: LpGlpk::LpGlpk() : Parent(), alpar@1321: lp(lpx_create_prob()) { alpar@1321: ///\todo constrol function for this: alpar@1321: lpx_set_int_parm(lp, LPX_K_DUAL, 1); alpar@1321: messageLevel(0); alpar@1321: } alpar@1321: alpar@2321: LpGlpk::LpGlpk(const LpGlpk &glp) : Parent(glp), alpar@2321: lp(lpx_create_prob()) { alpar@2321: ///\todo constrol function for this: alpar@2321: lpx_set_int_parm(lp, LPX_K_DUAL, 1); alpar@2321: messageLevel(0); alpar@2321: //Coefficient matrix, row bounds alpar@2321: lpx_add_rows(lp, lpx_get_num_rows(glp.lp)); alpar@2321: lpx_add_cols(lp, lpx_get_num_cols(glp.lp)); alpar@2321: int len; alpar@2321: int ind[1+lpx_get_num_cols(glp.lp)]; alpar@2321: Value val[1+lpx_get_num_cols(glp.lp)]; alpar@2321: for (int i=1;i<=lpx_get_num_rows(glp.lp);++i) alpar@2321: { alpar@2321: len=lpx_get_mat_row(glp.lp,i,ind,val); alpar@2321: lpx_set_mat_row(lp, i,len,ind,val); alpar@2321: lpx_set_row_bnds(lp,i,lpx_get_row_type(glp.lp,i), alpar@2321: lpx_get_row_lb(glp.lp,i),lpx_get_row_ub(glp.lp,i)); alpar@2321: } alpar@2321: alpar@2321: //Objective function, coloumn bounds alpar@2321: lpx_set_obj_dir(lp, lpx_get_obj_dir(glp.lp)); alpar@2321: //Objectif function's constant term treated separately alpar@2321: lpx_set_obj_coef(lp,0,lpx_get_obj_coef(glp.lp,0)); alpar@2321: for (int i=1;i<=lpx_get_num_cols(glp.lp);++i) alpar@2321: { alpar@2321: lpx_set_obj_coef(lp,i,lpx_get_obj_coef(glp.lp,i)); alpar@2321: lpx_set_col_bnds(lp,i,lpx_get_col_type(glp.lp,i), alpar@2321: lpx_get_col_lb(glp.lp,i),lpx_get_col_ub(glp.lp,i)); alpar@2321: } alpar@2321: } alpar@2321: alpar@1321: LpGlpk::~LpGlpk() { alpar@1321: lpx_delete_prob(lp); alpar@1321: } alpar@1321: alpar@1321: int LpGlpk::_addCol() { alpar@1321: int i=lpx_add_cols(lp, 1); alpar@1321: _setColLowerBound(i, -INF); alpar@1321: _setColUpperBound(i, INF); alpar@1321: return i; alpar@1321: } alpar@1321: athos@1436: ///\e athos@1436: athos@1436: athos@1436: LpSolverBase &LpGlpk::_newLp() athos@1436: { alpar@2321: LpGlpk* newlp=new LpGlpk; athos@1436: return *newlp; athos@1436: } athos@1436: athos@1436: ///\e athos@1436: athos@1436: LpSolverBase &LpGlpk::_copyLp() athos@1436: { alpar@2321: LpGlpk* newlp=new LpGlpk(*this); athos@1436: return *newlp; athos@1436: } athos@1436: alpar@1321: int LpGlpk::_addRow() { alpar@1321: int i=lpx_add_rows(lp, 1); alpar@1321: return i; alpar@1321: } alpar@1321: alpar@1321: athos@1432: void LpGlpk::_eraseCol(int i) { athos@1432: int cols[2]; athos@1432: cols[1]=i; athos@1432: lpx_del_cols(lp, 1, cols); athos@1432: } athos@1432: athos@1432: void LpGlpk::_eraseRow(int i) { athos@1432: int rows[2]; athos@1432: rows[1]=i; athos@1432: lpx_del_rows(lp, 1, rows); athos@1432: } athos@1432: alpar@1895: void LpGlpk::_getColName(int col, std::string & name) alpar@1895: { alpar@1895: alpar@1895: char *n = lpx_get_col_name(lp,col); alpar@1895: name = n?n:""; alpar@1895: } alpar@1895: alpar@1895: alpar@1895: void LpGlpk::_setColName(int col, const std::string & name) alpar@1895: { alpar@1895: lpx_set_col_name(lp,col,const_cast(name.c_str())); alpar@1895: } alpar@1895: deba@2312: void LpGlpk::_setRowCoeffs(int i, LpRowIterator b, LpRowIterator e) alpar@1321: { deba@2312: std::vector indices; deba@2312: std::vector values; deba@2312: deba@2312: indices.push_back(0); deba@2312: values.push_back(0); deba@2312: deba@2312: for(LpRowIterator it=b; it!=e; ++it) { deba@2312: indices.push_back(it->first); deba@2312: values.push_back(it->second); deba@2312: } deba@2312: deba@2312: lpx_set_mat_row(lp, i, values.size() - 1, &indices[0], &values[0]); alpar@1321: } alpar@1321: deba@2312: void LpGlpk::_setColCoeffs(int i, LpColIterator b, LpColIterator e) { deba@2312: deba@2312: std::vector indices; deba@2312: std::vector values; deba@2312: deba@2312: indices.push_back(0); deba@2312: values.push_back(0); deba@2312: deba@2312: for(LpColIterator it=b; it!=e; ++it) { deba@2312: indices.push_back(it->first); deba@2312: values.push_back(it->second); deba@2312: } deba@2312: deba@2312: lpx_set_mat_col(lp, i, values.size() - 1, &indices[0], &values[0]); alpar@1321: } athos@1431: athos@1431: athos@1431: void LpGlpk::_setCoeff(int row, int col, Value value) athos@1431: { deba@2312: deba@2312: if (lpx_get_num_cols(lp) < lpx_get_num_rows(lp)) { deba@2312: deba@2312: int length=lpx_get_mat_row(lp, row, 0, 0); deba@2312: deba@2312: std::vector indices(length + 2); deba@2312: std::vector values(length + 2); deba@2312: deba@2312: lpx_get_mat_row(lp, row, &indices[0], &values[0]); deba@2312: deba@2312: //The following code does not suppose that the elements of the deba@2312: //array indices are sorted deba@2312: bool found=false; deba@2312: for (int i = 1; i <= length; ++i) { deba@2312: if (indices[i]==col){ deba@2312: found=true; deba@2312: values[i]=value; deba@2312: break; deba@2312: } deba@2312: } deba@2312: if (!found){ deba@2312: ++length; deba@2312: indices[length]=col; deba@2312: values[length]=value; deba@2312: } athos@1431: deba@2312: lpx_set_mat_row(lp, row, length, &indices[0], &values[0]); deba@2312: deba@2312: } else { deba@2312: deba@2312: int length=lpx_get_mat_col(lp, col, 0, 0); deba@2312: deba@2312: std::vector indices(length + 2); deba@2312: std::vector values(length + 2); deba@2312: deba@2312: lpx_get_mat_col(lp, col, &indices[0], &values[0]); deba@2312: deba@2312: //The following code does not suppose that the elements of the deba@2312: //array indices are sorted deba@2312: bool found=false; deba@2312: for (int i = 1; i <= length; ++i) { deba@2312: if (indices[i]==col){ deba@2312: found=true; deba@2312: values[i]=value; deba@2312: break; deba@2312: } deba@2312: } deba@2312: if (!found){ deba@2312: ++length; deba@2312: indices[length]=row; deba@2312: values[length]=value; deba@2312: } athos@1431: deba@2312: lpx_set_mat_col(lp, col, length, &indices[0], &values[0]); athos@1431: } athos@1431: } athos@1431: alpar@1321: void LpGlpk::_setColLowerBound(int i, Value lo) alpar@1321: { alpar@1321: if (lo==INF) { alpar@1321: //FIXME error alpar@1321: } alpar@1321: int b=lpx_get_col_type(lp, i); alpar@1321: double up=lpx_get_col_ub(lp, i); alpar@1321: if (lo==-INF) { alpar@1321: switch (b) { alpar@1321: case LPX_FR: alpar@1321: case LPX_LO: alpar@1321: lpx_set_col_bnds(lp, i, LPX_FR, lo, up); alpar@1321: break; alpar@1321: case LPX_UP: alpar@1321: break; alpar@1321: case LPX_DB: alpar@1321: case LPX_FX: alpar@1321: lpx_set_col_bnds(lp, i, LPX_UP, lo, up); alpar@1321: break; alpar@1321: default: ; alpar@1321: //FIXME error alpar@1321: } alpar@1321: } else { alpar@1321: switch (b) { alpar@1321: case LPX_FR: alpar@1321: case LPX_LO: alpar@1321: lpx_set_col_bnds(lp, i, LPX_LO, lo, up); alpar@1321: break; alpar@1321: case LPX_UP: alpar@1321: case LPX_DB: alpar@1321: case LPX_FX: alpar@1321: if (lo==up) alpar@1321: lpx_set_col_bnds(lp, i, LPX_FX, lo, up); alpar@1321: else alpar@1321: lpx_set_col_bnds(lp, i, LPX_DB, lo, up); alpar@1321: break; alpar@1321: default: ; alpar@1321: //FIXME error alpar@1321: } athos@1261: } athos@1261: alpar@1321: } alpar@1321: alpar@1321: void LpGlpk::_setColUpperBound(int i, Value up) alpar@1321: { alpar@1321: if (up==-INF) { alpar@1321: //FIXME error athos@1261: } alpar@1321: int b=lpx_get_col_type(lp, i); alpar@1321: double lo=lpx_get_col_lb(lp, i); alpar@1321: if (up==INF) { alpar@1321: switch (b) { alpar@1321: case LPX_FR: alpar@1321: case LPX_LO: alpar@1321: break; alpar@1321: case LPX_UP: alpar@1321: lpx_set_col_bnds(lp, i, LPX_FR, lo, up); alpar@1321: break; alpar@1321: case LPX_DB: alpar@1321: case LPX_FX: alpar@1321: lpx_set_col_bnds(lp, i, LPX_LO, lo, up); alpar@1321: break; alpar@1321: default: ; athos@1261: //FIXME error athos@1261: } alpar@1321: } else { alpar@1321: switch (b) { alpar@1321: case LPX_FR: alpar@1321: lpx_set_col_bnds(lp, i, LPX_UP, lo, up); alpar@1321: break; alpar@1321: case LPX_UP: alpar@1321: lpx_set_col_bnds(lp, i, LPX_UP, lo, up); alpar@1321: break; alpar@1321: case LPX_LO: alpar@1321: case LPX_DB: alpar@1321: case LPX_FX: alpar@1321: if (lo==up) alpar@1321: lpx_set_col_bnds(lp, i, LPX_FX, lo, up); alpar@1321: else alpar@1321: lpx_set_col_bnds(lp, i, LPX_DB, lo, up); alpar@1321: break; alpar@1321: default: ; athos@1261: //FIXME error athos@1261: } alpar@1321: } alpar@1321: } alpar@1321: athos@1405: // void LpGlpk::_setRowLowerBound(int i, Value lo) athos@1405: // { athos@1405: // if (lo==INF) { athos@1405: // //FIXME error athos@1405: // } athos@1405: // int b=lpx_get_row_type(lp, i); athos@1405: // double up=lpx_get_row_ub(lp, i); athos@1405: // if (lo==-INF) { athos@1405: // switch (b) { athos@1405: // case LPX_FR: athos@1405: // case LPX_LO: athos@1405: // lpx_set_row_bnds(lp, i, LPX_FR, lo, up); athos@1405: // break; athos@1405: // case LPX_UP: athos@1405: // break; athos@1405: // case LPX_DB: athos@1405: // case LPX_FX: athos@1405: // lpx_set_row_bnds(lp, i, LPX_UP, lo, up); athos@1405: // break; athos@1405: // default: ; athos@1405: // //FIXME error athos@1405: // } athos@1405: // } else { athos@1405: // switch (b) { athos@1405: // case LPX_FR: athos@1405: // case LPX_LO: athos@1405: // lpx_set_row_bnds(lp, i, LPX_LO, lo, up); athos@1405: // break; athos@1405: // case LPX_UP: athos@1405: // case LPX_DB: athos@1405: // case LPX_FX: athos@1405: // if (lo==up) athos@1405: // lpx_set_row_bnds(lp, i, LPX_FX, lo, up); athos@1405: // else athos@1405: // lpx_set_row_bnds(lp, i, LPX_DB, lo, up); athos@1405: // break; athos@1405: // default: ; athos@1405: // //FIXME error athos@1405: // } athos@1405: // } athos@1405: // } athos@1261: athos@1405: // void LpGlpk::_setRowUpperBound(int i, Value up) athos@1405: // { athos@1405: // if (up==-INF) { athos@1405: // //FIXME error athos@1405: // } athos@1405: // int b=lpx_get_row_type(lp, i); athos@1405: // double lo=lpx_get_row_lb(lp, i); athos@1405: // if (up==INF) { athos@1405: // switch (b) { athos@1405: // case LPX_FR: athos@1405: // case LPX_LO: athos@1405: // break; athos@1405: // case LPX_UP: athos@1405: // lpx_set_row_bnds(lp, i, LPX_FR, lo, up); athos@1405: // break; athos@1405: // case LPX_DB: athos@1405: // case LPX_FX: athos@1405: // lpx_set_row_bnds(lp, i, LPX_LO, lo, up); athos@1405: // break; athos@1405: // default: ; athos@1405: // //FIXME error athos@1405: // } athos@1405: // } else { athos@1405: // switch (b) { athos@1405: // case LPX_FR: athos@1405: // lpx_set_row_bnds(lp, i, LPX_UP, lo, up); athos@1405: // break; athos@1405: // case LPX_UP: athos@1405: // lpx_set_row_bnds(lp, i, LPX_UP, lo, up); athos@1405: // break; athos@1405: // case LPX_LO: athos@1405: // case LPX_DB: athos@1405: // case LPX_FX: athos@1405: // if (lo==up) athos@1405: // lpx_set_row_bnds(lp, i, LPX_FX, lo, up); athos@1405: // else athos@1405: // lpx_set_row_bnds(lp, i, LPX_DB, lo, up); athos@1405: // break; athos@1405: // default: ; athos@1405: // //FIXME error athos@1405: // } athos@1405: // } athos@1405: // } athos@1379: athos@1379: void LpGlpk::_setRowBounds(int i, Value lb, Value ub) athos@1379: { athos@1379: //Bad parameter athos@1379: if (lb==INF || ub==-INF) { athos@1379: //FIXME error athos@1379: } athos@1379: athos@1379: if (lb == -INF){ athos@1379: if (ub == INF){ athos@1379: lpx_set_row_bnds(lp, i, LPX_FR, lb, ub); athos@1379: } athos@1379: else{ athos@1379: lpx_set_row_bnds(lp, i, LPX_UP, lb, ub); athos@1379: } athos@1379: } athos@1379: else{ athos@1379: if (ub==INF){ athos@1379: lpx_set_row_bnds(lp, i, LPX_LO, lb, ub); athos@1379: athos@1379: } athos@1379: else{ athos@1379: if (lb == ub){ athos@1379: lpx_set_row_bnds(lp, i, LPX_FX, lb, ub); athos@1379: } athos@1379: else{ athos@1379: lpx_set_row_bnds(lp, i, LPX_DB, lb, ub); athos@1379: } athos@1379: } athos@1379: } athos@1379: athos@1379: } athos@1261: athos@1298: void LpGlpk::_setObjCoeff(int i, Value obj_coef) athos@1298: { athos@1376: //i=0 means the constant term (shift) athos@1298: lpx_set_obj_coef(lp, i, obj_coef); athos@1298: } athos@1261: athos@1377: void LpGlpk::_clearObj() athos@1376: { athos@1377: for (int i=0;i<=lpx_get_num_cols(lp);++i){ athos@1377: lpx_set_obj_coef(lp, i, 0); athos@1376: } athos@1376: } athos@1377: // void LpGlpk::_setObj(int length, athos@1377: // int const * indices, athos@1377: // Value const * values ) athos@1377: // { athos@1377: // Value new_values[1+lpx_num_cols()]; athos@1377: // for (i=0;i<=lpx_num_cols();++i){ athos@1377: // new_values[i]=0; athos@1377: // } athos@1377: // for (i=1;i<=length;++i){ athos@1377: // new_values[indices[i]]=values[i]; athos@1377: // } athos@1377: athos@1377: // for (i=0;i<=lpx_num_cols();++i){ athos@1377: // lpx_set_obj_coef(lp, i, new_values[i]); athos@1377: // } athos@1377: // } alpar@1263: alpar@1303: LpGlpk::SolveExitStatus LpGlpk::_solve() alpar@1263: { athos@1458: int i = lpx_simplex(lp); athos@1298: switch (i) { athos@1298: case LPX_E_OK: athos@1298: return SOLVED; athos@1298: default: athos@1298: return UNSOLVED; athos@1298: } alpar@1263: } alpar@1263: alpar@1293: LpGlpk::Value LpGlpk::_getPrimal(int i) alpar@1263: { athos@1298: return lpx_get_col_prim(lp,i); alpar@1263: } marci@1787: marci@1787: LpGlpk::Value LpGlpk::_getDual(int i) marci@1787: { marci@1787: return lpx_get_row_dual(lp,i); marci@1787: } alpar@1263: alpar@1312: LpGlpk::Value LpGlpk::_getPrimalValue() alpar@1312: { athos@1314: return lpx_get_obj_val(lp); alpar@1312: } marci@1840: bool LpGlpk::_isBasicCol(int i) { marci@1840: return (lpx_get_col_stat(lp, i)==LPX_BS); marci@1840: } alpar@1312: athos@1298: alpar@1312: LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus() alpar@1294: { athos@1298: int stat= lpx_get_status(lp); athos@1298: switch (stat) { athos@1298: case LPX_UNDEF://Undefined (no solve has been run yet) athos@1298: return UNDEFINED; athos@1458: case LPX_NOFEAS://There is no feasible solution (primal, I guess) athos@1458: case LPX_INFEAS://Infeasible athos@1458: return INFEASIBLE; athos@1458: case LPX_UNBND://Unbounded athos@1458: return INFINITE; athos@1458: case LPX_FEAS://Feasible athos@1458: return FEASIBLE; athos@1458: case LPX_OPT://Feasible athos@1458: return OPTIMAL; athos@1458: default: athos@1458: return UNDEFINED; //to avoid gcc warning athos@1458: //FIXME error athos@1458: } athos@1458: } athos@1458: athos@1458: LpGlpk::SolutionStatus LpGlpk::_getDualStatus() athos@1458: { athos@1473: // std::cout<<"Itt megy: "<