athos@1261: /* -*- C++ -*- ladanyi@1435: * lemon/lp_glpk.cc - Part of LEMON, a generic C++ optimization library athos@1261: * athos@1261: * Copyright (C) 2005 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: #ifndef LEMON_LP_GLPK_CC athos@1261: #define LEMON_LP_GLPK_CC 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@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: { athos@1436: LpGlpk* newlp=new LpGlpk(); athos@1436: return *newlp; athos@1436: } athos@1436: athos@1436: ///\e athos@1436: athos@1436: LpSolverBase &LpGlpk::_copyLp() athos@1436: { athos@1436: LpGlpk* newlp=new LpGlpk(); athos@1436: athos@1436: //Coefficient matrix, row bounds athos@1436: lpx_add_rows(newlp->lp, lpx_get_num_rows(lp)); athos@1436: lpx_add_cols(newlp->lp, lpx_get_num_cols(lp)); athos@1436: int len; athos@1436: int ind[1+lpx_get_num_cols(lp)]; athos@1436: Value val[1+lpx_get_num_cols(lp)]; athos@1436: for (int i=1;i<=lpx_get_num_rows(lp);++i){ athos@1436: len=lpx_get_mat_row(lp,i,ind,val); athos@1436: lpx_set_mat_row(newlp->lp, i,len,ind,val); athos@1436: lpx_set_row_bnds(newlp->lp,i,lpx_get_row_type(lp,i), athos@1436: lpx_get_row_lb(lp,i),lpx_get_row_ub(lp,i)); athos@1436: } athos@1436: athos@1436: //Objective function, coloumn bounds athos@1436: lpx_set_obj_dir(newlp->lp, lpx_get_obj_dir(lp)); athos@1436: //Objectif function's constant term treated separately athos@1436: lpx_set_obj_coef(newlp->lp,0,lpx_get_obj_coef(lp,0)); athos@1436: for (int i=1;i<=lpx_get_num_cols(lp);++i){ athos@1436: lpx_set_obj_coef(newlp->lp,i,lpx_get_obj_coef(lp,i)); athos@1436: lpx_set_col_bnds(newlp->lp,i,lpx_get_col_type(lp,i), athos@1436: lpx_get_col_lb(lp,i),lpx_get_col_ub(lp,i)); athos@1436: athos@1436: athos@1436: } athos@1436: 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@1321: void LpGlpk::_setRowCoeffs(int i, alpar@1321: int length, alpar@1321: const int * indices, alpar@1321: const Value * values ) alpar@1321: { alpar@1321: lpx_set_mat_row(lp, i, length, alpar@1321: const_cast(indices) , alpar@1321: const_cast(values)); alpar@1321: } alpar@1321: alpar@1321: void LpGlpk::_setColCoeffs(int i, alpar@1321: int length, alpar@1321: const int * indices, alpar@1321: const Value * values) alpar@1321: { alpar@1321: lpx_set_mat_col(lp, i, length, alpar@1321: const_cast(indices), alpar@1321: const_cast(values)); alpar@1321: } athos@1431: athos@1431: athos@1431: void LpGlpk::_setCoeff(int row, int col, Value value) athos@1431: { athos@1431: ///FIXME Of course this is not efficient at all, but GLPK knows not more. athos@1431: // First approach: get one row, apply changes and set it again athos@1431: //(one idea to improve this: maybe it is better to do this with 1 coloumn) athos@1431: athos@1431: int mem_length=2+lpx_get_num_cols(lp); athos@1431: int* indices = new int[mem_length]; athos@1431: Value* values = new Value[mem_length]; athos@1431: athos@1431: athos@1431: int length=lpx_get_mat_row(lp, row, indices, values); athos@1431: athos@1431: //The following code does not suppose that the elements of the array indices are sorted athos@1431: int i=1; athos@1431: bool found=false; athos@1431: while (i <= length && !found){ athos@1431: if (indices[i]==col){ athos@1431: found = true; athos@1431: values[i]=value; athos@1431: } athos@1431: ++i; athos@1431: } athos@1431: if (!found){ athos@1431: ++length; athos@1431: indices[length]=col; athos@1431: values[length]=value; athos@1431: } athos@1431: athos@1431: lpx_set_mat_row(lp, row, length, indices, values); athos@1431: delete [] indices; athos@1431: delete [] values; 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: "<