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

     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 >= 900

   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     int stat = CPXgetstat(env, lp);

   420 #if CPX_VERSION >= 900

   421     switch (stat)

   422     {

   423       case CPX_STAT_OPTIMAL:

   424         return OPTIMAL;

   425       case CPX_STAT_UNBOUNDED:

   426         return INFINITE;

   427       case CPX_STAT_INFEASIBLE:

   428         return INFEASIBLE;

   429       default:

   430         return UNDEFINED;

   431     }

   432 #else

   433     statusSwitch(env,stat);

   434     //CPXgetstat(env, lp);

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

   436     switch (stat) {

   437     case 0:

   438       return UNDEFINED; //Undefined

   439     case CPX_OPTIMAL://Optimal

   440       return OPTIMAL;

   441     case CPX_UNBOUNDED://Unbounded

   442       return INFEASIBLE;//In case of dual simplex

   443       //return INFINITE;

   444     case CPX_INFEASIBLE://Infeasible

   445  //    case CPX_IT_LIM_INFEAS:

   446 //     case CPX_TIME_LIM_INFEAS:

   447 //     case CPX_NUM_BEST_INFEAS:

   448 //     case CPX_OPTIMAL_INFEAS:

   449 //     case CPX_ABORT_INFEAS:

   450 //     case CPX_ABORT_PRIM_INFEAS:

   451 //     case CPX_ABORT_PRIM_DUAL_INFEAS:

   452       return INFINITE;//In case of dual simplex

   453       //return INFEASIBLE;

   454 //     case CPX_OBJ_LIM:

   455 //     case CPX_IT_LIM_FEAS:

   456 //     case CPX_TIME_LIM_FEAS:

   457 //     case CPX_NUM_BEST_FEAS:

   458 //     case CPX_ABORT_FEAS:

   459 //     case CPX_ABORT_PRIM_DUAL_FEAS:

   460 //       return FEASIBLE;

   461     default:

   462       return UNDEFINED; //Everything else comes here

   463       //FIXME error

   464     }

   465 #endif

   466   }

   468 //9.0-as cplex verzio statusai

   469 // CPX_STAT_ABORT_DUAL_OBJ_LIM

   470 // CPX_STAT_ABORT_IT_LIM

   471 // CPX_STAT_ABORT_OBJ_LIM

   472 // CPX_STAT_ABORT_PRIM_OBJ_LIM

   473 // CPX_STAT_ABORT_TIME_LIM

   474 // CPX_STAT_ABORT_USER

   475 // CPX_STAT_FEASIBLE_RELAXED

   476 // CPX_STAT_INFEASIBLE

   477 // CPX_STAT_INForUNBD

   478 // CPX_STAT_NUM_BEST

   479 // CPX_STAT_OPTIMAL

   480 // CPX_STAT_OPTIMAL_FACE_UNBOUNDED

   481 // CPX_STAT_OPTIMAL_INFEAS

   482 // CPX_STAT_OPTIMAL_RELAXED

   483 // CPX_STAT_UNBOUNDED

   485   LpCplex::SolutionStatus LpCplex::_getDualStatus()

   486   {

   487     int stat = CPXgetstat(env, lp);

   488 #if CPX_VERSION >= 900

   489     switch (stat)

   490     {

   491       case CPX_STAT_OPTIMAL:

   492         return OPTIMAL;

   493       case CPX_STAT_UNBOUNDED:

   494         return INFEASIBLE;

   495       default:

   496         return UNDEFINED;

   497     }

   498 #else

   499     statusSwitch(env,stat);

   500     switch (stat) {

   501     case 0:

   502       return UNDEFINED; //Undefined

   503     case CPX_OPTIMAL://Optimal

   504       return OPTIMAL;

   505     case CPX_UNBOUNDED:

   506      return INFEASIBLE;

   507     default:

   508       return UNDEFINED; //Everything else comes here

   509       //FIXME error

   510     }

   511 #endif

   512   }

   514   LpCplex::ProblemTypes LpCplex::_getProblemType()

   515   {

   516     int stat = CPXgetstat(env, lp);

   517 #if CPX_VERSION >= 900

   518     switch (stat)

   519     {

   520       case CPX_STAT_OPTIMAL:

   521 	return PRIMAL_DUAL_FEASIBLE;

   522       case CPX_STAT_UNBOUNDED:

   523  	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

   524       default:

   525         return UNKNOWN;

   526     }

   527 #else

   528     switch (stat) {

   529     case CPX_OPTIMAL://Optimal

   530 	return PRIMAL_DUAL_FEASIBLE;

   531     case CPX_UNBOUNDED:

   532  	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

   533 // 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;

   534 // 	return PRIMAL_DUAL_INFEASIBLE;

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

   537     default:

   538 	//In all other cases

   539 	return UNKNOWN;

   540       //FIXME error

   541     }

   542 #endif

   543   }

   545   void LpCplex::_setMax()

   546   {

   547     CPXchgobjsen(env, lp, CPX_MAX);

   548    }

   549   void LpCplex::_setMin()

   550   {

   551     CPXchgobjsen(env, lp, CPX_MIN);

   552    }

   554 } //namespace lemon

author	ladanyi
	Mon, 28 Aug 2006 15:43:17 +0000
changeset 2182	d8cea77af505
parent 1956	a055123339d5
child 2218	50f1a780a5ff
permissions	-rw-r--r--