COIN-OR::LEMON - Graph Library

source: lemon/lemon/lp_cplex.cc @ 481:7afc121e0689

Last change on this file since 481:7afc121e0689 was 481:7afc121e0689, checked in by Balazs Dezso <deba@…>, 10 years ago

Port LP and MIP solvers from SVN -r3509 (#44)

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