COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_cplex.cc

Last change on this file was 2605:852361980706, checked in by Balazs Dezso, 11 years ago

Bug fixes in LP solvers

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