lemon/lp_cplex.cc
author alpar
Thu, 02 Feb 2006 08:52:20 +0000
changeset 1941 9fe177e0437d
parent 1875 98698b69a902
child 1950 a1a6f5b788bd
permissions -rw-r--r--
The version tag of the trunk is svn-head
     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>
    18 
    19 ///\file
    20 ///\brief Implementation of the LEMON-CPLEX lp solver interface.
    21 namespace lemon {
    22   
    23   LpCplex::LpCplex() : LpSolverBase() {
    24 
    25     //    env = CPXopenCPLEXdevelop(&status);     
    26     env = CPXopenCPLEX(&status);     
    27     lp = CPXcreateprob(env, &status, "LP problem");
    28   }
    29   
    30   LpCplex::~LpCplex() {
    31     CPXfreeprob(env,&lp); 
    32     CPXcloseCPLEX(&env); 
    33   }
    34   
    35   LpSolverBase &LpCplex::_newLp() 
    36   {
    37     //The first approach opens a new environment
    38     LpCplex* newlp=new LpCplex();
    39     return *newlp;
    40   }
    41 
    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   }
    51 
    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   }
    61 
    62   
    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   }
    74 
    75 
    76   void LpCplex::_eraseCol(int i) {
    77     CPXdelcols(env, lp, i, i);
    78   }
    79   
    80   void LpCplex::_eraseRow(int i) {
    81     CPXdelrows(env, lp, i, i);
    82   }
    83   
    84   void LpCplex::_getColName(int col, std::string &name)
    85   {
    86     ///\bug Unimplemented
    87   }
    88   
    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   }
    94   
    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   }
   112   
   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   }
   129   
   130   void LpCplex::_setCoeff(int row, int col, Value value) 
   131   {
   132     CPXchgcoef(env, lp, row, col, value);
   133   }
   134 
   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);
   144  
   145   }
   146   
   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   }
   157 
   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     }
   165     
   166     int cnt=1;
   167     int indices[1];
   168     indices[0]=i;
   169     char sense[1];
   170 
   171     if (lb==-INF){
   172       sense[0]='L';
   173       CPXchgsense(env, lp, cnt, indices, sense);
   174       CPXchgcoef(env, lp, i, -1, ub);
   175       
   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   }
   198 
   199 //   void LpCplex::_setRowLowerBound(int i, Value value)
   200 //   {
   201 //     //Not implemented, obsolete
   202 //   }
   203   
   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);
   213 
   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 // //     }
   226 
   227 // //     status = CPXchgcoef(env, lp, i, -2, value_rng);
   228 //   }
   229   
   230   void LpCplex::_setObjCoeff(int i, Value obj_coef)
   231   {
   232     CPXchgcoef(env, lp, -1, i, obj_coef);
   233   }
   234 
   235   void LpCplex::_clearObj()
   236   {
   237     for (int i=0;i< CPXgetnumcols(env, lp);++i){
   238       CPXchgcoef(env, lp, -1, i, 0);
   239     }
   240     
   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   }
   273 
   274   LpCplex::Value LpCplex::_getPrimal(int i)
   275   {
   276     Value x;
   277     CPXgetx(env, lp, &x, i, i);
   278     return x;
   279   }
   280 
   281   LpCplex::Value LpCplex::_getDual(int i)
   282   {
   283     Value y;
   284     CPXgetpi(env, lp, &y, i, i);
   285     return y;
   286   }
   287   
   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   }  
   302 
   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.
   305 
   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              
   353          
   354 //Some more interesting stuff:
   355 
   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   }
   379 
   380   LpCplex::SolutionStatus LpCplex::_getPrimalStatus()
   381   {
   382     
   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     }
   416 
   417   }
   418 
   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
   435 
   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   }
   452 
   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;
   463 
   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   }
   471 
   472   void LpCplex::_setMax()
   473   {
   474     CPXchgobjsen(env, lp, CPX_MAX);
   475    }
   476   void LpCplex::_setMin()
   477   {
   478     CPXchgobjsen(env, lp, CPX_MIN);
   479    }
   480   
   481 } //namespace lemon
   482