COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_cplex.cc @ 2218:50f1a780a5ff

Last change on this file since 2218:50f1a780a5ff was 2218:50f1a780a5ff, checked in by athos, 13 years ago

Interface to the cplex MIP solver: it is little, a bit sour but it is ours.

File size: 14.8 KB
Line 
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 */
18
19#include <iostream>
20#include<lemon/lp_cplex.h>
21
22///\file
23///\brief Implementation of the LEMON-CPLEX lp solver interface.
24namespace lemon {
25 
26  LpCplex::LpCplex() : LpSolverBase() {
27
28    //    env = CPXopenCPLEXdevelop(&status);     
29    env = CPXopenCPLEX(&status);     
30    lp = CPXcreateprob(env, &status, "LP problem");
31  }
32 
33  LpCplex::~LpCplex() {
34    CPXfreeprob(env,&lp);
35    CPXcloseCPLEX(&env);
36  }
37 
38  LpSolverBase &LpCplex::_newLp()
39  {
40    //The first approach opens a new environment
41    LpCplex* newlp=new LpCplex();
42    return *newlp;
43  }
44
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  }
54
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  }
64
65 
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  }
77
78
79  void LpCplex::_eraseCol(int i) {
80    CPXdelcols(env, lp, i, i);
81  }
82 
83  void LpCplex::_eraseRow(int i) {
84    CPXdelrows(env, lp, i, i);
85  }
86 
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);
92
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  }
101 
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  }
110 
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  }
128 
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  }
145 
146  void LpCplex::_setCoeff(int row, int col, Value value)
147  {
148    CPXchgcoef(env, lp, row, col, value);
149  }
150
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);
160 
161  }
162 
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  }
173
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    }
181   
182    int cnt=1;
183    int indices[1];
184    indices[0]=i;
185    char sense[1];
186
187    if (lb==-INF){
188      sense[0]='L';
189      CPXchgsense(env, lp, cnt, indices, sense);
190      CPXchgcoef(env, lp, i, -1, ub);
191     
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  }
214
215//   void LpCplex::_setRowLowerBound(int i, Value value)
216//   {
217//     //Not implemented, obsolete
218//   }
219 
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);
229
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// //     }
242
243// //     status = CPXchgcoef(env, lp, i, -2, value_rng);
244//   }
245 
246  void LpCplex::_setObjCoeff(int i, Value obj_coef)
247  {
248    CPXchgcoef(env, lp, -1, i, obj_coef);
249  }
250
251  void LpCplex::_clearObj()
252  {
253    for (int i=0;i< CPXgetnumcols(env, lp);++i){
254      CPXchgcoef(env, lp, -1, i, 0);
255    }
256   
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 >= 800
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  }
308
309  LpCplex::Value LpCplex::_getPrimal(int i)
310  {
311    Value x;
312    CPXgetx(env, lp, &x, i, i);
313    return x;
314  }
315
316  LpCplex::Value LpCplex::_getDual(int i)
317  {
318    Value y;
319    CPXgetpi(env, lp, &y, i, i);
320    return y;
321  }
322 
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  } 
337
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.
340
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             
388         
389//Some more interesting stuff:
390
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  }
416
417  LpCplex::SolutionStatus LpCplex::_getPrimalStatus()
418  {
419    //Unboundedness not treated well: the following is from cplex 9.0 doc
420    // About Unboundedness
421
422    // The treatment of models that are unbounded involves a few
423    // subtleties. Specifically, a declaration of unboundedness means that
424    // ILOG CPLEX has determined that the model has an unbounded
425    // ray. Given any feasible solution x with objective z, a multiple of
426    // the unbounded ray can be added to x to give a feasible solution
427    // with objective z-1 (or z+1 for maximization models). Thus, if a
428    // feasible solution exists, then the optimal objective is
429    // unbounded. Note that ILOG CPLEX has not necessarily concluded that
430    // a feasible solution exists. Users can call the routine CPXsolninfo
431    // to determine whether ILOG CPLEX has also concluded that the model
432    // has a feasible solution.
433
434    int stat = CPXgetstat(env, lp);
435#if CPX_VERSION >= 800
436    switch (stat)
437    {
438      case CPX_STAT_OPTIMAL:
439        return OPTIMAL;
440      case CPX_STAT_UNBOUNDED:
441        return INFINITE;
442      case CPX_STAT_INFEASIBLE:
443        return INFEASIBLE;
444      default:
445        return UNDEFINED;
446    }
447#else
448    statusSwitch(env,stat);
449    //CPXgetstat(env, lp);
450    //printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL);
451    switch (stat) {
452    case 0:
453      return UNDEFINED; //Undefined
454    case CPX_OPTIMAL://Optimal
455      return OPTIMAL;
456    case CPX_UNBOUNDED://Unbounded
457      return INFEASIBLE;//In case of dual simplex
458      //return INFINITE;
459    case CPX_INFEASIBLE://Infeasible
460 //    case CPX_IT_LIM_INFEAS:
461//     case CPX_TIME_LIM_INFEAS:
462//     case CPX_NUM_BEST_INFEAS:             
463//     case CPX_OPTIMAL_INFEAS:             
464//     case CPX_ABORT_INFEAS:               
465//     case CPX_ABORT_PRIM_INFEAS:           
466//     case CPX_ABORT_PRIM_DUAL_INFEAS:     
467      return INFINITE;//In case of dual simplex
468      //return INFEASIBLE;
469//     case CPX_OBJ_LIM:                   
470//     case CPX_IT_LIM_FEAS:             
471//     case CPX_TIME_LIM_FEAS:               
472//     case CPX_NUM_BEST_FEAS:               
473//     case CPX_ABORT_FEAS:                 
474//     case CPX_ABORT_PRIM_DUAL_FEAS:       
475//       return FEASIBLE;
476    default:
477      return UNDEFINED; //Everything else comes here
478      //FIXME error
479    }
480#endif
481  }
482
483//9.0-as cplex verzio statusai
484// CPX_STAT_ABORT_DUAL_OBJ_LIM
485// CPX_STAT_ABORT_IT_LIM
486// CPX_STAT_ABORT_OBJ_LIM
487// CPX_STAT_ABORT_PRIM_OBJ_LIM
488// CPX_STAT_ABORT_TIME_LIM
489// CPX_STAT_ABORT_USER
490// CPX_STAT_FEASIBLE_RELAXED
491// CPX_STAT_INFEASIBLE
492// CPX_STAT_INForUNBD
493// CPX_STAT_NUM_BEST
494// CPX_STAT_OPTIMAL
495// CPX_STAT_OPTIMAL_FACE_UNBOUNDED
496// CPX_STAT_OPTIMAL_INFEAS
497// CPX_STAT_OPTIMAL_RELAXED
498// CPX_STAT_UNBOUNDED
499
500  LpCplex::SolutionStatus LpCplex::_getDualStatus()
501  {
502    int stat = CPXgetstat(env, lp);
503#if CPX_VERSION >= 800
504    switch (stat)
505    {
506      case CPX_STAT_OPTIMAL:
507        return OPTIMAL;
508      case CPX_STAT_UNBOUNDED:
509        return INFEASIBLE;
510      default:
511        return UNDEFINED;
512    }
513#else
514    statusSwitch(env,stat);
515    switch (stat) {
516    case 0:
517      return UNDEFINED; //Undefined
518    case CPX_OPTIMAL://Optimal
519      return OPTIMAL;
520    case CPX_UNBOUNDED:
521     return INFEASIBLE;
522    default:
523      return UNDEFINED; //Everything else comes here
524      //FIXME error
525    }
526#endif
527  }
528
529  LpCplex::ProblemTypes LpCplex::_getProblemType()
530  {
531    int stat = CPXgetstat(env, lp);
532#if CPX_VERSION >= 800
533    switch (stat)
534    {
535      case CPX_STAT_OPTIMAL:
536        return PRIMAL_DUAL_FEASIBLE;
537      case CPX_STAT_UNBOUNDED:
538        return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
539      default:
540        return UNKNOWN;
541    }
542#else
543    switch (stat) {
544    case CPX_OPTIMAL://Optimal
545        return PRIMAL_DUAL_FEASIBLE;
546    case CPX_UNBOUNDED:
547        return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
548//      return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
549//      return PRIMAL_DUAL_INFEASIBLE;
550
551//Seems to be that this is all we can say for sure
552    default:
553        //In all other cases
554        return UNKNOWN;
555      //FIXME error
556    }
557#endif
558  }
559
560  void LpCplex::_setMax()
561  {
562    CPXchgobjsen(env, lp, CPX_MAX);
563   }
564  void LpCplex::_setMin()
565  {
566    CPXchgobjsen(env, lp, CPX_MIN);
567   }
568 
569} //namespace lemon
570
Note: See TracBrowser for help on using the repository browser.