lemon/lp_cplex.cc
author deba
Fri, 24 Nov 2006 14:24:43 +0000
changeset 2308 cddae1c4fee6
parent 2168 6474b8254f24
child 2312 07e46cbb7d85
permissions -rw-r--r--
Erasing unionfind Item template parameter
     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  */
    18 
    19 #include <iostream>
    20 #include<lemon/lp_cplex.h>
    21 
    22 ///\file
    23 ///\brief Implementation of the LEMON-CPLEX lp solver interface.
    24 namespace lemon {
    25   
    26   LpCplex::LpCplex() : LpSolverBase() {
    27 
    28     //    env = CPXopenCPLEXdevelop(&status);     
    29     env = CPXopenCPLEX(&status);     
    30     lp = CPXcreateprob(env, &status, "LP problem");
    31   }
    32   
    33   LpCplex::~LpCplex() {
    34     CPXfreeprob(env,&lp); 
    35     CPXcloseCPLEX(&env); 
    36   }
    37   
    38   LpSolverBase &LpCplex::_newLp() 
    39   {
    40     //The first approach opens a new environment
    41     LpCplex* newlp=new LpCplex();
    42     return *newlp;
    43   }
    44 
    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   }
    54 
    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   }
    64 
    65   
    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   }
    77 
    78 
    79   void LpCplex::_eraseCol(int i) {
    80     CPXdelcols(env, lp, i, i);
    81   }
    82   
    83   void LpCplex::_eraseRow(int i) {
    84     CPXdelrows(env, lp, i, i);
    85   }
    86   
    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);
    92 
    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   }
   101   
   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   }
   110   
   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   }
   128   
   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   }
   145   
   146   void LpCplex::_setCoeff(int row, int col, Value value) 
   147   {
   148     CPXchgcoef(env, lp, row, col, value);
   149   }
   150 
   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);
   160  
   161   }
   162   
   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   }
   173 
   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     }
   181     
   182     int cnt=1;
   183     int indices[1];
   184     indices[0]=i;
   185     char sense[1];
   186 
   187     if (lb==-INF){
   188       sense[0]='L';
   189       CPXchgsense(env, lp, cnt, indices, sense);
   190       CPXchgcoef(env, lp, i, -1, ub);
   191       
   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   }
   214 
   215 //   void LpCplex::_setRowLowerBound(int i, Value value)
   216 //   {
   217 //     //Not implemented, obsolete
   218 //   }
   219   
   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);
   229 
   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 // //     }
   242 
   243 // //     status = CPXchgcoef(env, lp, i, -2, value_rng);
   244 //   }
   245   
   246   void LpCplex::_setObjCoeff(int i, Value obj_coef)
   247   {
   248     CPXchgcoef(env, lp, -1, i, obj_coef);
   249   }
   250 
   251   void LpCplex::_clearObj()
   252   {
   253     for (int i=0;i< CPXgetnumcols(env, lp);++i){
   254       CPXchgcoef(env, lp, -1, i, 0);
   255     }
   256     
   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   }
   308 
   309   LpCplex::Value LpCplex::_getPrimal(int i)
   310   {
   311     Value x;
   312     CPXgetx(env, lp, &x, i, i);
   313     return x;
   314   }
   315 
   316   LpCplex::Value LpCplex::_getDual(int i)
   317   {
   318     Value y;
   319     CPXgetpi(env, lp, &y, i, i);
   320     return y;
   321   }
   322   
   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   }  
   337 
   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.
   340 
   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              
   388          
   389 //Some more interesting stuff:
   390 
   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   }
   416 
   417   LpCplex::SolutionStatus LpCplex::_getPrimalStatus()
   418   {
   419     //Unboundedness not treated well: the following is from cplex 9.0 doc
   420     // About Unboundedness
   421 
   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.
   433 
   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   }
   482 
   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
   499 
   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   }
   528 
   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;
   550 
   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   }
   559 
   560   void LpCplex::_setMax()
   561   {
   562     CPXchgobjsen(env, lp, CPX_MAX);
   563    }
   564   void LpCplex::_setMin()
   565   {
   566     CPXchgobjsen(env, lp, CPX_MIN);
   567    }
   568   
   569 } //namespace lemon
   570