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

     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>

    19 ///\file

    20 ///\brief Implementation of the LEMON-CPLEX lp solver interface.

    21 namespace lemon {

    23   LpCplex::LpCplex() : LpSolverBase() {

    25     //    env = CPXopenCPLEXdevelop(&status);

    26     env = CPXopenCPLEX(&status);

    27     lp = CPXcreateprob(env, &status, "LP problem");

    28   }

    30   LpCplex::~LpCplex() {

    31     CPXfreeprob(env,&lp);

    32     CPXcloseCPLEX(&env);

    33   }

    35   LpSolverBase &LpCplex::_newLp()

    36   {

    37     //The first approach opens a new environment

    38     LpCplex* newlp=new LpCplex();

    39     return *newlp;

    40   }

    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   }

    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   }

    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   }

    76   void LpCplex::_eraseCol(int i) {

    77     CPXdelcols(env, lp, i, i);

    78   }

    80   void LpCplex::_eraseRow(int i) {

    81     CPXdelrows(env, lp, i, i);

    82   }

    84   void LpCplex::_getColName(int col, std::string &name)

    85   {

    86     ///\bug Untested

    87     int storespace;

    88     CPXgetcolname(env, lp, 0, 0, 0, &storespace, col, col);

    90     storespace *= -1;

    91     char buf[storespace];

    92     char *names[1];

    93     int dontcare;

    94     ///\bug return code unchecked for error

    95     CPXgetcolname(env, lp, names, buf, storespace, &dontcare, col, col);

    96     name = names[0];

    97   }

    99   void LpCplex::_setColName(int col, const std::string &name)

   100   {

   101     ///\bug Untested

   102     char *names[1];

   103     names[0] = const_cast<char*>(name.c_str());

   104     ///\bug return code unchecked for error

   105     CPXchgcolname(env, lp, 1, &col, names);

   106   }

   108   ///\warning Data at index 0 is ignored in the arrays.

   109   void LpCplex::_setRowCoeffs(int i,

   110 			      int length,

   111 			      int  const * indices,

   112 			      Value  const * values )

   113   {

   114     int rowlist[length+1];

   115     int* p=rowlist;

   116     for (int k=1;k<=length;++k){

   117       rowlist[k]=i;

   118     }

   119     status = CPXchgcoeflist(env, lp,

   120 			    length,

   121 			    p+1,

   122 			    const_cast<int * >(indices+1),

   123 			    const_cast<Value * >(values+1));

   124   }

   126   void LpCplex::_setColCoeffs(int i,

   127 			      int length,

   128 			      int  const * indices,

   129 			      Value  const * values)

   130   {

   131     int collist[length+1];

   132     int* p=collist;

   133     for (int k=1;k<=length;++k){

   134       collist[k]=i;

   135     }

   136     status = CPXchgcoeflist(env, lp,

   137 			    length,

   138 			    const_cast<int * >(indices+1),

   139 			    p+1,

   140 			    const_cast<Value * >(values+1));

   141   }

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

   144   {

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

   146   }

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

   149   {

   150     int indices[1];

   151     indices[0]=i;

   152     char lu[1];

   153     lu[0]='L';

   154     Value bd[1];

   155     bd[0]=value;

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

   158   }

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

   161   {

   162     int indices[1];

   163     indices[0]=i;

   164     char lu[1];

   165     lu[0]='U';

   166     Value bd[1];

   167     bd[0]=value;

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

   169   }

   171   //This will be easier to implement

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

   173   {

   174     //Bad parameter

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

   176       //FIXME error

   177     }

   179     int cnt=1;

   180     int indices[1];

   181     indices[0]=i;

   182     char sense[1];

   184     if (lb==-INF){

   185       sense[0]='L';

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

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

   189     }

   190     else{

   191       if (ub==INF){

   192 	sense[0]='G';

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

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

   195       }

   196       else{

   197 	if (lb == ub){

   198 	  sense[0]='E';

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

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

   201 	}

   202 	else{

   203 	  sense[0]='R';

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

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

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

   207 	}

   208       }

   209     }

   210   }

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

   213 //   {

   214 //     //Not implemented, obsolete

   215 //   }

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

   218 //   {

   219 //     //Not implemented, obsolete

   220 // //     //TODO Ezt kell meg megirni

   221 // //     //type of the problem

   222 // //     char sense[1];

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

   224 // //     Value rhs[1];

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

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

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

   229 // //       break;

   230 // //     case 'E'://= constraint

   231 // //       break;

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

   233 // //       break;

   234 // //     case 'R'://ranged constraint

   235 // //       break;

   236 // //     default: ;

   237 // //       //FIXME error

   238 // //     }

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

   241 //   }

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

   244   {

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

   246   }

   248   void LpCplex::_clearObj()

   249   {

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

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

   252     }

   254   }

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

   256   // optimization. Examples of errors include exhausting available

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

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

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

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

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

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

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

   264   LpCplex::SolveExitStatus LpCplex::_solve()

   265   {

   266     //CPX_PARAM_LPMETHOD

   267     status = CPXlpopt(env, lp);

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

   269     if (status == 0){

   270       //We want to exclude some cases

   271       switch (CPXgetstat(env, lp)){

   272       case CPX_OBJ_LIM:

   273       case CPX_IT_LIM_FEAS:

   274       case CPX_IT_LIM_INFEAS:

   275       case CPX_TIME_LIM_FEAS:

   276       case CPX_TIME_LIM_INFEAS:

   277 	return UNSOLVED;

   278       default:

   279 	return SOLVED;

   280       }

   281     }

   282     else{

   283       return UNSOLVED;

   284     }

   285   }

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

   288   {

   289     Value x;

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

   291     return x;

   292   }

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

   295   {

   296     Value y;

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

   298     return y;

   299   }

   301   LpCplex::Value LpCplex::_getPrimalValue()

   302   {

   303     Value objval;

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

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

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

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

   308     return objval;

   309   }

   310   bool LpCplex::_isBasicCol(int i) {

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

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

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

   314   }

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

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

   319 // For Simplex, Barrier

   320 // 1  	CPX_OPTIMAL

   321 // 	 Optimal solution found

   322 // 2  	CPX_INFEASIBLE

   323 // 	 Problem infeasible

   324 // 3    CPX_UNBOUNDED

   325 // 	 Problem unbounded

   326 // 4  	CPX_OBJ_LIM

   327 // 	 Objective limit exceeded in Phase II

   328 // 5  	CPX_IT_LIM_FEAS

   329 // 	 Iteration limit exceeded in Phase II

   330 // 6  	CPX_IT_LIM_INFEAS

   331 // 	 Iteration limit exceeded in Phase I

   332 // 7  	CPX_TIME_LIM_FEAS

   333 // 	 Time limit exceeded in Phase II

   334 // 8  	CPX_TIME_LIM_INFEAS

   335 // 	 Time limit exceeded in Phase I

   336 // 9  	CPX_NUM_BEST_FEAS

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

   338 // 10 	CPX_NUM_BEST_INFEAS

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

   340 // 11 	CPX_OPTIMAL_INFEAS

   341 // 	 Optimal solution found, unscaled infeasibilities

   342 // 12 	CPX_ABORT_FEAS

   343 // 	 Aborted in Phase II

   344 // 13 	CPX_ABORT_INFEAS

   345 // 	 Aborted in Phase I

   346 // 14  	CPX_ABORT_DUAL_INFEAS

   347 // 	 Aborted in barrier, dual infeasible

   348 // 15  	CPX_ABORT_PRIM_INFEAS

   349 // 	 Aborted in barrier, primal infeasible

   350 // 16  	CPX_ABORT_PRIM_DUAL_INFEAS

   351 // 	 Aborted in barrier, primal and dual infeasible

   352 // 17  	CPX_ABORT_PRIM_DUAL_FEAS

   353 // 	 Aborted in barrier, primal and dual feasible

   354 // 18  	CPX_ABORT_CROSSOVER

   355 // 	 Aborted in crossover

   356 // 19  	CPX_INForUNBD

   357 // 	 Infeasible or unbounded

   358 // 20   CPX_PIVOT

   359 //       User pivot used

   360 //

   361 //     Ezeket hova tegyem:

   362 // ??case CPX_ABORT_DUAL_INFEAS

   363 // ??case CPX_ABORT_CROSSOVER

   364 // ??case CPX_INForUNBD

   365 // ??case CPX_PIVOT

   367 //Some more interesting stuff:

   369 // CPX_PARAM_LPMETHOD  1062  int  LPMETHOD

   370 // 0 Automatic

   371 // 1 Primal Simplex

   372 // 2 Dual Simplex

   373 // 3 Network Simplex

   374 // 4 Standard Barrier

   375 // Default: 0

   376 // Description: Method for linear optimization.

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

   378   //Hulye cplex

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

   380     int lpmethod;

   381     CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);

   382     if (lpmethod==2){

   383       if (stat==CPX_UNBOUNDED){

   384 	stat=CPX_INFEASIBLE;

   385       }

   386       else{

   387 	if (stat==CPX_INFEASIBLE)

   388 	  stat=CPX_UNBOUNDED;

   389       }

   390     }

   391   }

   393   LpCplex::SolutionStatus LpCplex::_getPrimalStatus()

   394   {

   396     int stat = CPXgetstat(env, lp);

   397     statusSwitch(env,stat);

   398     //CPXgetstat(env, lp);

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

   400     switch (stat) {

   401     case 0:

   402       return UNDEFINED; //Undefined

   403     case CPX_OPTIMAL://Optimal

   404       return OPTIMAL;

   405     case CPX_UNBOUNDED://Unbounded

   406       return INFEASIBLE;//In case of dual simplex

   407       //return INFINITE;

   408     case CPX_INFEASIBLE://Infeasible

   409  //    case CPX_IT_LIM_INFEAS:

   410 //     case CPX_TIME_LIM_INFEAS:

   411 //     case CPX_NUM_BEST_INFEAS:

   412 //     case CPX_OPTIMAL_INFEAS:

   413 //     case CPX_ABORT_INFEAS:

   414 //     case CPX_ABORT_PRIM_INFEAS:

   415 //     case CPX_ABORT_PRIM_DUAL_INFEAS:

   416       return INFINITE;//In case of dual simplex

   417       //return INFEASIBLE;

   418 //     case CPX_OBJ_LIM:

   419 //     case CPX_IT_LIM_FEAS:

   420 //     case CPX_TIME_LIM_FEAS:

   421 //     case CPX_NUM_BEST_FEAS:

   422 //     case CPX_ABORT_FEAS:

   423 //     case CPX_ABORT_PRIM_DUAL_FEAS:

   424 //       return FEASIBLE;

   425     default:

   426       return UNDEFINED; //Everything else comes here

   427       //FIXME error

   428     }

   430   }

   432 //9.0-as cplex verzio statusai

   433 // CPX_STAT_ABORT_DUAL_OBJ_LIM

   434 // CPX_STAT_ABORT_IT_LIM

   435 // CPX_STAT_ABORT_OBJ_LIM

   436 // CPX_STAT_ABORT_PRIM_OBJ_LIM

   437 // CPX_STAT_ABORT_TIME_LIM

   438 // CPX_STAT_ABORT_USER

   439 // CPX_STAT_FEASIBLE_RELAXED

   440 // CPX_STAT_INFEASIBLE

   441 // CPX_STAT_INForUNBD

   442 // CPX_STAT_NUM_BEST

   443 // CPX_STAT_OPTIMAL

   444 // CPX_STAT_OPTIMAL_FACE_UNBOUNDED

   445 // CPX_STAT_OPTIMAL_INFEAS

   446 // CPX_STAT_OPTIMAL_RELAXED

   447 // CPX_STAT_UNBOUNDED

   449   LpCplex::SolutionStatus LpCplex::_getDualStatus()

   450   {

   451     int stat = CPXgetstat(env, lp);

   452     statusSwitch(env,stat);

   453     switch (stat) {

   454     case 0:

   455       return UNDEFINED; //Undefined

   456     case CPX_OPTIMAL://Optimal

   457       return OPTIMAL;

   458     case CPX_UNBOUNDED:

   459      return INFEASIBLE;

   460     default:

   461       return UNDEFINED; //Everything else comes here

   462       //FIXME error

   463     }

   464   }

   466   LpCplex::ProblemTypes LpCplex::_getProblemType()

   467   {

   468     int stat = CPXgetstat(env, lp);

   469     switch (stat) {

   470     case CPX_OPTIMAL://Optimal

   471 	return PRIMAL_DUAL_FEASIBLE;

   472     case CPX_UNBOUNDED:

   473  	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

   474 // 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;

   475 // 	return PRIMAL_DUAL_INFEASIBLE;

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

   478     default:

   479 	//In all other cases

   480 	return UNKNOWN;

   481       //FIXME error

   482     }

   483   }

   485   void LpCplex::_setMax()

   486   {

   487     CPXchgobjsen(env, lp, CPX_MAX);

   488    }

   489   void LpCplex::_setMin()

   490   {

   491     CPXchgobjsen(env, lp, CPX_MIN);

   492    }

   494 } //namespace lemon

author	alpar
	Fri, 03 Feb 2006 15:58:24 +0000
changeset 1953	d4f411003580
parent 1895	5b01801efbc0
child 1956	a055123339d5
permissions	-rw-r--r--