lemon-0.x: lemon/lp_cplex.cc@914602e294be

     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 (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   }

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

   291   {

   292     Value x;

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

   294     return x;

   295   }

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

   298   {

   299     Value y;

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

   301     return y;

   302   }

   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   }

   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.

   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

   370 //Some more interesting stuff:

   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   }

   396   LpCplex::SolutionStatus LpCplex::_getPrimalStatus()

   397   {

   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     }

   433   }

   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

   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   }

   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;

   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   }

   488   void LpCplex::_setMax()

   489   {

   490     CPXchgobjsen(env, lp, CPX_MAX);

   491    }

   492   void LpCplex::_setMin()

   493   {

   494     CPXchgobjsen(env, lp, CPX_MIN);

   495    }

   497 } //namespace lemon

author	alpar
	Wed, 12 Jul 2006 11:14:12 +0000
changeset 2134	914602e294be
parent 1950	a1a6f5b788bd
child 2168	6474b8254f24
permissions	-rw-r--r--