lemon-0.x: lemon/lp_cplex.cc@99b1f7aec9d5

     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, LpRowIterator b, LpRowIterator e)

   113   {

   114     std::vector<int> indices;

   115     std::vector<int> rowlist;

   116     std::vector<Value> values;

   118     for(LpRowIterator it=b; it!=e; ++it) {

   119       indices.push_back(it->first);

   120       values.push_back(it->second);

   121       rowlist.push_back(i);

   122     }

   124     status = CPXchgcoeflist(env, lp, values.size(),

   125 			    &rowlist[0], &indices[0], &values[0]);

   126   }

   128   void LpCplex::_setColCoeffs(int i, LpColIterator b, LpColIterator e)

   129   {

   130     std::vector<int> indices;

   131     std::vector<int> collist;

   132     std::vector<Value> values;

   134     for(LpColIterator it=b; it!=e; ++it) {

   135       indices.push_back(it->first);

   136       values.push_back(it->second);

   137       collist.push_back(i);

   138     }

   140     status = CPXchgcoeflist(env, lp, values.size(),

   141 			    &indices[0], &collist[0], &values[0]);

   142   }

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

   145   {

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

   147   }

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

   150   {

   151     int indices[1];

   152     indices[0]=i;

   153     char lu[1];

   154     lu[0]='L';

   155     Value bd[1];

   156     bd[0]=value;

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

   159   }

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

   162   {

   163     int indices[1];

   164     indices[0]=i;

   165     char lu[1];

   166     lu[0]='U';

   167     Value bd[1];

   168     bd[0]=value;

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

   170   }

   172   //This will be easier to implement

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

   174   {

   175     //Bad parameter

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

   177       //FIXME error

   178     }

   180     int cnt=1;

   181     int indices[1];

   182     indices[0]=i;

   183     char sense[1];

   185     if (lb==-INF){

   186       sense[0]='L';

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

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

   190     }

   191     else{

   192       if (ub==INF){

   193 	sense[0]='G';

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

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

   196       }

   197       else{

   198 	if (lb == ub){

   199 	  sense[0]='E';

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

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

   202 	}

   203 	else{

   204 	  sense[0]='R';

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

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

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

   208 	}

   209       }

   210     }

   211   }

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

   214 //   {

   215 //     //Not implemented, obsolete

   216 //   }

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

   219 //   {

   220 //     //Not implemented, obsolete

   221 // //     //TODO Ezt kell meg megirni

   222 // //     //type of the problem

   223 // //     char sense[1];

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

   225 // //     Value rhs[1];

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

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

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

   230 // //       break;

   231 // //     case 'E'://= constraint

   232 // //       break;

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

   234 // //       break;

   235 // //     case 'R'://ranged constraint

   236 // //       break;

   237 // //     default: ;

   238 // //       //FIXME error

   239 // //     }

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

   242 //   }

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

   245   {

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

   247   }

   249   void LpCplex::_clearObj()

   250   {

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

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

   253     }

   255   }

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

   257   // optimization. Examples of errors include exhausting available

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

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

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

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

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

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

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

   265   LpCplex::SolveExitStatus LpCplex::_solve()

   266   {

   267     //CPX_PARAM_LPMETHOD

   268     status = CPXlpopt(env, lp);

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

   270 #if CPX_VERSION >= 800

   271     if (status)

   272     {

   273       return UNSOLVED;

   274     }

   275     else

   276     {

   277       switch (CPXgetstat(env, lp))

   278       {

   279         case CPX_STAT_OPTIMAL:

   280         case CPX_STAT_INFEASIBLE:

   281         case CPX_STAT_UNBOUNDED:

   282           return SOLVED;

   283         default:

   284           return UNSOLVED;

   285       }

   286     }

   287 #else

   288     if (status == 0){

   289       //We want to exclude some cases

   290       switch (CPXgetstat(env, lp)){

   291       case CPX_OBJ_LIM:

   292       case CPX_IT_LIM_FEAS:

   293       case CPX_IT_LIM_INFEAS:

   294       case CPX_TIME_LIM_FEAS:

   295       case CPX_TIME_LIM_INFEAS:

   296 	return UNSOLVED;

   297       default:

   298 	return SOLVED;

   299       }

   300     }

   301     else{

   302       return UNSOLVED;

   303     }

   304 #endif

   305   }

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

   308   {

   309     Value x;

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

   311     return x;

   312   }

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

   315   {

   316     Value y;

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

   318     return y;

   319   }

   321   LpCplex::Value LpCplex::_getPrimalValue()

   322   {

   323     Value objval;

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

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

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

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

   328     return objval;

   329   }

   330   bool LpCplex::_isBasicCol(int i) {

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

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

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

   334   }

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

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

   339 // For Simplex, Barrier

   340 // 1  	CPX_OPTIMAL

   341 // 	 Optimal solution found

   342 // 2  	CPX_INFEASIBLE

   343 // 	 Problem infeasible

   344 // 3    CPX_UNBOUNDED

   345 // 	 Problem unbounded

   346 // 4  	CPX_OBJ_LIM

   347 // 	 Objective limit exceeded in Phase II

   348 // 5  	CPX_IT_LIM_FEAS

   349 // 	 Iteration limit exceeded in Phase II

   350 // 6  	CPX_IT_LIM_INFEAS

   351 // 	 Iteration limit exceeded in Phase I

   352 // 7  	CPX_TIME_LIM_FEAS

   353 // 	 Time limit exceeded in Phase II

   354 // 8  	CPX_TIME_LIM_INFEAS

   355 // 	 Time limit exceeded in Phase I

   356 // 9  	CPX_NUM_BEST_FEAS

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

   358 // 10 	CPX_NUM_BEST_INFEAS

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

   360 // 11 	CPX_OPTIMAL_INFEAS

   361 // 	 Optimal solution found, unscaled infeasibilities

   362 // 12 	CPX_ABORT_FEAS

   363 // 	 Aborted in Phase II

   364 // 13 	CPX_ABORT_INFEAS

   365 // 	 Aborted in Phase I

   366 // 14  	CPX_ABORT_DUAL_INFEAS

   367 // 	 Aborted in barrier, dual infeasible

   368 // 15  	CPX_ABORT_PRIM_INFEAS

   369 // 	 Aborted in barrier, primal infeasible

   370 // 16  	CPX_ABORT_PRIM_DUAL_INFEAS

   371 // 	 Aborted in barrier, primal and dual infeasible

   372 // 17  	CPX_ABORT_PRIM_DUAL_FEAS

   373 // 	 Aborted in barrier, primal and dual feasible

   374 // 18  	CPX_ABORT_CROSSOVER

   375 // 	 Aborted in crossover

   376 // 19  	CPX_INForUNBD

   377 // 	 Infeasible or unbounded

   378 // 20   CPX_PIVOT

   379 //       User pivot used

   380 //

   381 //     Ezeket hova tegyem:

   382 // ??case CPX_ABORT_DUAL_INFEAS

   383 // ??case CPX_ABORT_CROSSOVER

   384 // ??case CPX_INForUNBD

   385 // ??case CPX_PIVOT

   387 //Some more interesting stuff:

   389 // CPX_PARAM_LPMETHOD  1062  int  LPMETHOD

   390 // 0 Automatic

   391 // 1 Primal Simplex

   392 // 2 Dual Simplex

   393 // 3 Network Simplex

   394 // 4 Standard Barrier

   395 // Default: 0

   396 // Description: Method for linear optimization.

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

   398   //Hulye cplex

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

   400 #if CPX_VERSION < 900

   401     int lpmethod;

   402     CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);

   403     if (lpmethod==2){

   404       if (stat==CPX_UNBOUNDED){

   405 	stat=CPX_INFEASIBLE;

   406       }

   407       else{

   408 	if (stat==CPX_INFEASIBLE)

   409 	  stat=CPX_UNBOUNDED;

   410       }

   411     }

   412 #endif

   413   }

   415   LpCplex::SolutionStatus LpCplex::_getPrimalStatus()

   416   {

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

   418     // About Unboundedness

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

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

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

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

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

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

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

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

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

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

   430     // has a feasible solution.

   432     int stat = CPXgetstat(env, lp);

   433 #if CPX_VERSION >= 800

   434     switch (stat)

   435     {

   436       case CPX_STAT_OPTIMAL:

   437         return OPTIMAL;

   438       case CPX_STAT_UNBOUNDED:

   439         return INFINITE;

   440       case CPX_STAT_INFEASIBLE:

   441         return INFEASIBLE;

   442       default:

   443         return UNDEFINED;

   444     }

   445 #else

   446     statusSwitch(env,stat);

   447     //CPXgetstat(env, lp);

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

   449     switch (stat) {

   450     case 0:

   451       return UNDEFINED; //Undefined

   452     case CPX_OPTIMAL://Optimal

   453       return OPTIMAL;

   454     case CPX_UNBOUNDED://Unbounded

   455       return INFEASIBLE;//In case of dual simplex

   456       //return INFINITE;

   457     case CPX_INFEASIBLE://Infeasible

   458  //    case CPX_IT_LIM_INFEAS:

   459 //     case CPX_TIME_LIM_INFEAS:

   460 //     case CPX_NUM_BEST_INFEAS:

   461 //     case CPX_OPTIMAL_INFEAS:

   462 //     case CPX_ABORT_INFEAS:

   463 //     case CPX_ABORT_PRIM_INFEAS:

   464 //     case CPX_ABORT_PRIM_DUAL_INFEAS:

   465       return INFINITE;//In case of dual simplex

   466       //return INFEASIBLE;

   467 //     case CPX_OBJ_LIM:

   468 //     case CPX_IT_LIM_FEAS:

   469 //     case CPX_TIME_LIM_FEAS:

   470 //     case CPX_NUM_BEST_FEAS:

   471 //     case CPX_ABORT_FEAS:

   472 //     case CPX_ABORT_PRIM_DUAL_FEAS:

   473 //       return FEASIBLE;

   474     default:

   475       return UNDEFINED; //Everything else comes here

   476       //FIXME error

   477     }

   478 #endif

   479   }

   481 //9.0-as cplex verzio statusai

   482 // CPX_STAT_ABORT_DUAL_OBJ_LIM

   483 // CPX_STAT_ABORT_IT_LIM

   484 // CPX_STAT_ABORT_OBJ_LIM

   485 // CPX_STAT_ABORT_PRIM_OBJ_LIM

   486 // CPX_STAT_ABORT_TIME_LIM

   487 // CPX_STAT_ABORT_USER

   488 // CPX_STAT_FEASIBLE_RELAXED

   489 // CPX_STAT_INFEASIBLE

   490 // CPX_STAT_INForUNBD

   491 // CPX_STAT_NUM_BEST

   492 // CPX_STAT_OPTIMAL

   493 // CPX_STAT_OPTIMAL_FACE_UNBOUNDED

   494 // CPX_STAT_OPTIMAL_INFEAS

   495 // CPX_STAT_OPTIMAL_RELAXED

   496 // CPX_STAT_UNBOUNDED

   498   LpCplex::SolutionStatus LpCplex::_getDualStatus()

   499   {

   500     int stat = CPXgetstat(env, lp);

   501 #if CPX_VERSION >= 800

   502     switch (stat)

   503     {

   504       case CPX_STAT_OPTIMAL:

   505         return OPTIMAL;

   506       case CPX_STAT_UNBOUNDED:

   507         return INFEASIBLE;

   508       default:

   509         return UNDEFINED;

   510     }

   511 #else

   512     statusSwitch(env,stat);

   513     switch (stat) {

   514     case 0:

   515       return UNDEFINED; //Undefined

   516     case CPX_OPTIMAL://Optimal

   517       return OPTIMAL;

   518     case CPX_UNBOUNDED:

   519      return INFEASIBLE;

   520     default:

   521       return UNDEFINED; //Everything else comes here

   522       //FIXME error

   523     }

   524 #endif

   525   }

   527   LpCplex::ProblemTypes LpCplex::_getProblemType()

   528   {

   529     int stat = CPXgetstat(env, lp);

   530 #if CPX_VERSION >= 800

   531     switch (stat)

   532     {

   533       case CPX_STAT_OPTIMAL:

   534 	return PRIMAL_DUAL_FEASIBLE;

   535       case CPX_STAT_UNBOUNDED:

   536  	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

   537       default:

   538         return UNKNOWN;

   539     }

   540 #else

   541     switch (stat) {

   542     case CPX_OPTIMAL://Optimal

   543 	return PRIMAL_DUAL_FEASIBLE;

   544     case CPX_UNBOUNDED:

   545  	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

   546 // 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;

   547 // 	return PRIMAL_DUAL_INFEASIBLE;

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

   550     default:

   551 	//In all other cases

   552 	return UNKNOWN;

   553       //FIXME error

   554     }

   555 #endif

   556   }

   558   void LpCplex::_setMax()

   559   {

   560     CPXchgobjsen(env, lp, CPX_MAX);

   561    }

   562   void LpCplex::_setMin()

   563   {

   564     CPXchgobjsen(env, lp, CPX_MIN);

   565    }

   567 } //namespace lemon

author	alpar
	Thu, 30 Nov 2006 14:42:18 +0000
changeset 2319	99b1f7aec9d5
parent 2218	50f1a780a5ff
child 2328	b4931ae52069
permissions	-rw-r--r--