alpar@1381: /* -*- C++ -*- ladanyi@1435: * lemon/lp_cplex.cc - Part of LEMON, a generic C++ optimization library alpar@1381: * alpar@1875: * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1381: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@1381: * alpar@1381: * Permission to use, modify and distribute this software is granted alpar@1381: * provided that this copyright notice appears in all copies. For alpar@1381: * precise terms see the accompanying LICENSE file. alpar@1381: * alpar@1381: * This software is provided "AS IS" with no warranty of any kind, alpar@1381: * express or implied, and with no claim as to its suitability for any alpar@1381: * purpose. alpar@1381: * alpar@1381: */ athos@1405: #include athos@1405: #include alpar@1381: alpar@1381: ///\file alpar@1381: ///\brief Implementation of the LEMON-CPLEX lp solver interface. alpar@1381: namespace lemon { alpar@1381: alpar@1381: LpCplex::LpCplex() : LpSolverBase() { athos@1436: athos@1436: // env = CPXopenCPLEXdevelop(&status); athos@1436: env = CPXopenCPLEX(&status); alpar@1381: lp = CPXcreateprob(env, &status, "LP problem"); alpar@1381: } alpar@1381: alpar@1381: LpCplex::~LpCplex() { athos@1436: CPXfreeprob(env,&lp); athos@1436: CPXcloseCPLEX(&env); alpar@1381: } alpar@1381: athos@1405: LpSolverBase &LpCplex::_newLp() athos@1405: { athos@1436: //The first approach opens a new environment athos@1436: LpCplex* newlp=new LpCplex(); athos@1436: return *newlp; athos@1405: } athos@1436: athos@1405: LpSolverBase &LpCplex::_copyLp() { athos@1436: //The first approach opens a new environment athos@1436: LpCplex* newlp=new LpCplex(); athos@1436: //The routine CPXcloneprob can be used to create a new CPLEX problem athos@1436: //object and copy all the problem data from an existing problem athos@1436: //object to it. Solution and starting information is not copied. athos@1508: newlp->lp = CPXcloneprob(env, lp, &status); athos@1436: return *newlp; athos@1405: } alpar@1381: alpar@1381: int LpCplex::_addCol() alpar@1381: { athos@1508: int i = CPXgetnumcols(env, lp); alpar@1381: Value lb[1],ub[1]; alpar@1381: lb[0]=-INF;//-CPX_INFBOUND; alpar@1381: ub[0]=INF;//CPX_INFBOUND; athos@1508: status = CPXnewcols(env, lp, 1, NULL, lb, ub, NULL, NULL); alpar@1381: return i; alpar@1381: } athos@1436: alpar@1381: alpar@1381: int LpCplex::_addRow() alpar@1381: { alpar@1381: //We want a row that is not constrained alpar@1381: char sense[1]; alpar@1381: sense[0]='L';//<= constraint alpar@1381: Value rhs[1]; alpar@1381: rhs[0]=INF; athos@1508: int i = CPXgetnumrows(env, lp); athos@1508: status = CPXnewrows(env, lp, 1, rhs, sense, NULL, NULL); alpar@1381: return i; alpar@1381: } athos@1432: athos@1432: athos@1432: void LpCplex::_eraseCol(int i) { athos@1508: CPXdelcols(env, lp, i, i); athos@1432: } athos@1432: athos@1432: void LpCplex::_eraseRow(int i) { athos@1508: CPXdelrows(env, lp, i, i); athos@1432: } athos@1432: alpar@1381: alpar@1381: ///\warning Data at index 0 is ignored in the arrays. alpar@1381: void LpCplex::_setRowCoeffs(int i, alpar@1381: int length, alpar@1381: int const * indices, alpar@1381: Value const * values ) alpar@1381: { alpar@1381: int rowlist[length+1]; alpar@1381: int* p=rowlist; alpar@1381: for (int k=1;k<=length;++k){ alpar@1381: rowlist[k]=i; alpar@1381: } alpar@1381: status = CPXchgcoeflist(env, lp, alpar@1381: length, alpar@1381: p+1, alpar@1381: const_cast(indices+1), alpar@1381: const_cast(values+1)); alpar@1381: } alpar@1381: alpar@1381: void LpCplex::_setColCoeffs(int i, alpar@1381: int length, alpar@1381: int const * indices, alpar@1381: Value const * values) alpar@1381: { alpar@1381: int collist[length+1]; alpar@1381: int* p=collist; alpar@1381: for (int k=1;k<=length;++k){ alpar@1381: collist[k]=i; alpar@1381: } alpar@1381: status = CPXchgcoeflist(env, lp, alpar@1381: length, alpar@1381: const_cast(indices+1), alpar@1381: p+1, alpar@1381: const_cast(values+1)); alpar@1381: } alpar@1381: athos@1431: void LpCplex::_setCoeff(int row, int col, Value value) athos@1431: { athos@1508: CPXchgcoef(env, lp, row, col, value); athos@1431: } athos@1431: alpar@1381: void LpCplex::_setColLowerBound(int i, Value value) alpar@1381: { alpar@1381: int indices[1]; alpar@1381: indices[0]=i; alpar@1381: char lu[1]; alpar@1381: lu[0]='L'; alpar@1381: Value bd[1]; alpar@1381: bd[0]=value; athos@1508: status = CPXchgbds(env, lp, 1, indices, lu, bd); alpar@1381: alpar@1381: } alpar@1381: alpar@1381: void LpCplex::_setColUpperBound(int i, Value value) alpar@1381: { alpar@1381: int indices[1]; alpar@1381: indices[0]=i; alpar@1381: char lu[1]; alpar@1381: lu[0]='U'; alpar@1381: Value bd[1]; alpar@1381: bd[0]=value; athos@1508: status = CPXchgbds(env, lp, 1, indices, lu, bd); alpar@1381: } alpar@1381: alpar@1381: //This will be easier to implement alpar@1381: void LpCplex::_setRowBounds(int i, Value lb, Value ub) alpar@1381: { alpar@1381: //Bad parameter alpar@1381: if (lb==INF || ub==-INF) { alpar@1381: //FIXME error alpar@1381: } athos@1405: alpar@1381: int cnt=1; alpar@1381: int indices[1]; alpar@1381: indices[0]=i; alpar@1381: char sense[1]; alpar@1381: alpar@1381: if (lb==-INF){ alpar@1381: sense[0]='L'; athos@1508: CPXchgsense(env, lp, cnt, indices, sense); athos@1508: CPXchgcoef(env, lp, i, -1, ub); athos@1405: alpar@1381: } alpar@1381: else{ alpar@1381: if (ub==INF){ alpar@1381: sense[0]='G'; athos@1508: CPXchgsense(env, lp, cnt, indices, sense); athos@1508: CPXchgcoef(env, lp, i, -1, lb); alpar@1381: } alpar@1381: else{ alpar@1381: if (lb == ub){ alpar@1381: sense[0]='E'; athos@1508: CPXchgsense(env, lp, cnt, indices, sense); athos@1508: CPXchgcoef(env, lp, i, -1, lb); alpar@1381: } alpar@1381: else{ alpar@1381: sense[0]='R'; athos@1508: CPXchgsense(env, lp, cnt, indices, sense); athos@1508: CPXchgcoef(env, lp, i, -1, lb); athos@1508: CPXchgcoef(env, lp, i, -2, ub-lb); alpar@1381: } alpar@1381: } alpar@1381: } alpar@1381: } alpar@1381: athos@1405: // void LpCplex::_setRowLowerBound(int i, Value value) athos@1405: // { athos@1405: // //Not implemented, obsolete athos@1405: // } alpar@1381: athos@1405: // void LpCplex::_setRowUpperBound(int i, Value value) athos@1405: // { athos@1405: // //Not implemented, obsolete athos@1405: // // //TODO Ezt kell meg megirni athos@1405: // // //type of the problem athos@1405: // // char sense[1]; athos@1508: // // status = CPXgetsense(env, lp, sense, i, i); athos@1405: // // Value rhs[1]; athos@1508: // // status = CPXgetrhs(env, lp, rhs, i, i); alpar@1381: athos@1405: // // switch (sense[0]) { athos@1405: // // case 'L'://<= constraint athos@1405: // // break; athos@1405: // // case 'E'://= constraint athos@1405: // // break; athos@1405: // // case 'G'://>= constraint athos@1405: // // break; athos@1405: // // case 'R'://ranged constraint athos@1405: // // break; athos@1405: // // default: ; athos@1405: // // //FIXME error athos@1405: // // } alpar@1381: athos@1508: // // status = CPXchgcoef(env, lp, i, -2, value_rng); athos@1405: // } alpar@1381: alpar@1381: void LpCplex::_setObjCoeff(int i, Value obj_coef) alpar@1381: { athos@1508: CPXchgcoef(env, lp, -1, i, obj_coef); alpar@1381: } alpar@1381: alpar@1381: void LpCplex::_clearObj() alpar@1381: { athos@1508: for (int i=0;i< CPXgetnumcols(env, lp);++i){ athos@1508: CPXchgcoef(env, lp, -1, i, 0); alpar@1381: } alpar@1381: alpar@1381: } athos@1458: // The routine returns zero unless an error occurred during the athos@1458: // optimization. Examples of errors include exhausting available athos@1458: // memory (CPXERR_NO_MEMORY) or encountering invalid data in the athos@1458: // CPLEX problem object (CPXERR_NO_PROBLEM). Exceeding a athos@1458: // user-specified CPLEX limit, or proving the model infeasible or athos@1458: // unbounded, are not considered errors. Note that a zero return athos@1458: // value does not necessarily mean that a solution exists. Use query athos@1458: // routines CPXsolninfo, CPXgetstat, and CPXsolution to obtain athos@1458: // further information about the status of the optimization. alpar@1381: LpCplex::SolveExitStatus LpCplex::_solve() alpar@1381: { athos@1458: //CPX_PARAM_LPMETHOD athos@1508: status = CPXlpopt(env, lp); athos@1542: //status = CPXprimopt(env, lp); alpar@1381: if (status == 0){ athos@1458: //We want to exclude some cases athos@1508: switch (CPXgetstat(env, lp)){ athos@1458: case CPX_OBJ_LIM: athos@1458: case CPX_IT_LIM_FEAS: athos@1458: case CPX_IT_LIM_INFEAS: athos@1458: case CPX_TIME_LIM_FEAS: athos@1458: case CPX_TIME_LIM_INFEAS: athos@1458: return UNSOLVED; athos@1458: default: athos@1458: return SOLVED; athos@1458: } alpar@1381: } alpar@1381: else{ alpar@1381: return UNSOLVED; alpar@1381: } alpar@1381: } alpar@1381: athos@1460: LpCplex::Value LpCplex::_getPrimal(int i) athos@1460: { athos@1460: Value x; athos@1508: CPXgetx(env, lp, &x, i, i); athos@1460: return x; athos@1460: } marci@1787: marci@1787: LpCplex::Value LpCplex::_getDual(int i) marci@1787: { marci@1787: Value y; klao@1798: CPXgetpi(env, lp, &y, i, i); marci@1787: return y; marci@1787: } athos@1460: athos@1460: LpCplex::Value LpCplex::_getPrimalValue() athos@1460: { athos@1460: Value objval; athos@1460: //method = CPXgetmethod (env, lp); athos@1508: //printf("CPXgetprobtype %d \n",CPXgetprobtype(env,lp)); athos@1508: status = CPXgetobjval(env, lp, &objval); athos@1508: //printf("Objective value: %g \n",objval); athos@1460: return objval; athos@1460: } marci@1840: bool LpCplex::_isBasicCol(int i) { marci@1841: int cstat[CPXgetnumcols(env, lp)]; marci@1841: CPXgetbase(env, lp, cstat, NULL); marci@1841: return (cstat[i]==CPX_BASIC); marci@1840: } athos@1407: athos@1458: //7.5-os cplex statusai (Vigyazat: a 9.0-asei masok!) athos@1458: // This table lists the statuses, returned by the CPXgetstat() routine, for solutions to LP problems or mixed integer problems. If no solution exists, the return value is zero. athos@1458: athos@1458: // For Simplex, Barrier athos@1458: // 1 CPX_OPTIMAL athos@1458: // Optimal solution found athos@1458: // 2 CPX_INFEASIBLE athos@1458: // Problem infeasible athos@1458: // 3 CPX_UNBOUNDED athos@1458: // Problem unbounded athos@1458: // 4 CPX_OBJ_LIM athos@1458: // Objective limit exceeded in Phase II athos@1458: // 5 CPX_IT_LIM_FEAS athos@1458: // Iteration limit exceeded in Phase II athos@1458: // 6 CPX_IT_LIM_INFEAS athos@1458: // Iteration limit exceeded in Phase I athos@1458: // 7 CPX_TIME_LIM_FEAS athos@1458: // Time limit exceeded in Phase II athos@1458: // 8 CPX_TIME_LIM_INFEAS athos@1458: // Time limit exceeded in Phase I athos@1458: // 9 CPX_NUM_BEST_FEAS athos@1458: // Problem non-optimal, singularities in Phase II athos@1458: // 10 CPX_NUM_BEST_INFEAS athos@1458: // Problem non-optimal, singularities in Phase I athos@1458: // 11 CPX_OPTIMAL_INFEAS athos@1458: // Optimal solution found, unscaled infeasibilities athos@1458: // 12 CPX_ABORT_FEAS athos@1458: // Aborted in Phase II athos@1458: // 13 CPX_ABORT_INFEAS athos@1458: // Aborted in Phase I athos@1458: // 14 CPX_ABORT_DUAL_INFEAS athos@1458: // Aborted in barrier, dual infeasible athos@1458: // 15 CPX_ABORT_PRIM_INFEAS athos@1458: // Aborted in barrier, primal infeasible athos@1458: // 16 CPX_ABORT_PRIM_DUAL_INFEAS athos@1458: // Aborted in barrier, primal and dual infeasible athos@1458: // 17 CPX_ABORT_PRIM_DUAL_FEAS athos@1458: // Aborted in barrier, primal and dual feasible athos@1458: // 18 CPX_ABORT_CROSSOVER athos@1458: // Aborted in crossover athos@1458: // 19 CPX_INForUNBD athos@1458: // Infeasible or unbounded athos@1458: // 20 CPX_PIVOT athos@1458: // User pivot used athos@1458: // athos@1407: // Ezeket hova tegyem: athos@1407: // ??case CPX_ABORT_DUAL_INFEAS athos@1407: // ??case CPX_ABORT_CROSSOVER athos@1407: // ??case CPX_INForUNBD athos@1542: // ??case CPX_PIVOT athos@1542: athos@1542: //Some more interesting stuff: athos@1542: athos@1542: // CPX_PARAM_LPMETHOD 1062 int LPMETHOD athos@1542: // 0 Automatic athos@1542: // 1 Primal Simplex athos@1542: // 2 Dual Simplex athos@1542: // 3 Network Simplex athos@1542: // 4 Standard Barrier athos@1542: // Default: 0 athos@1542: // Description: Method for linear optimization. athos@1542: // Determines which algorithm is used when CPXlpopt() (or "optimize" in the Interactive Optimizer) is called. Currently the behavior of the "Automatic" setting is that CPLEX simply invokes the dual simplex method, but this capability may be expanded in the future so that CPLEX chooses the method based on problem characteristics athos@1542: //Hulye cplex athos@1542: void statusSwitch(CPXENVptr env,int& stat){ athos@1542: int lpmethod; athos@1542: CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod); athos@1542: if (lpmethod==2){ athos@1542: if (stat==CPX_UNBOUNDED){ athos@1542: stat=CPX_INFEASIBLE; athos@1542: } athos@1542: else{ athos@1542: if (stat==CPX_INFEASIBLE) athos@1542: stat=CPX_UNBOUNDED; athos@1542: } athos@1542: } athos@1542: } athos@1407: athos@1458: LpCplex::SolutionStatus LpCplex::_getPrimalStatus() athos@1458: { athos@1542: athos@1508: int stat = CPXgetstat(env, lp); athos@1542: statusSwitch(env,stat); athos@1542: //CPXgetstat(env, lp); athos@1508: //printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL); athos@1407: switch (stat) { athos@1407: case 0: athos@1407: return UNDEFINED; //Undefined athos@1407: case CPX_OPTIMAL://Optimal athos@1407: return OPTIMAL; athos@1407: case CPX_UNBOUNDED://Unbounded athos@1542: return INFEASIBLE;//In case of dual simplex athos@1542: //return INFINITE; athos@1407: case CPX_INFEASIBLE://Infeasible athos@1458: // case CPX_IT_LIM_INFEAS: athos@1458: // case CPX_TIME_LIM_INFEAS: athos@1458: // case CPX_NUM_BEST_INFEAS: athos@1458: // case CPX_OPTIMAL_INFEAS: athos@1458: // case CPX_ABORT_INFEAS: athos@1458: // case CPX_ABORT_PRIM_INFEAS: athos@1458: // case CPX_ABORT_PRIM_DUAL_INFEAS: athos@1542: return INFINITE;//In case of dual simplex athos@1542: //return INFEASIBLE; athos@1458: // case CPX_OBJ_LIM: athos@1458: // case CPX_IT_LIM_FEAS: athos@1458: // case CPX_TIME_LIM_FEAS: athos@1458: // case CPX_NUM_BEST_FEAS: athos@1458: // case CPX_ABORT_FEAS: athos@1458: // case CPX_ABORT_PRIM_DUAL_FEAS: athos@1458: // return FEASIBLE; athos@1407: default: athos@1407: return UNDEFINED; //Everything else comes here athos@1407: //FIXME error athos@1407: } athos@1407: athos@1458: } athos@1407: athos@1458: //9.0-as cplex verzio statusai athos@1405: // CPX_STAT_ABORT_DUAL_OBJ_LIM athos@1405: // CPX_STAT_ABORT_IT_LIM athos@1405: // CPX_STAT_ABORT_OBJ_LIM athos@1405: // CPX_STAT_ABORT_PRIM_OBJ_LIM athos@1405: // CPX_STAT_ABORT_TIME_LIM athos@1405: // CPX_STAT_ABORT_USER athos@1405: // CPX_STAT_FEASIBLE_RELAXED athos@1405: // CPX_STAT_INFEASIBLE athos@1405: // CPX_STAT_INForUNBD athos@1405: // CPX_STAT_NUM_BEST athos@1405: // CPX_STAT_OPTIMAL athos@1405: // CPX_STAT_OPTIMAL_FACE_UNBOUNDED athos@1405: // CPX_STAT_OPTIMAL_INFEAS athos@1405: // CPX_STAT_OPTIMAL_RELAXED athos@1405: // CPX_STAT_UNBOUNDED athos@1405: athos@1458: LpCplex::SolutionStatus LpCplex::_getDualStatus() athos@1458: { athos@1508: int stat = CPXgetstat(env, lp); athos@1542: statusSwitch(env,stat); athos@1458: switch (stat) { athos@1458: case 0: athos@1458: return UNDEFINED; //Undefined athos@1458: case CPX_OPTIMAL://Optimal athos@1458: return OPTIMAL; athos@1458: case CPX_UNBOUNDED: athos@1458: return INFEASIBLE; athos@1458: default: athos@1458: return UNDEFINED; //Everything else comes here athos@1458: //FIXME error athos@1458: } athos@1473: } alpar@1381: athos@1460: LpCplex::ProblemTypes LpCplex::_getProblemType() alpar@1381: { athos@1508: int stat = CPXgetstat(env, lp); athos@1460: switch (stat) { athos@1460: case CPX_OPTIMAL://Optimal athos@1460: return PRIMAL_DUAL_FEASIBLE; athos@1460: case CPX_UNBOUNDED: athos@1460: return PRIMAL_FEASIBLE_DUAL_INFEASIBLE; athos@1460: // return PRIMAL_INFEASIBLE_DUAL_FEASIBLE; athos@1460: // return PRIMAL_DUAL_INFEASIBLE; athos@1460: athos@1460: //Seems to be that this is all we can say for sure athos@1460: default: athos@1460: //In all other cases athos@1460: return UNKNOWN; athos@1460: //FIXME error athos@1460: } athos@1473: } alpar@1381: alpar@1381: void LpCplex::_setMax() alpar@1381: { athos@1508: CPXchgobjsen(env, lp, CPX_MAX); alpar@1381: } alpar@1381: void LpCplex::_setMin() alpar@1381: { athos@1508: CPXchgobjsen(env, lp, CPX_MIN); alpar@1381: } alpar@1381: alpar@1381: } //namespace lemon alpar@1381: