lemon-0.x: lemon/lp_cplex.cc@723b2b81d900

     1 /* -*- C++ -*-

     2  * lemon/lp_cplex.cc - Part of LEMON, a generic C++ optimization library

     3  *

     4  * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     6  *

     7  * Permission to use, modify and distribute this software is granted

     8  * provided that this copyright notice appears in all copies. For

     9  * precise terms see the accompanying LICENSE file.

    10  *

    11  * This software is provided "AS IS" with no warranty of any kind,

    12  * express or implied, and with no claim as to its suitability for any

    13  * purpose.

    14  *

    15  */

    16 #include <iostream>

    17 #include<lemon/lp_cplex.h>

    19 ///\file

    20 ///\brief Implementation of the LEMON-CPLEX lp solver interface.

    21 namespace lemon {

    23   LpCplex::LpCplex() : LpSolverBase() {

    25     //    env = CPXopenCPLEXdevelop(&status);

    26     env = CPXopenCPLEX(&status);

    27     lp = CPXcreateprob(env, &status, "LP problem");

    28   }

    30   LpCplex::~LpCplex() {

    31     CPXfreeprob(env,&lp);

    32     CPXcloseCPLEX(&env);

    33   }

    35   LpSolverBase &LpCplex::_newLp()

    36   {

    37     //The first approach opens a new environment

    38     LpCplex* newlp=new LpCplex();

    39     return *newlp;

    40   }

    42   LpSolverBase &LpCplex::_copyLp() {

    43     //The first approach opens a new environment

    44     LpCplex* newlp=new LpCplex();

    45     //The routine CPXcloneprob can be used to create a new CPLEX problem

    46     //object and copy all the problem data from an existing problem

    47     //object to it. Solution and starting information is not copied.

    48     newlp->lp = CPXcloneprob(env, lp, &status);

    49     return *newlp;

    50   }

    52   int LpCplex::_addCol()

    53   {

    54     int i = CPXgetnumcols(env, lp);

    55     Value lb[1],ub[1];

    56     lb[0]=-INF;//-CPX_INFBOUND;

    57     ub[0]=INF;//CPX_INFBOUND;

    58     status = CPXnewcols(env, lp, 1, NULL, lb, ub, NULL, NULL);

    59     return i;

    60   }

    63   int LpCplex::_addRow()

    64   {

    65     //We want a row that is not constrained

    66     char sense[1];

    67     sense[0]='L';//<= constraint

    68     Value rhs[1];

    69     rhs[0]=INF;

    70     int i = CPXgetnumrows(env, lp);

    71     status = CPXnewrows(env, lp, 1, rhs, sense, NULL, NULL);

    72     return i;

    73   }

    76   void LpCplex::_eraseCol(int i) {

    77     CPXdelcols(env, lp, i, i);

    78   }

    80   void LpCplex::_eraseRow(int i) {

    81     CPXdelrows(env, lp, i, i);

    82   }

    84   void LpCplex::_getColName(int col, std::string &name)

    85   {

    86     ///\bug Unimplemented

    87   }

    89   void LpCplex::_setColName(int col, const std::string &name)

    90   {

    91     ///\bug Untested

    92     CPXchgcolname(env, lp, 1, &col, const_cast<char*>(name.c_str()));

    93   }

    95   ///\warning Data at index 0 is ignored in the arrays.

    96   void LpCplex::_setRowCoeffs(int i,

    97 			      int length,

    98 			      int  const * indices,

    99 			      Value  const * values )

   100   {

   101     int rowlist[length+1];

   102     int* p=rowlist;

   103     for (int k=1;k<=length;++k){

   104       rowlist[k]=i;

   105     }

   106     status = CPXchgcoeflist(env, lp,

   107 			    length,

   108 			    p+1,

   109 			    const_cast<int * >(indices+1),

   110 			    const_cast<Value * >(values+1));

   111   }

   113   void LpCplex::_setColCoeffs(int i,

   114 			      int length,

   115 			      int  const * indices,

   116 			      Value  const * values)

   117   {

   118     int collist[length+1];

   119     int* p=collist;

   120     for (int k=1;k<=length;++k){

   121       collist[k]=i;

   122     }

   123     status = CPXchgcoeflist(env, lp,

   124 			    length,

   125 			    const_cast<int * >(indices+1),

   126 			    p+1,

   127 			    const_cast<Value * >(values+1));

   128   }

   130   void LpCplex::_setCoeff(int row, int col, Value value)

   131   {

   132     CPXchgcoef(env, lp, row, col, value);

   133   }

   135   void LpCplex::_setColLowerBound(int i, Value value)

   136   {

   137     int indices[1];

   138     indices[0]=i;

   139     char lu[1];

   140     lu[0]='L';

   141     Value bd[1];

   142     bd[0]=value;

   143     status = CPXchgbds(env, lp, 1, indices, lu, bd);

   145   }

   147   void LpCplex::_setColUpperBound(int i, Value value)

   148   {

   149     int indices[1];

   150     indices[0]=i;

   151     char lu[1];

   152     lu[0]='U';

   153     Value bd[1];

   154     bd[0]=value;

   155     status = CPXchgbds(env, lp, 1, indices, lu, bd);

   156   }

   158   //This will be easier to implement

   159   void LpCplex::_setRowBounds(int i, Value lb, Value ub)

   160   {

   161     //Bad parameter

   162     if (lb==INF || ub==-INF) {

   163       //FIXME error

   164     }

   166     int cnt=1;

   167     int indices[1];

   168     indices[0]=i;

   169     char sense[1];

   171     if (lb==-INF){

   172       sense[0]='L';

   173       CPXchgsense(env, lp, cnt, indices, sense);

   174       CPXchgcoef(env, lp, i, -1, ub);

   176     }

   177     else{

   178       if (ub==INF){

   179 	sense[0]='G';

   180 	CPXchgsense(env, lp, cnt, indices, sense);

   181 	CPXchgcoef(env, lp, i, -1, lb);

   182       }

   183       else{

   184 	if (lb == ub){

   185 	  sense[0]='E';

   186 	  CPXchgsense(env, lp, cnt, indices, sense);

   187 	  CPXchgcoef(env, lp, i, -1, lb);

   188 	}

   189 	else{

   190 	  sense[0]='R';

   191 	  CPXchgsense(env, lp, cnt, indices, sense);

   192 	  CPXchgcoef(env, lp, i, -1, lb);

   193 	  CPXchgcoef(env, lp, i, -2, ub-lb);

   194 	}

   195       }

   196     }

   197   }

   199 //   void LpCplex::_setRowLowerBound(int i, Value value)

   200 //   {

   201 //     //Not implemented, obsolete

   202 //   }

   204 //   void LpCplex::_setRowUpperBound(int i, Value value)

   205 //   {

   206 //     //Not implemented, obsolete

   207 // //     //TODO Ezt kell meg megirni

   208 // //     //type of the problem

   209 // //     char sense[1];

   210 // //     status = CPXgetsense(env, lp, sense, i, i);

   211 // //     Value rhs[1];

   212 // //     status = CPXgetrhs(env, lp, rhs, i, i);

   214 // //     switch (sense[0]) {

   215 // //     case 'L'://<= constraint

   216 // //       break;

   217 // //     case 'E'://= constraint

   218 // //       break;

   219 // //     case 'G'://>= constraint

   220 // //       break;

   221 // //     case 'R'://ranged constraint

   222 // //       break;

   223 // //     default: ;

   224 // //       //FIXME error

   225 // //     }

   227 // //     status = CPXchgcoef(env, lp, i, -2, value_rng);

   228 //   }

   230   void LpCplex::_setObjCoeff(int i, Value obj_coef)

   231   {

   232     CPXchgcoef(env, lp, -1, i, obj_coef);

   233   }

   235   void LpCplex::_clearObj()

   236   {

   237     for (int i=0;i< CPXgetnumcols(env, lp);++i){

   238       CPXchgcoef(env, lp, -1, i, 0);

   239     }

   241   }

   242   // The routine returns zero unless an error occurred during the

   243   // optimization. Examples of errors include exhausting available

   244   // memory (CPXERR_NO_MEMORY) or encountering invalid data in the

   245   // CPLEX problem object (CPXERR_NO_PROBLEM). Exceeding a

   246   // user-specified CPLEX limit, or proving the model infeasible or

   247   // unbounded, are not considered errors. Note that a zero return

   248   // value does not necessarily mean that a solution exists. Use query

   249   // routines CPXsolninfo, CPXgetstat, and CPXsolution to obtain

   250   // further information about the status of the optimization.

   251   LpCplex::SolveExitStatus LpCplex::_solve()

   252   {

   253     //CPX_PARAM_LPMETHOD

   254     status = CPXlpopt(env, lp);

   255     //status = CPXprimopt(env, lp);

   256     if (status == 0){

   257       //We want to exclude some cases

   258       switch (CPXgetstat(env, lp)){

   259       case CPX_OBJ_LIM:

   260       case CPX_IT_LIM_FEAS:

   261       case CPX_IT_LIM_INFEAS:

   262       case CPX_TIME_LIM_FEAS:

   263       case CPX_TIME_LIM_INFEAS:

   264 	return UNSOLVED;

   265       default:

   266 	return SOLVED;

   267       }

   268     }

   269     else{

   270       return UNSOLVED;

   271     }

   272   }

   274   LpCplex::Value LpCplex::_getPrimal(int i)

   275   {

   276     Value x;

   277     CPXgetx(env, lp, &x, i, i);

   278     return x;

   279   }

   281   LpCplex::Value LpCplex::_getDual(int i)

   282   {

   283     Value y;

   284     CPXgetpi(env, lp, &y, i, i);

   285     return y;

   286   }

   288   LpCplex::Value LpCplex::_getPrimalValue()

   289   {

   290     Value objval;

   291     //method = CPXgetmethod (env, lp);

   292     //printf("CPXgetprobtype %d \n",CPXgetprobtype(env,lp));

   293     status = CPXgetobjval(env, lp, &objval);

   294     //printf("Objective value: %g \n",objval);

   295     return objval;

   296   }

   297   bool LpCplex::_isBasicCol(int i) {

   298     int cstat[CPXgetnumcols(env, lp)];

   299     CPXgetbase(env, lp, cstat, NULL);

   300     return (cstat[i]==CPX_BASIC);

   301   }

   303 //7.5-os cplex statusai (Vigyazat: a 9.0-asei masok!)

   304 // 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.

   306 // For Simplex, Barrier

   307 // 1  	CPX_OPTIMAL

   308 // 	 Optimal solution found

   309 // 2  	CPX_INFEASIBLE

   310 // 	 Problem infeasible

   311 // 3    CPX_UNBOUNDED

   312 // 	 Problem unbounded

   313 // 4  	CPX_OBJ_LIM

   314 // 	 Objective limit exceeded in Phase II

   315 // 5  	CPX_IT_LIM_FEAS

   316 // 	 Iteration limit exceeded in Phase II

   317 // 6  	CPX_IT_LIM_INFEAS

   318 // 	 Iteration limit exceeded in Phase I

   319 // 7  	CPX_TIME_LIM_FEAS

   320 // 	 Time limit exceeded in Phase II

   321 // 8  	CPX_TIME_LIM_INFEAS

   322 // 	 Time limit exceeded in Phase I

   323 // 9  	CPX_NUM_BEST_FEAS

   324 // 	 Problem non-optimal, singularities in Phase II

   325 // 10 	CPX_NUM_BEST_INFEAS

   326 // 	 Problem non-optimal, singularities in Phase I

   327 // 11 	CPX_OPTIMAL_INFEAS

   328 // 	 Optimal solution found, unscaled infeasibilities

   329 // 12 	CPX_ABORT_FEAS

   330 // 	 Aborted in Phase II

   331 // 13 	CPX_ABORT_INFEAS

   332 // 	 Aborted in Phase I

   333 // 14  	CPX_ABORT_DUAL_INFEAS

   334 // 	 Aborted in barrier, dual infeasible

   335 // 15  	CPX_ABORT_PRIM_INFEAS

   336 // 	 Aborted in barrier, primal infeasible

   337 // 16  	CPX_ABORT_PRIM_DUAL_INFEAS

   338 // 	 Aborted in barrier, primal and dual infeasible

   339 // 17  	CPX_ABORT_PRIM_DUAL_FEAS

   340 // 	 Aborted in barrier, primal and dual feasible

   341 // 18  	CPX_ABORT_CROSSOVER

   342 // 	 Aborted in crossover

   343 // 19  	CPX_INForUNBD

   344 // 	 Infeasible or unbounded

   345 // 20   CPX_PIVOT

   346 //       User pivot used

   347 //

   348 //     Ezeket hova tegyem:

   349 // ??case CPX_ABORT_DUAL_INFEAS

   350 // ??case CPX_ABORT_CROSSOVER

   351 // ??case CPX_INForUNBD

   352 // ??case CPX_PIVOT

   354 //Some more interesting stuff:

   356 // CPX_PARAM_LPMETHOD  1062  int  LPMETHOD

   357 // 0 Automatic

   358 // 1 Primal Simplex

   359 // 2 Dual Simplex

   360 // 3 Network Simplex

   361 // 4 Standard Barrier

   362 // Default: 0

   363 // Description: Method for linear optimization.

   364 // 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

   365   //Hulye cplex

   366   void statusSwitch(CPXENVptr env,int& stat){

   367     int lpmethod;

   368     CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);

   369     if (lpmethod==2){

   370       if (stat==CPX_UNBOUNDED){

   371 	stat=CPX_INFEASIBLE;

   372       }

   373       else{

   374 	if (stat==CPX_INFEASIBLE)

   375 	  stat=CPX_UNBOUNDED;

   376       }

   377     }

   378   }

   380   LpCplex::SolutionStatus LpCplex::_getPrimalStatus()

   381   {

   383     int stat = CPXgetstat(env, lp);

   384     statusSwitch(env,stat);

   385     //CPXgetstat(env, lp);

   386     //printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL);

   387     switch (stat) {

   388     case 0:

   389       return UNDEFINED; //Undefined

   390     case CPX_OPTIMAL://Optimal

   391       return OPTIMAL;

   392     case CPX_UNBOUNDED://Unbounded

   393       return INFEASIBLE;//In case of dual simplex

   394       //return INFINITE;

   395     case CPX_INFEASIBLE://Infeasible

   396  //    case CPX_IT_LIM_INFEAS:

   397 //     case CPX_TIME_LIM_INFEAS:

   398 //     case CPX_NUM_BEST_INFEAS:

   399 //     case CPX_OPTIMAL_INFEAS:

   400 //     case CPX_ABORT_INFEAS:

   401 //     case CPX_ABORT_PRIM_INFEAS:

   402 //     case CPX_ABORT_PRIM_DUAL_INFEAS:

   403       return INFINITE;//In case of dual simplex

   404       //return INFEASIBLE;

   405 //     case CPX_OBJ_LIM:

   406 //     case CPX_IT_LIM_FEAS:

   407 //     case CPX_TIME_LIM_FEAS:

   408 //     case CPX_NUM_BEST_FEAS:

   409 //     case CPX_ABORT_FEAS:

   410 //     case CPX_ABORT_PRIM_DUAL_FEAS:

   411 //       return FEASIBLE;

   412     default:

   413       return UNDEFINED; //Everything else comes here

   414       //FIXME error

   415     }

   417   }

   419 //9.0-as cplex verzio statusai

   420 // CPX_STAT_ABORT_DUAL_OBJ_LIM

   421 // CPX_STAT_ABORT_IT_LIM

   422 // CPX_STAT_ABORT_OBJ_LIM

   423 // CPX_STAT_ABORT_PRIM_OBJ_LIM

   424 // CPX_STAT_ABORT_TIME_LIM

   425 // CPX_STAT_ABORT_USER

   426 // CPX_STAT_FEASIBLE_RELAXED

   427 // CPX_STAT_INFEASIBLE

   428 // CPX_STAT_INForUNBD

   429 // CPX_STAT_NUM_BEST

   430 // CPX_STAT_OPTIMAL

   431 // CPX_STAT_OPTIMAL_FACE_UNBOUNDED

   432 // CPX_STAT_OPTIMAL_INFEAS

   433 // CPX_STAT_OPTIMAL_RELAXED

   434 // CPX_STAT_UNBOUNDED

   436   LpCplex::SolutionStatus LpCplex::_getDualStatus()

   437   {

   438     int stat = CPXgetstat(env, lp);

   439     statusSwitch(env,stat);

   440     switch (stat) {

   441     case 0:

   442       return UNDEFINED; //Undefined

   443     case CPX_OPTIMAL://Optimal

   444       return OPTIMAL;

   445     case CPX_UNBOUNDED:

   446      return INFEASIBLE;

   447     default:

   448       return UNDEFINED; //Everything else comes here

   449       //FIXME error

   450     }

   451   }

   453   LpCplex::ProblemTypes LpCplex::_getProblemType()

   454   {

   455     int stat = CPXgetstat(env, lp);

   456     switch (stat) {

   457     case CPX_OPTIMAL://Optimal

   458 	return PRIMAL_DUAL_FEASIBLE;

   459     case CPX_UNBOUNDED:

   460  	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

   461 // 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;

   462 // 	return PRIMAL_DUAL_INFEASIBLE;

   464 //Seems to be that this is all we can say for sure

   465     default:

   466 	//In all other cases

   467 	return UNKNOWN;

   468       //FIXME error

   469     }

   470   }

   472   void LpCplex::_setMax()

   473   {

   474     CPXchgobjsen(env, lp, CPX_MAX);

   475    }

   476   void LpCplex::_setMin()

   477   {

   478     CPXchgobjsen(env, lp, CPX_MIN);

   479    }

   481 } //namespace lemon

author	deba
	Tue, 24 Jan 2006 16:07:38 +0000
changeset 1901	723b2b81d900
parent 1875	98698b69a902
child 1950	a1a6f5b788bd
permissions	-rw-r--r--