COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_cplex.cc @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 13 years ago

Happy New Year to all source files!

File size: 16.5 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
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    //    env = CPXopenCPLEXdevelop(&status);     
28    env = CPXopenCPLEX(&status);     
29    lp = CPXcreateprob(env, &status, "LP problem");
30  }
31 
32  LpCplex::~LpCplex() {
33    CPXfreeprob(env,&lp);
34    CPXcloseCPLEX(&env);
35  }
36 
37  LpSolverBase &LpCplex::_newLp()
38  {
39    //The first approach opens a new environment
40    LpCplex* newlp=new LpCplex();
41    return *newlp;
42  }
43
44  LpSolverBase &LpCplex::_copyLp() {
45    ///\bug FixID data is not copied!
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) const
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  int LpCplex::_colByName(const std::string& name) const
112  {
113    int index;
114    if (CPXgetcolindex(env, lp,
115                       const_cast<char*>(name.c_str()), &index) == 0) {
116      return index;
117    }
118    return -1;
119  }
120 
121  ///\warning Data at index 0 is ignored in the arrays.
122  void LpCplex::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e)
123  {
124    std::vector<int> indices;
125    std::vector<int> rowlist;
126    std::vector<Value> values;
127
128    for(ConstRowIterator it=b; it!=e; ++it) {
129      indices.push_back(it->first);
130      values.push_back(it->second);
131      rowlist.push_back(i);
132    }
133
134    status = CPXchgcoeflist(env, lp, values.size(),
135                            &rowlist[0], &indices[0], &values[0]);
136  }
137
138  void LpSoplex::_getRowCoeffs(int i, RowIterator b) const {
139    /// \todo implement
140  }
141 
142  void LpCplex::_setColCoeffs(int i, ConstColIterator b, ConstColIterator e)
143  {
144    std::vector<int> indices;
145    std::vector<int> collist;
146    std::vector<Value> values;
147
148    for(ConstColIterator it=b; it!=e; ++it) {
149      indices.push_back(it->first);
150      values.push_back(it->second);
151      collist.push_back(i);
152    }
153
154    status = CPXchgcoeflist(env, lp, values.size(),
155                            &indices[0], &collist[0], &values[0]);
156  }
157
158  void LpSoplex::_getColCoeffs(int i, ColIterator b) const {
159    /// \todo implement
160  }
161 
162  void LpCplex::_setCoeff(int row, int col, Value value)
163  {
164    CPXchgcoef(env, lp, row, col, value);
165  }
166
167  LpCplex::Value LpCplex::_getCoeff(int row, int col) const
168  {
169    LpCplex::Value value;
170    CPXgetcoef(env, lp, row, col, &value);
171    return value;
172  }
173
174  void LpCplex::_setColLowerBound(int i, Value value)
175  {
176    int indices[1];
177    indices[0]=i;
178    char lu[1];
179    lu[0]='L';
180    Value bd[1];
181    bd[0]=value;
182    status = CPXchgbds(env, lp, 1, indices, lu, bd);
183 
184  }
185
186  LpCplex::Value LpCplex::_getColLowerBound(int i) const
187  {
188    LpCplex::Value x;
189    CPXgetlb (env, lp, &x, i, i);
190    return x;
191  }
192 
193  void LpCplex::_setColUpperBound(int i, Value value)
194  {
195    int indices[1];
196    indices[0]=i;
197    char lu[1];
198    lu[0]='U';
199    Value bd[1];
200    bd[0]=value;
201    status = CPXchgbds(env, lp, 1, indices, lu, bd);
202  }
203
204  LpCplex::Value LpCplex::_getColUpperBound(int i) const
205  {
206    LpCplex::Value x;
207    CPXgetub (env, lp, &x, i, i);
208    return x;
209  }
210
211  //This will be easier to implement
212  void LpCplex::_setRowBounds(int i, Value lb, Value ub)
213  {
214    //Bad parameter
215    if (lb==INF || ub==-INF) {
216      //FIXME error
217    }
218   
219    int cnt=1;
220    int indices[1];
221    indices[0]=i;
222    char sense[1];
223
224    if (lb==-INF){
225      sense[0]='L';
226      CPXchgsense(env, lp, cnt, indices, sense);
227      CPXchgcoef(env, lp, i, -1, ub);
228     
229    }
230    else{
231      if (ub==INF){
232        sense[0]='G';
233        CPXchgsense(env, lp, cnt, indices, sense);
234        CPXchgcoef(env, lp, i, -1, lb);
235      }
236      else{
237        if (lb == ub){
238          sense[0]='E';
239          CPXchgsense(env, lp, cnt, indices, sense);
240          CPXchgcoef(env, lp, i, -1, lb);
241        }
242        else{
243          sense[0]='R';
244          CPXchgsense(env, lp, cnt, indices, sense);
245          CPXchgcoef(env, lp, i, -1, lb);
246          CPXchgcoef(env, lp, i, -2, ub-lb);     
247        }
248      }
249    }
250  }
251
252//   void LpCplex::_setRowLowerBound(int i, Value value)
253//   {
254//     //Not implemented, obsolete
255//   }
256 
257//   void LpCplex::_setRowUpperBound(int i, Value value)
258//   {
259//     //Not implemented, obsolete
260// //     //TODO Ezt kell meg megirni
261// //     //type of the problem
262// //     char sense[1];
263// //     status = CPXgetsense(env, lp, sense, i, i);
264// //     Value rhs[1];
265// //     status = CPXgetrhs(env, lp, rhs, i, i);
266
267// //     switch (sense[0]) {
268// //     case 'L'://<= constraint
269// //       break;
270// //     case 'E'://= constraint
271// //       break;
272// //     case 'G'://>= constraint
273// //       break;
274// //     case 'R'://ranged constraint
275// //       break;
276// //     default: ;
277// //       //FIXME error
278// //     }
279
280// //     status = CPXchgcoef(env, lp, i, -2, value_rng);
281//   }
282 
283  void LpCplex::_getRowBounds(int i, Value &lb, Value &ub) const
284  {
285    char sense;
286    CPXgetsense(env, lp, &sense,i,i);
287    lb=-INF;
288    ub=INF;
289    switch (sense)
290      {
291      case 'L':
292        CPXgetcoef(env, lp, i, -1, &ub);
293        break;
294      case 'G':
295        CPXgetcoef(env, lp, i, -1, &lb);
296        break;
297      case 'E':
298        CPXgetcoef(env, lp, i, -1, &lb);
299        ub=lb;
300        break;
301      case 'R':
302        CPXgetcoef(env, lp, i, -1, &lb);
303        Value x;
304        CPXgetcoef(env, lp, i, -2, &x);
305        ub=lb+x;
306        break;
307      }
308  }
309
310  void LpCplex::_setObjCoeff(int i, Value obj_coef)
311  {
312    CPXchgcoef(env, lp, -1, i, obj_coef);
313  }
314
315  LpCplex::Value LpCplex::_getObjCoeff(int i) const
316  {
317    Value x;
318    CPXgetcoef(env, lp, -1, i, &x);
319    return x;
320  }
321
322  void LpCplex::_clearObj()
323  {
324    for (int i=0;i< CPXgetnumcols(env, lp);++i){
325      CPXchgcoef(env, lp, -1, i, 0);
326    }
327   
328  }
329  // The routine returns zero unless an error occurred during the
330  // optimization. Examples of errors include exhausting available
331  // memory (CPXERR_NO_MEMORY) or encountering invalid data in the
332  // CPLEX problem object (CPXERR_NO_PROBLEM). Exceeding a
333  // user-specified CPLEX limit, or proving the model infeasible or
334  // unbounded, are not considered errors. Note that a zero return
335  // value does not necessarily mean that a solution exists. Use query
336  // routines CPXsolninfo, CPXgetstat, and CPXsolution to obtain
337  // further information about the status of the optimization.
338  LpCplex::SolveExitStatus LpCplex::_solve()
339  {
340    //CPX_PARAM_LPMETHOD
341    status = CPXlpopt(env, lp);
342    //status = CPXprimopt(env, lp);
343#if CPX_VERSION >= 800
344    if (status)
345    {
346      return UNSOLVED;
347    }
348    else
349    {
350      switch (CPXgetstat(env, lp))
351      {
352        case CPX_STAT_OPTIMAL:
353        case CPX_STAT_INFEASIBLE:
354        case CPX_STAT_UNBOUNDED:
355          return SOLVED;
356        default:
357          return UNSOLVED;
358      }
359    }
360#else
361    if (status == 0){
362      //We want to exclude some cases
363      switch (CPXgetstat(env, lp)){
364      case CPX_OBJ_LIM:
365      case CPX_IT_LIM_FEAS:
366      case CPX_IT_LIM_INFEAS:               
367      case CPX_TIME_LIM_FEAS:
368      case CPX_TIME_LIM_INFEAS:
369        return UNSOLVED;
370      default:
371        return SOLVED;
372      }
373    }
374    else{
375      return UNSOLVED;
376    }
377#endif
378  }
379
380  LpCplex::Value LpCplex::_getPrimal(int i) const
381  {
382    Value x;
383    CPXgetx(env, lp, &x, i, i);
384    return x;
385  }
386
387  LpCplex::Value LpCplex::_getDual(int i) const
388  {
389    Value y;
390    CPXgetpi(env, lp, &y, i, i);
391    return y;
392  }
393 
394  LpCplex::Value LpCplex::_getPrimalValue() const
395  {
396    Value objval;
397    //method = CPXgetmethod (env, lp);
398    //printf("CPXgetprobtype %d \n",CPXgetprobtype(env,lp));
399    status = CPXgetobjval(env, lp, &objval);
400    //printf("Objective value: %g \n",objval);
401    return objval;
402  }
403  bool LpCplex::_isBasicCol(int i) const
404  {
405    int cstat[CPXgetnumcols(env, lp)];
406    CPXgetbase(env, lp, cstat, NULL);
407    return (cstat[i]==CPX_BASIC);
408  } 
409
410//7.5-os cplex statusai (Vigyazat: a 9.0-asei masok!)
411// 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.
412
413// For Simplex, Barrier 
414// 1    CPX_OPTIMAL 
415//       Optimal solution found 
416// 2    CPX_INFEASIBLE 
417//       Problem infeasible 
418// 3    CPX_UNBOUNDED 
419//       Problem unbounded 
420// 4    CPX_OBJ_LIM 
421//       Objective limit exceeded in Phase II 
422// 5    CPX_IT_LIM_FEAS 
423//       Iteration limit exceeded in Phase II 
424// 6    CPX_IT_LIM_INFEAS 
425//       Iteration limit exceeded in Phase I 
426// 7    CPX_TIME_LIM_FEAS 
427//       Time limit exceeded in Phase II 
428// 8    CPX_TIME_LIM_INFEAS 
429//       Time limit exceeded in Phase I 
430// 9    CPX_NUM_BEST_FEAS 
431//       Problem non-optimal, singularities in Phase II 
432// 10   CPX_NUM_BEST_INFEAS 
433//       Problem non-optimal, singularities in Phase I 
434// 11   CPX_OPTIMAL_INFEAS 
435//       Optimal solution found, unscaled infeasibilities 
436// 12   CPX_ABORT_FEAS 
437//       Aborted in Phase II 
438// 13   CPX_ABORT_INFEAS 
439//       Aborted in Phase I 
440// 14   CPX_ABORT_DUAL_INFEAS 
441//       Aborted in barrier, dual infeasible 
442// 15   CPX_ABORT_PRIM_INFEAS 
443//       Aborted in barrier, primal infeasible 
444// 16   CPX_ABORT_PRIM_DUAL_INFEAS 
445//       Aborted in barrier, primal and dual infeasible 
446// 17   CPX_ABORT_PRIM_DUAL_FEAS 
447//       Aborted in barrier, primal and dual feasible 
448// 18   CPX_ABORT_CROSSOVER 
449//       Aborted in crossover 
450// 19   CPX_INForUNBD 
451//       Infeasible or unbounded 
452// 20   CPX_PIVOT
453//       User pivot used
454//
455//     Ezeket hova tegyem:
456// ??case CPX_ABORT_DUAL_INFEAS           
457// ??case CPX_ABORT_CROSSOVER             
458// ??case CPX_INForUNBD                   
459// ??case CPX_PIVOT             
460         
461//Some more interesting stuff:
462
463// CPX_PARAM_LPMETHOD  1062  int  LPMETHOD
464// 0 Automatic
465// 1 Primal Simplex
466// 2 Dual Simplex
467// 3 Network Simplex
468// 4 Standard Barrier
469// Default: 0
470// Description: Method for linear optimization.
471// 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
472  void statusSwitch(CPXENVptr env,int& stat){
473#if CPX_VERSION < 900
474    int lpmethod;
475    CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);
476    if (lpmethod==2){
477      if (stat==CPX_UNBOUNDED){
478        stat=CPX_INFEASIBLE;
479      }
480      else{
481        if (stat==CPX_INFEASIBLE)
482          stat=CPX_UNBOUNDED;
483      }
484    }
485#endif
486  }
487
488  LpCplex::SolutionStatus LpCplex::_getPrimalStatus() const
489  {
490    //Unboundedness not treated well: the following is from cplex 9.0 doc
491    // About Unboundedness
492
493    // The treatment of models that are unbounded involves a few
494    // subtleties. Specifically, a declaration of unboundedness means that
495    // ILOG CPLEX has determined that the model has an unbounded
496    // ray. Given any feasible solution x with objective z, a multiple of
497    // the unbounded ray can be added to x to give a feasible solution
498    // with objective z-1 (or z+1 for maximization models). Thus, if a
499    // feasible solution exists, then the optimal objective is
500    // unbounded. Note that ILOG CPLEX has not necessarily concluded that
501    // a feasible solution exists. Users can call the routine CPXsolninfo
502    // to determine whether ILOG CPLEX has also concluded that the model
503    // has a feasible solution.
504
505    int stat = CPXgetstat(env, lp);
506#if CPX_VERSION >= 800
507    switch (stat)
508    {
509      case CPX_STAT_OPTIMAL:
510        return OPTIMAL;
511      case CPX_STAT_UNBOUNDED:
512        return INFINITE;
513      case CPX_STAT_INFEASIBLE:
514        return INFEASIBLE;
515      default:
516        return UNDEFINED;
517    }
518#else
519    statusSwitch(env,stat);
520    //CPXgetstat(env, lp);
521    //printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL);
522    switch (stat) {
523    case 0:
524      return UNDEFINED; //Undefined
525    case CPX_OPTIMAL://Optimal
526      return OPTIMAL;
527    case CPX_UNBOUNDED://Unbounded
528      return INFEASIBLE;//In case of dual simplex
529      //return INFINITE;
530    case CPX_INFEASIBLE://Infeasible
531 //    case CPX_IT_LIM_INFEAS:
532//     case CPX_TIME_LIM_INFEAS:
533//     case CPX_NUM_BEST_INFEAS:             
534//     case CPX_OPTIMAL_INFEAS:             
535//     case CPX_ABORT_INFEAS:               
536//     case CPX_ABORT_PRIM_INFEAS:           
537//     case CPX_ABORT_PRIM_DUAL_INFEAS:     
538      return INFINITE;//In case of dual simplex
539      //return INFEASIBLE;
540//     case CPX_OBJ_LIM:                   
541//     case CPX_IT_LIM_FEAS:             
542//     case CPX_TIME_LIM_FEAS:               
543//     case CPX_NUM_BEST_FEAS:               
544//     case CPX_ABORT_FEAS:                 
545//     case CPX_ABORT_PRIM_DUAL_FEAS:       
546//       return FEASIBLE;
547    default:
548      return UNDEFINED; //Everything else comes here
549      //FIXME error
550    }
551#endif
552  }
553
554//9.0-as cplex verzio statusai
555// CPX_STAT_ABORT_DUAL_OBJ_LIM
556// CPX_STAT_ABORT_IT_LIM
557// CPX_STAT_ABORT_OBJ_LIM
558// CPX_STAT_ABORT_PRIM_OBJ_LIM
559// CPX_STAT_ABORT_TIME_LIM
560// CPX_STAT_ABORT_USER
561// CPX_STAT_FEASIBLE_RELAXED
562// CPX_STAT_INFEASIBLE
563// CPX_STAT_INForUNBD
564// CPX_STAT_NUM_BEST
565// CPX_STAT_OPTIMAL
566// CPX_STAT_OPTIMAL_FACE_UNBOUNDED
567// CPX_STAT_OPTIMAL_INFEAS
568// CPX_STAT_OPTIMAL_RELAXED
569// CPX_STAT_UNBOUNDED
570
571  LpCplex::SolutionStatus LpCplex::_getDualStatus() const
572  {
573    int stat = CPXgetstat(env, lp);
574#if CPX_VERSION >= 800
575    switch (stat)
576    {
577      case CPX_STAT_OPTIMAL:
578        return OPTIMAL;
579      case CPX_STAT_UNBOUNDED:
580        return INFEASIBLE;
581      default:
582        return UNDEFINED;
583    }
584#else
585    statusSwitch(env,stat);
586    switch (stat) {
587    case 0:
588      return UNDEFINED; //Undefined
589    case CPX_OPTIMAL://Optimal
590      return OPTIMAL;
591    case CPX_UNBOUNDED:
592     return INFEASIBLE;
593    default:
594      return UNDEFINED; //Everything else comes here
595      //FIXME error
596    }
597#endif
598  }
599
600  LpCplex::ProblemTypes LpCplex::_getProblemType() const
601  {
602    int stat = CPXgetstat(env, lp);
603#if CPX_VERSION >= 800
604    switch (stat)
605    {
606      case CPX_STAT_OPTIMAL:
607        return PRIMAL_DUAL_FEASIBLE;
608      case CPX_STAT_UNBOUNDED:
609        return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
610      default:
611        return UNKNOWN;
612    }
613#else
614    switch (stat) {
615    case CPX_OPTIMAL://Optimal
616        return PRIMAL_DUAL_FEASIBLE;
617    case CPX_UNBOUNDED:
618        return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
619//      return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
620//      return PRIMAL_DUAL_INFEASIBLE;
621
622//Seems to be that this is all we can say for sure
623    default:
624        //In all other cases
625        return UNKNOWN;
626      //FIXME error
627    }
628#endif
629  }
630
631  void LpCplex::_setMax()
632  {
633    CPXchgobjsen(env, lp, CPX_MAX);
634   }
635  void LpCplex::_setMin()
636  {
637    CPXchgobjsen(env, lp, CPX_MIN);
638   }
639
640  bool LpCplex::_isMax() const
641  {
642    if (CPXgetobjsen(env, lp)==CPX_MAX)
643      return true;
644    else
645      return false;
646  }
647 
648} //namespace lemon
649
Note: See TracBrowser for help on using the repository browser.