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

     1 /* -*- C++ -*-

     2  * lemon/lp_cplex.cc - Part of LEMON, a generic C++ optimization library

     3  *

     4  * Copyright (C) 2005 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   }

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

    86   void LpCplex::_setRowCoeffs(int i,

    87 			      int length,

    88 			      int  const * indices,

    89 			      Value  const * values )

    90   {

    91     int rowlist[length+1];

    92     int* p=rowlist;

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

    94       rowlist[k]=i;

    95     }

    96     status = CPXchgcoeflist(env, lp,

    97 			    length,

    98 			    p+1,

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

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

   101   }

   103   void LpCplex::_setColCoeffs(int i,

   104 			      int length,

   105 			      int  const * indices,

   106 			      Value  const * values)

   107   {

   108     int collist[length+1];

   109     int* p=collist;

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

   111       collist[k]=i;

   112     }

   113     status = CPXchgcoeflist(env, lp,

   114 			    length,

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

   116 			    p+1,

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

   118   }

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

   121   {

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

   123   }

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

   126   {

   127     int indices[1];

   128     indices[0]=i;

   129     char lu[1];

   130     lu[0]='L';

   131     Value bd[1];

   132     bd[0]=value;

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

   135   }

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

   138   {

   139     int indices[1];

   140     indices[0]=i;

   141     char lu[1];

   142     lu[0]='U';

   143     Value bd[1];

   144     bd[0]=value;

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

   146   }

   148   //This will be easier to implement

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

   150   {

   151     //Bad parameter

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

   153       //FIXME error

   154     }

   156     int cnt=1;

   157     int indices[1];

   158     indices[0]=i;

   159     char sense[1];

   161     if (lb==-INF){

   162       sense[0]='L';

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

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

   166     }

   167     else{

   168       if (ub==INF){

   169 	sense[0]='G';

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

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

   172       }

   173       else{

   174 	if (lb == ub){

   175 	  sense[0]='E';

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

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

   178 	}

   179 	else{

   180 	  sense[0]='R';

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

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

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

   184 	}

   185       }

   186     }

   187   }

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

   190 //   {

   191 //     //Not implemented, obsolete

   192 //   }

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

   195 //   {

   196 //     //Not implemented, obsolete

   197 // //     //TODO Ezt kell meg megirni

   198 // //     //type of the problem

   199 // //     char sense[1];

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

   201 // //     Value rhs[1];

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

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

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

   206 // //       break;

   207 // //     case 'E'://= constraint

   208 // //       break;

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

   210 // //       break;

   211 // //     case 'R'://ranged constraint

   212 // //       break;

   213 // //     default: ;

   214 // //       //FIXME error

   215 // //     }

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

   218 //   }

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

   221   {

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

   223   }

   225   void LpCplex::_clearObj()

   226   {

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

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

   229     }

   231   }

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

   233   // optimization. Examples of errors include exhausting available

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

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

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

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

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

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

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

   241   LpCplex::SolveExitStatus LpCplex::_solve()

   242   {

   243     //CPX_PARAM_LPMETHOD

   244     status = CPXlpopt(env, lp);

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

   246     if (status == 0){

   247       //We want to exclude some cases

   248       switch (CPXgetstat(env, lp)){

   249       case CPX_OBJ_LIM:

   250       case CPX_IT_LIM_FEAS:

   251       case CPX_IT_LIM_INFEAS:

   252       case CPX_TIME_LIM_FEAS:

   253       case CPX_TIME_LIM_INFEAS:

   254 	return UNSOLVED;

   255       default:

   256 	return SOLVED;

   257       }

   258     }

   259     else{

   260       return UNSOLVED;

   261     }

   262   }

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

   265   {

   266     Value x;

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

   268     return x;

   269   }

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

   272   {

   273     Value y;

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

   275     return y;

   276   }

   278   LpCplex::Value LpCplex::_getPrimalValue()

   279   {

   280     Value objval;

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

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

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

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

   285     return objval;

   286   }

   287   bool LpCplex::_isBasicCol(int i) {

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

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

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

   291   }

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

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

   296 // For Simplex, Barrier

   297 // 1  	CPX_OPTIMAL

   298 // 	 Optimal solution found

   299 // 2  	CPX_INFEASIBLE

   300 // 	 Problem infeasible

   301 // 3    CPX_UNBOUNDED

   302 // 	 Problem unbounded

   303 // 4  	CPX_OBJ_LIM

   304 // 	 Objective limit exceeded in Phase II

   305 // 5  	CPX_IT_LIM_FEAS

   306 // 	 Iteration limit exceeded in Phase II

   307 // 6  	CPX_IT_LIM_INFEAS

   308 // 	 Iteration limit exceeded in Phase I

   309 // 7  	CPX_TIME_LIM_FEAS

   310 // 	 Time limit exceeded in Phase II

   311 // 8  	CPX_TIME_LIM_INFEAS

   312 // 	 Time limit exceeded in Phase I

   313 // 9  	CPX_NUM_BEST_FEAS

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

   315 // 10 	CPX_NUM_BEST_INFEAS

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

   317 // 11 	CPX_OPTIMAL_INFEAS

   318 // 	 Optimal solution found, unscaled infeasibilities

   319 // 12 	CPX_ABORT_FEAS

   320 // 	 Aborted in Phase II

   321 // 13 	CPX_ABORT_INFEAS

   322 // 	 Aborted in Phase I

   323 // 14  	CPX_ABORT_DUAL_INFEAS

   324 // 	 Aborted in barrier, dual infeasible

   325 // 15  	CPX_ABORT_PRIM_INFEAS

   326 // 	 Aborted in barrier, primal infeasible

   327 // 16  	CPX_ABORT_PRIM_DUAL_INFEAS

   328 // 	 Aborted in barrier, primal and dual infeasible

   329 // 17  	CPX_ABORT_PRIM_DUAL_FEAS

   330 // 	 Aborted in barrier, primal and dual feasible

   331 // 18  	CPX_ABORT_CROSSOVER

   332 // 	 Aborted in crossover

   333 // 19  	CPX_INForUNBD

   334 // 	 Infeasible or unbounded

   335 // 20   CPX_PIVOT

   336 //       User pivot used

   337 //

   338 //     Ezeket hova tegyem:

   339 // ??case CPX_ABORT_DUAL_INFEAS

   340 // ??case CPX_ABORT_CROSSOVER

   341 // ??case CPX_INForUNBD

   342 // ??case CPX_PIVOT

   344 //Some more interesting stuff:

   346 // CPX_PARAM_LPMETHOD  1062  int  LPMETHOD

   347 // 0 Automatic

   348 // 1 Primal Simplex

   349 // 2 Dual Simplex

   350 // 3 Network Simplex

   351 // 4 Standard Barrier

   352 // Default: 0

   353 // Description: Method for linear optimization.

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

   355   //Hulye cplex

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

   357     int lpmethod;

   358     CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);

   359     if (lpmethod==2){

   360       if (stat==CPX_UNBOUNDED){

   361 	stat=CPX_INFEASIBLE;

   362       }

   363       else{

   364 	if (stat==CPX_INFEASIBLE)

   365 	  stat=CPX_UNBOUNDED;

   366       }

   367     }

   368   }

   370   LpCplex::SolutionStatus LpCplex::_getPrimalStatus()

   371   {

   373     int stat = CPXgetstat(env, lp);

   374     statusSwitch(env,stat);

   375     //CPXgetstat(env, lp);

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

   377     switch (stat) {

   378     case 0:

   379       return UNDEFINED; //Undefined

   380     case CPX_OPTIMAL://Optimal

   381       return OPTIMAL;

   382     case CPX_UNBOUNDED://Unbounded

   383       return INFEASIBLE;//In case of dual simplex

   384       //return INFINITE;

   385     case CPX_INFEASIBLE://Infeasible

   386  //    case CPX_IT_LIM_INFEAS:

   387 //     case CPX_TIME_LIM_INFEAS:

   388 //     case CPX_NUM_BEST_INFEAS:

   389 //     case CPX_OPTIMAL_INFEAS:

   390 //     case CPX_ABORT_INFEAS:

   391 //     case CPX_ABORT_PRIM_INFEAS:

   392 //     case CPX_ABORT_PRIM_DUAL_INFEAS:

   393       return INFINITE;//In case of dual simplex

   394       //return INFEASIBLE;

   395 //     case CPX_OBJ_LIM:

   396 //     case CPX_IT_LIM_FEAS:

   397 //     case CPX_TIME_LIM_FEAS:

   398 //     case CPX_NUM_BEST_FEAS:

   399 //     case CPX_ABORT_FEAS:

   400 //     case CPX_ABORT_PRIM_DUAL_FEAS:

   401 //       return FEASIBLE;

   402     default:

   403       return UNDEFINED; //Everything else comes here

   404       //FIXME error

   405     }

   407   }

   409 //9.0-as cplex verzio statusai

   410 // CPX_STAT_ABORT_DUAL_OBJ_LIM

   411 // CPX_STAT_ABORT_IT_LIM

   412 // CPX_STAT_ABORT_OBJ_LIM

   413 // CPX_STAT_ABORT_PRIM_OBJ_LIM

   414 // CPX_STAT_ABORT_TIME_LIM

   415 // CPX_STAT_ABORT_USER

   416 // CPX_STAT_FEASIBLE_RELAXED

   417 // CPX_STAT_INFEASIBLE

   418 // CPX_STAT_INForUNBD

   419 // CPX_STAT_NUM_BEST

   420 // CPX_STAT_OPTIMAL

   421 // CPX_STAT_OPTIMAL_FACE_UNBOUNDED

   422 // CPX_STAT_OPTIMAL_INFEAS

   423 // CPX_STAT_OPTIMAL_RELAXED

   424 // CPX_STAT_UNBOUNDED

   426   LpCplex::SolutionStatus LpCplex::_getDualStatus()

   427   {

   428     int stat = CPXgetstat(env, lp);

   429     statusSwitch(env,stat);

   430     switch (stat) {

   431     case 0:

   432       return UNDEFINED; //Undefined

   433     case CPX_OPTIMAL://Optimal

   434       return OPTIMAL;

   435     case CPX_UNBOUNDED:

   436      return INFEASIBLE;

   437     default:

   438       return UNDEFINED; //Everything else comes here

   439       //FIXME error

   440     }

   441   }

   443   LpCplex::ProblemTypes LpCplex::_getProblemType()

   444   {

   445     int stat = CPXgetstat(env, lp);

   446     switch (stat) {

   447     case CPX_OPTIMAL://Optimal

   448 	return PRIMAL_DUAL_FEASIBLE;

   449     case CPX_UNBOUNDED:

   450  	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

   451 // 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;

   452 // 	return PRIMAL_DUAL_INFEASIBLE;

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

   455     default:

   456 	//In all other cases

   457 	return UNKNOWN;

   458       //FIXME error

   459     }

   460   }

   462   void LpCplex::_setMax()

   463   {

   464     CPXchgobjsen(env, lp, CPX_MAX);

   465    }

   466   void LpCplex::_setMin()

   467   {

   468     CPXchgobjsen(env, lp, CPX_MIN);

   469    }

   471 } //namespace lemon

author	alpar
	Wed, 07 Dec 2005 15:39:48 +0000
changeset 1853	dd0b47adc152
parent 1840	173b53b28d7c
child 1875	98698b69a902
permissions	-rw-r--r--