lemon-0.x: lemon/lp_cplex.cc@cddae1c4fee6

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

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2006

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

     8  *

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

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

    11  * precise terms see the accompanying LICENSE file.

    12  *

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

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

    15  * purpose.

    16  *

    17  */

    19 #include <iostream>

    20 #include<lemon/lp_cplex.h>

    22 ///\file

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

    24 namespace lemon {

    26   LpCplex::LpCplex() : LpSolverBase() {

    28     //    env = CPXopenCPLEXdevelop(&status);

    29     env = CPXopenCPLEX(&status);

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

    31   }

    33   LpCplex::~LpCplex() {

    34     CPXfreeprob(env,&lp);

    35     CPXcloseCPLEX(&env);

    36   }

    38   LpSolverBase &LpCplex::_newLp()

    39   {

    40     //The first approach opens a new environment

    41     LpCplex* newlp=new LpCplex();

    42     return *newlp;

    43   }

    45   LpSolverBase &LpCplex::_copyLp() {

    46     //The first approach opens a new environment

    47     LpCplex* newlp=new LpCplex();

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

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

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

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

    52     return *newlp;

    53   }

    55   int LpCplex::_addCol()

    56   {

    57     int i = CPXgetnumcols(env, lp);

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

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

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

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

    62     return i;

    63   }

    66   int LpCplex::_addRow()

    67   {

    68     //We want a row that is not constrained

    69     char sense[1];

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

    71     Value rhs[1];

    72     rhs[0]=INF;

    73     int i = CPXgetnumrows(env, lp);

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

    75     return i;

    76   }

    79   void LpCplex::_eraseCol(int i) {

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

    81   }

    83   void LpCplex::_eraseRow(int i) {

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

    85   }

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

    88   {

    89     ///\bug Untested

    90     int storespace;

    91     CPXgetcolname(env, lp, 0, 0, 0, &storespace, col, col);

    93     storespace *= -1;

    94     char buf[storespace];

    95     char *names[1];

    96     int dontcare;

    97     ///\bug return code unchecked for error

    98     CPXgetcolname(env, lp, names, buf, storespace, &dontcare, col, col);

    99     name = names[0];

   100   }

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

   103   {

   104     ///\bug Untested

   105     char *names[1];

   106     names[0] = const_cast<char*>(name.c_str());

   107     ///\bug return code unchecked for error

   108     CPXchgcolname(env, lp, 1, &col, names);

   109   }

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

   112   void LpCplex::_setRowCoeffs(int i,

   113 			      int length,

   114 			      int  const * indices,

   115 			      Value  const * values )

   116   {

   117     int rowlist[length+1];

   118     int* p=rowlist;

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

   120       rowlist[k]=i;

   121     }

   122     status = CPXchgcoeflist(env, lp,

   123 			    length,

   124 			    p+1,

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

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

   127   }

   129   void LpCplex::_setColCoeffs(int i,

   130 			      int length,

   131 			      int  const * indices,

   132 			      Value  const * values)

   133   {

   134     int collist[length+1];

   135     int* p=collist;

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

   137       collist[k]=i;

   138     }

   139     status = CPXchgcoeflist(env, lp,

   140 			    length,

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

   142 			    p+1,

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

   144   }

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

   147   {

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

   149   }

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

   152   {

   153     int indices[1];

   154     indices[0]=i;

   155     char lu[1];

   156     lu[0]='L';

   157     Value bd[1];

   158     bd[0]=value;

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

   161   }

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

   164   {

   165     int indices[1];

   166     indices[0]=i;

   167     char lu[1];

   168     lu[0]='U';

   169     Value bd[1];

   170     bd[0]=value;

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

   172   }

   174   //This will be easier to implement

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

   176   {

   177     //Bad parameter

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

   179       //FIXME error

   180     }

   182     int cnt=1;

   183     int indices[1];

   184     indices[0]=i;

   185     char sense[1];

   187     if (lb==-INF){

   188       sense[0]='L';

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

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

   192     }

   193     else{

   194       if (ub==INF){

   195 	sense[0]='G';

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

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

   198       }

   199       else{

   200 	if (lb == ub){

   201 	  sense[0]='E';

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

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

   204 	}

   205 	else{

   206 	  sense[0]='R';

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

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

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

   210 	}

   211       }

   212     }

   213   }

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

   216 //   {

   217 //     //Not implemented, obsolete

   218 //   }

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

   221 //   {

   222 //     //Not implemented, obsolete

   223 // //     //TODO Ezt kell meg megirni

   224 // //     //type of the problem

   225 // //     char sense[1];

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

   227 // //     Value rhs[1];

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

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

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

   232 // //       break;

   233 // //     case 'E'://= constraint

   234 // //       break;

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

   236 // //       break;

   237 // //     case 'R'://ranged constraint

   238 // //       break;

   239 // //     default: ;

   240 // //       //FIXME error

   241 // //     }

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

   244 //   }

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

   247   {

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

   249   }

   251   void LpCplex::_clearObj()

   252   {

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

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

   255     }

   257   }

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

   259   // optimization. Examples of errors include exhausting available

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

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

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

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

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

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

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

   267   LpCplex::SolveExitStatus LpCplex::_solve()

   268   {

   269     //CPX_PARAM_LPMETHOD

   270     status = CPXlpopt(env, lp);

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

   272 #if CPX_VERSION >= 800

   273     if (status)

   274     {

   275       return UNSOLVED;

   276     }

   277     else

   278     {

   279       switch (CPXgetstat(env, lp))

   280       {

   281         case CPX_STAT_OPTIMAL:

   282         case CPX_STAT_INFEASIBLE:

   283         case CPX_STAT_UNBOUNDED:

   284           return SOLVED;

   285         default:

   286           return UNSOLVED;

   287       }

   288     }

   289 #else

   290     if (status == 0){

   291       //We want to exclude some cases

   292       switch (CPXgetstat(env, lp)){

   293       case CPX_OBJ_LIM:

   294       case CPX_IT_LIM_FEAS:

   295       case CPX_IT_LIM_INFEAS:

   296       case CPX_TIME_LIM_FEAS:

   297       case CPX_TIME_LIM_INFEAS:

   298 	return UNSOLVED;

   299       default:

   300 	return SOLVED;

   301       }

   302     }

   303     else{

   304       return UNSOLVED;

   305     }

   306 #endif

   307   }

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

   310   {

   311     Value x;

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

   313     return x;

   314   }

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

   317   {

   318     Value y;

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

   320     return y;

   321   }

   323   LpCplex::Value LpCplex::_getPrimalValue()

   324   {

   325     Value objval;

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

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

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

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

   330     return objval;

   331   }

   332   bool LpCplex::_isBasicCol(int i) {

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

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

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

   336   }

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

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

   341 // For Simplex, Barrier

   342 // 1  	CPX_OPTIMAL

   343 // 	 Optimal solution found

   344 // 2  	CPX_INFEASIBLE

   345 // 	 Problem infeasible

   346 // 3    CPX_UNBOUNDED

   347 // 	 Problem unbounded

   348 // 4  	CPX_OBJ_LIM

   349 // 	 Objective limit exceeded in Phase II

   350 // 5  	CPX_IT_LIM_FEAS

   351 // 	 Iteration limit exceeded in Phase II

   352 // 6  	CPX_IT_LIM_INFEAS

   353 // 	 Iteration limit exceeded in Phase I

   354 // 7  	CPX_TIME_LIM_FEAS

   355 // 	 Time limit exceeded in Phase II

   356 // 8  	CPX_TIME_LIM_INFEAS

   357 // 	 Time limit exceeded in Phase I

   358 // 9  	CPX_NUM_BEST_FEAS

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

   360 // 10 	CPX_NUM_BEST_INFEAS

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

   362 // 11 	CPX_OPTIMAL_INFEAS

   363 // 	 Optimal solution found, unscaled infeasibilities

   364 // 12 	CPX_ABORT_FEAS

   365 // 	 Aborted in Phase II

   366 // 13 	CPX_ABORT_INFEAS

   367 // 	 Aborted in Phase I

   368 // 14  	CPX_ABORT_DUAL_INFEAS

   369 // 	 Aborted in barrier, dual infeasible

   370 // 15  	CPX_ABORT_PRIM_INFEAS

   371 // 	 Aborted in barrier, primal infeasible

   372 // 16  	CPX_ABORT_PRIM_DUAL_INFEAS

   373 // 	 Aborted in barrier, primal and dual infeasible

   374 // 17  	CPX_ABORT_PRIM_DUAL_FEAS

   375 // 	 Aborted in barrier, primal and dual feasible

   376 // 18  	CPX_ABORT_CROSSOVER

   377 // 	 Aborted in crossover

   378 // 19  	CPX_INForUNBD

   379 // 	 Infeasible or unbounded

   380 // 20   CPX_PIVOT

   381 //       User pivot used

   382 //

   383 //     Ezeket hova tegyem:

   384 // ??case CPX_ABORT_DUAL_INFEAS

   385 // ??case CPX_ABORT_CROSSOVER

   386 // ??case CPX_INForUNBD

   387 // ??case CPX_PIVOT

   389 //Some more interesting stuff:

   391 // CPX_PARAM_LPMETHOD  1062  int  LPMETHOD

   392 // 0 Automatic

   393 // 1 Primal Simplex

   394 // 2 Dual Simplex

   395 // 3 Network Simplex

   396 // 4 Standard Barrier

   397 // Default: 0

   398 // Description: Method for linear optimization.

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

   400   //Hulye cplex

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

   402 #if CPX_VERSION < 900

   403     int lpmethod;

   404     CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);

   405     if (lpmethod==2){

   406       if (stat==CPX_UNBOUNDED){

   407 	stat=CPX_INFEASIBLE;

   408       }

   409       else{

   410 	if (stat==CPX_INFEASIBLE)

   411 	  stat=CPX_UNBOUNDED;

   412       }

   413     }

   414 #endif

   415   }

   417   LpCplex::SolutionStatus LpCplex::_getPrimalStatus()

   418   {

   419     //Unboundedness not treated well: the following is from cplex 9.0 doc

   420     // About Unboundedness

   422     // The treatment of models that are unbounded involves a few

   423     // subtleties. Specifically, a declaration of unboundedness means that

   424     // ILOG CPLEX has determined that the model has an unbounded

   425     // ray. Given any feasible solution x with objective z, a multiple of

   426     // the unbounded ray can be added to x to give a feasible solution

   427     // with objective z-1 (or z+1 for maximization models). Thus, if a

   428     // feasible solution exists, then the optimal objective is

   429     // unbounded. Note that ILOG CPLEX has not necessarily concluded that

   430     // a feasible solution exists. Users can call the routine CPXsolninfo

   431     // to determine whether ILOG CPLEX has also concluded that the model

   432     // has a feasible solution.

   434     int stat = CPXgetstat(env, lp);

   435 #if CPX_VERSION >= 800

   436     switch (stat)

   437     {

   438       case CPX_STAT_OPTIMAL:

   439         return OPTIMAL;

   440       case CPX_STAT_UNBOUNDED:

   441         return INFINITE;

   442       case CPX_STAT_INFEASIBLE:

   443         return INFEASIBLE;

   444       default:

   445         return UNDEFINED;

   446     }

   447 #else

   448     statusSwitch(env,stat);

   449     //CPXgetstat(env, lp);

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

   451     switch (stat) {

   452     case 0:

   453       return UNDEFINED; //Undefined

   454     case CPX_OPTIMAL://Optimal

   455       return OPTIMAL;

   456     case CPX_UNBOUNDED://Unbounded

   457       return INFEASIBLE;//In case of dual simplex

   458       //return INFINITE;

   459     case CPX_INFEASIBLE://Infeasible

   460  //    case CPX_IT_LIM_INFEAS:

   461 //     case CPX_TIME_LIM_INFEAS:

   462 //     case CPX_NUM_BEST_INFEAS:

   463 //     case CPX_OPTIMAL_INFEAS:

   464 //     case CPX_ABORT_INFEAS:

   465 //     case CPX_ABORT_PRIM_INFEAS:

   466 //     case CPX_ABORT_PRIM_DUAL_INFEAS:

   467       return INFINITE;//In case of dual simplex

   468       //return INFEASIBLE;

   469 //     case CPX_OBJ_LIM:

   470 //     case CPX_IT_LIM_FEAS:

   471 //     case CPX_TIME_LIM_FEAS:

   472 //     case CPX_NUM_BEST_FEAS:

   473 //     case CPX_ABORT_FEAS:

   474 //     case CPX_ABORT_PRIM_DUAL_FEAS:

   475 //       return FEASIBLE;

   476     default:

   477       return UNDEFINED; //Everything else comes here

   478       //FIXME error

   479     }

   480 #endif

   481   }

   483 //9.0-as cplex verzio statusai

   484 // CPX_STAT_ABORT_DUAL_OBJ_LIM

   485 // CPX_STAT_ABORT_IT_LIM

   486 // CPX_STAT_ABORT_OBJ_LIM

   487 // CPX_STAT_ABORT_PRIM_OBJ_LIM

   488 // CPX_STAT_ABORT_TIME_LIM

   489 // CPX_STAT_ABORT_USER

   490 // CPX_STAT_FEASIBLE_RELAXED

   491 // CPX_STAT_INFEASIBLE

   492 // CPX_STAT_INForUNBD

   493 // CPX_STAT_NUM_BEST

   494 // CPX_STAT_OPTIMAL

   495 // CPX_STAT_OPTIMAL_FACE_UNBOUNDED

   496 // CPX_STAT_OPTIMAL_INFEAS

   497 // CPX_STAT_OPTIMAL_RELAXED

   498 // CPX_STAT_UNBOUNDED

   500   LpCplex::SolutionStatus LpCplex::_getDualStatus()

   501   {

   502     int stat = CPXgetstat(env, lp);

   503 #if CPX_VERSION >= 800

   504     switch (stat)

   505     {

   506       case CPX_STAT_OPTIMAL:

   507         return OPTIMAL;

   508       case CPX_STAT_UNBOUNDED:

   509         return INFEASIBLE;

   510       default:

   511         return UNDEFINED;

   512     }

   513 #else

   514     statusSwitch(env,stat);

   515     switch (stat) {

   516     case 0:

   517       return UNDEFINED; //Undefined

   518     case CPX_OPTIMAL://Optimal

   519       return OPTIMAL;

   520     case CPX_UNBOUNDED:

   521      return INFEASIBLE;

   522     default:

   523       return UNDEFINED; //Everything else comes here

   524       //FIXME error

   525     }

   526 #endif

   527   }

   529   LpCplex::ProblemTypes LpCplex::_getProblemType()

   530   {

   531     int stat = CPXgetstat(env, lp);

   532 #if CPX_VERSION >= 800

   533     switch (stat)

   534     {

   535       case CPX_STAT_OPTIMAL:

   536 	return PRIMAL_DUAL_FEASIBLE;

   537       case CPX_STAT_UNBOUNDED:

   538  	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

   539       default:

   540         return UNKNOWN;

   541     }

   542 #else

   543     switch (stat) {

   544     case CPX_OPTIMAL://Optimal

   545 	return PRIMAL_DUAL_FEASIBLE;

   546     case CPX_UNBOUNDED:

   547  	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

   548 // 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;

   549 // 	return PRIMAL_DUAL_INFEASIBLE;

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

   552     default:

   553 	//In all other cases

   554 	return UNKNOWN;

   555       //FIXME error

   556     }

   557 #endif

   558   }

   560   void LpCplex::_setMax()

   561   {

   562     CPXchgobjsen(env, lp, CPX_MAX);

   563    }

   564   void LpCplex::_setMin()

   565   {

   566     CPXchgobjsen(env, lp, CPX_MIN);

   567    }

   569 } //namespace lemon

author	deba
	Fri, 24 Nov 2006 14:24:43 +0000
changeset 2308	cddae1c4fee6
parent 2168	6474b8254f24
child 2312	07e46cbb7d85
permissions	-rw-r--r--