lemon/lp_cplex.cc
author alpar
Tue, 18 Jul 2006 16:59:34 +0000
changeset 2154 bbc79b698f62
parent 1950 a1a6f5b788bd
child 2168 6474b8254f24
permissions -rw-r--r--
Tolerance<unsigned int> and Tolerance<unsigned long long int> added.
     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 (status == 0){
   273       //We want to exclude some cases
   274       switch (CPXgetstat(env, lp)){
   275       case CPX_OBJ_LIM:
   276       case CPX_IT_LIM_FEAS:
   277       case CPX_IT_LIM_INFEAS:               
   278       case CPX_TIME_LIM_FEAS:
   279       case CPX_TIME_LIM_INFEAS:
   280 	return UNSOLVED;
   281       default:
   282 	return SOLVED; 
   283       }
   284     }
   285     else{
   286       return UNSOLVED;
   287     }
   288   }
   289 
   290   LpCplex::Value LpCplex::_getPrimal(int i)
   291   {
   292     Value x;
   293     CPXgetx(env, lp, &x, i, i);
   294     return x;
   295   }
   296 
   297   LpCplex::Value LpCplex::_getDual(int i)
   298   {
   299     Value y;
   300     CPXgetpi(env, lp, &y, i, i);
   301     return y;
   302   }
   303   
   304   LpCplex::Value LpCplex::_getPrimalValue()
   305   {
   306     Value objval;
   307     //method = CPXgetmethod (env, lp);
   308     //printf("CPXgetprobtype %d \n",CPXgetprobtype(env,lp));
   309     status = CPXgetobjval(env, lp, &objval);
   310     //printf("Objective value: %g \n",objval);
   311     return objval;
   312   }
   313   bool LpCplex::_isBasicCol(int i) {
   314     int cstat[CPXgetnumcols(env, lp)];
   315     CPXgetbase(env, lp, cstat, NULL);
   316     return (cstat[i]==CPX_BASIC);
   317   }  
   318 
   319 //7.5-os cplex statusai (Vigyazat: a 9.0-asei masok!)
   320 // 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.
   321 
   322 // For Simplex, Barrier  
   323 // 1  	CPX_OPTIMAL  
   324 // 	 Optimal solution found  
   325 // 2  	CPX_INFEASIBLE  
   326 // 	 Problem infeasible  
   327 // 3    CPX_UNBOUNDED  
   328 // 	 Problem unbounded  
   329 // 4  	CPX_OBJ_LIM  
   330 // 	 Objective limit exceeded in Phase II  
   331 // 5  	CPX_IT_LIM_FEAS  
   332 // 	 Iteration limit exceeded in Phase II  
   333 // 6  	CPX_IT_LIM_INFEAS  
   334 // 	 Iteration limit exceeded in Phase I  
   335 // 7  	CPX_TIME_LIM_FEAS  
   336 // 	 Time limit exceeded in Phase II  
   337 // 8  	CPX_TIME_LIM_INFEAS  
   338 // 	 Time limit exceeded in Phase I  
   339 // 9  	CPX_NUM_BEST_FEAS  
   340 // 	 Problem non-optimal, singularities in Phase II  
   341 // 10 	CPX_NUM_BEST_INFEAS  
   342 // 	 Problem non-optimal, singularities in Phase I  
   343 // 11 	CPX_OPTIMAL_INFEAS  
   344 // 	 Optimal solution found, unscaled infeasibilities  
   345 // 12 	CPX_ABORT_FEAS  
   346 // 	 Aborted in Phase II  
   347 // 13 	CPX_ABORT_INFEAS  
   348 // 	 Aborted in Phase I  
   349 // 14  	CPX_ABORT_DUAL_INFEAS  
   350 // 	 Aborted in barrier, dual infeasible  
   351 // 15  	CPX_ABORT_PRIM_INFEAS  
   352 // 	 Aborted in barrier, primal infeasible  
   353 // 16  	CPX_ABORT_PRIM_DUAL_INFEAS  
   354 // 	 Aborted in barrier, primal and dual infeasible  
   355 // 17  	CPX_ABORT_PRIM_DUAL_FEAS  
   356 // 	 Aborted in barrier, primal and dual feasible  
   357 // 18  	CPX_ABORT_CROSSOVER  
   358 // 	 Aborted in crossover  
   359 // 19  	CPX_INForUNBD  
   360 // 	 Infeasible or unbounded  
   361 // 20   CPX_PIVOT
   362 //       User pivot used
   363 //
   364 //     Ezeket hova tegyem:
   365 // ??case CPX_ABORT_DUAL_INFEAS           
   366 // ??case CPX_ABORT_CROSSOVER             
   367 // ??case CPX_INForUNBD                   
   368 // ??case CPX_PIVOT              
   369          
   370 //Some more interesting stuff:
   371 
   372 // CPX_PARAM_LPMETHOD  1062  int  LPMETHOD
   373 // 0 Automatic 
   374 // 1 Primal Simplex 
   375 // 2 Dual Simplex 
   376 // 3 Network Simplex 
   377 // 4 Standard Barrier 
   378 // Default: 0 
   379 // Description: Method for linear optimization. 
   380 // 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 
   381   //Hulye cplex
   382   void statusSwitch(CPXENVptr env,int& stat){
   383     int lpmethod;
   384     CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);
   385     if (lpmethod==2){
   386       if (stat==CPX_UNBOUNDED){
   387 	stat=CPX_INFEASIBLE;
   388       }
   389       else{
   390 	if (stat==CPX_INFEASIBLE)
   391 	  stat=CPX_UNBOUNDED;
   392       }
   393     }
   394   }
   395 
   396   LpCplex::SolutionStatus LpCplex::_getPrimalStatus()
   397   {
   398     
   399     int stat = CPXgetstat(env, lp);
   400     statusSwitch(env,stat);
   401     //CPXgetstat(env, lp);
   402     //printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL);
   403     switch (stat) {
   404     case 0:
   405       return UNDEFINED; //Undefined
   406     case CPX_OPTIMAL://Optimal
   407       return OPTIMAL;
   408     case CPX_UNBOUNDED://Unbounded
   409       return INFEASIBLE;//In case of dual simplex
   410       //return INFINITE;
   411     case CPX_INFEASIBLE://Infeasible 
   412  //    case CPX_IT_LIM_INFEAS:
   413 //     case CPX_TIME_LIM_INFEAS:
   414 //     case CPX_NUM_BEST_INFEAS:             
   415 //     case CPX_OPTIMAL_INFEAS:              
   416 //     case CPX_ABORT_INFEAS:                
   417 //     case CPX_ABORT_PRIM_INFEAS:           
   418 //     case CPX_ABORT_PRIM_DUAL_INFEAS:      
   419       return INFINITE;//In case of dual simplex
   420       //return INFEASIBLE;
   421 //     case CPX_OBJ_LIM:                    
   422 //     case CPX_IT_LIM_FEAS:             
   423 //     case CPX_TIME_LIM_FEAS:                
   424 //     case CPX_NUM_BEST_FEAS:                
   425 //     case CPX_ABORT_FEAS:                  
   426 //     case CPX_ABORT_PRIM_DUAL_FEAS:        
   427 //       return FEASIBLE;
   428     default:
   429       return UNDEFINED; //Everything else comes here
   430       //FIXME error
   431     }
   432 
   433   }
   434 
   435 //9.0-as cplex verzio statusai
   436 // CPX_STAT_ABORT_DUAL_OBJ_LIM
   437 // CPX_STAT_ABORT_IT_LIM
   438 // CPX_STAT_ABORT_OBJ_LIM
   439 // CPX_STAT_ABORT_PRIM_OBJ_LIM
   440 // CPX_STAT_ABORT_TIME_LIM
   441 // CPX_STAT_ABORT_USER
   442 // CPX_STAT_FEASIBLE_RELAXED
   443 // CPX_STAT_INFEASIBLE
   444 // CPX_STAT_INForUNBD
   445 // CPX_STAT_NUM_BEST
   446 // CPX_STAT_OPTIMAL
   447 // CPX_STAT_OPTIMAL_FACE_UNBOUNDED
   448 // CPX_STAT_OPTIMAL_INFEAS
   449 // CPX_STAT_OPTIMAL_RELAXED
   450 // CPX_STAT_UNBOUNDED
   451 
   452   LpCplex::SolutionStatus LpCplex::_getDualStatus()
   453   {
   454     int stat = CPXgetstat(env, lp);
   455     statusSwitch(env,stat);
   456     switch (stat) {
   457     case 0:
   458       return UNDEFINED; //Undefined
   459     case CPX_OPTIMAL://Optimal
   460       return OPTIMAL;
   461     case CPX_UNBOUNDED:
   462      return INFEASIBLE;
   463     default:
   464       return UNDEFINED; //Everything else comes here
   465       //FIXME error
   466     }
   467   }
   468 
   469   LpCplex::ProblemTypes LpCplex::_getProblemType()
   470   {
   471     int stat = CPXgetstat(env, lp);
   472     switch (stat) {
   473     case CPX_OPTIMAL://Optimal
   474 	return PRIMAL_DUAL_FEASIBLE;
   475     case CPX_UNBOUNDED:
   476  	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
   477 // 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
   478 // 	return PRIMAL_DUAL_INFEASIBLE;
   479 
   480 //Seems to be that this is all we can say for sure
   481     default:
   482 	//In all other cases
   483 	return UNKNOWN;
   484       //FIXME error
   485     }
   486   }
   487 
   488   void LpCplex::_setMax()
   489   {
   490     CPXchgobjsen(env, lp, CPX_MAX);
   491    }
   492   void LpCplex::_setMin()
   493   {
   494     CPXchgobjsen(env, lp, CPX_MIN);
   495    }
   496   
   497 } //namespace lemon
   498