COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_cplex.cc @ 1840:173b53b28d7c

Last change on this file since 1840:173b53b28d7c was 1840:173b53b28d7c, checked in by marci, 14 years ago

max flow with lp column generation

File size: 12.3 KB
Line 
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>
18
19///\file
20///\brief Implementation of the LEMON-CPLEX lp solver interface.
21namespace lemon {
22 
23  LpCplex::LpCplex() : LpSolverBase() {
24
25    //    env = CPXopenCPLEXdevelop(&status);     
26    env = CPXopenCPLEX(&status);     
27    lp = CPXcreateprob(env, &status, "LP problem");
28  }
29 
30  LpCplex::~LpCplex() {
31    CPXfreeprob(env,&lp);
32    CPXcloseCPLEX(&env);
33  }
34 
35  LpSolverBase &LpCplex::_newLp()
36  {
37    //The first approach opens a new environment
38    LpCplex* newlp=new LpCplex();
39    return *newlp;
40  }
41
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  }
51
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  }
61
62 
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  }
74
75
76  void LpCplex::_eraseCol(int i) {
77    CPXdelcols(env, lp, i, i);
78  }
79 
80  void LpCplex::_eraseRow(int i) {
81    CPXdelrows(env, lp, i, i);
82  }
83
84 
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  }
102 
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  }
119 
120  void LpCplex::_setCoeff(int row, int col, Value value)
121  {
122    CPXchgcoef(env, lp, row, col, value);
123  }
124
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);
134 
135  }
136 
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  }
147
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    }
155   
156    int cnt=1;
157    int indices[1];
158    indices[0]=i;
159    char sense[1];
160
161    if (lb==-INF){
162      sense[0]='L';
163      CPXchgsense(env, lp, cnt, indices, sense);
164      CPXchgcoef(env, lp, i, -1, ub);
165     
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  }
188
189//   void LpCplex::_setRowLowerBound(int i, Value value)
190//   {
191//     //Not implemented, obsolete
192//   }
193 
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);
203
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// //     }
216
217// //     status = CPXchgcoef(env, lp, i, -2, value_rng);
218//   }
219 
220  void LpCplex::_setObjCoeff(int i, Value obj_coef)
221  {
222    CPXchgcoef(env, lp, -1, i, obj_coef);
223  }
224
225  void LpCplex::_clearObj()
226  {
227    for (int i=0;i< CPXgetnumcols(env, lp);++i){
228      CPXchgcoef(env, lp, -1, i, 0);
229    }
230   
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  }
263
264  LpCplex::Value LpCplex::_getPrimal(int i)
265  {
266    Value x;
267    CPXgetx(env, lp, &x, i, i);
268    return x;
269  }
270
271  LpCplex::Value LpCplex::_getDual(int i)
272  {
273    Value y;
274    CPXgetpi(env, lp, &y, i, i);
275    return y;
276  }
277 
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=new int[CPXgetnumcols(env, lp)];
289    return CPXgetbase(env, lp, cstat, NULL);
290    bool result=(cstat[i]==CPX_BASIC);
291    delete[] cstat;
292    return result;
293  } 
294
295//7.5-os cplex statusai (Vigyazat: a 9.0-asei masok!)
296// 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.
297
298// For Simplex, Barrier 
299// 1    CPX_OPTIMAL 
300//       Optimal solution found 
301// 2    CPX_INFEASIBLE 
302//       Problem infeasible 
303// 3    CPX_UNBOUNDED 
304//       Problem unbounded 
305// 4    CPX_OBJ_LIM 
306//       Objective limit exceeded in Phase II 
307// 5    CPX_IT_LIM_FEAS 
308//       Iteration limit exceeded in Phase II 
309// 6    CPX_IT_LIM_INFEAS 
310//       Iteration limit exceeded in Phase I 
311// 7    CPX_TIME_LIM_FEAS 
312//       Time limit exceeded in Phase II 
313// 8    CPX_TIME_LIM_INFEAS 
314//       Time limit exceeded in Phase I 
315// 9    CPX_NUM_BEST_FEAS 
316//       Problem non-optimal, singularities in Phase II 
317// 10   CPX_NUM_BEST_INFEAS 
318//       Problem non-optimal, singularities in Phase I 
319// 11   CPX_OPTIMAL_INFEAS 
320//       Optimal solution found, unscaled infeasibilities 
321// 12   CPX_ABORT_FEAS 
322//       Aborted in Phase II 
323// 13   CPX_ABORT_INFEAS 
324//       Aborted in Phase I 
325// 14   CPX_ABORT_DUAL_INFEAS 
326//       Aborted in barrier, dual infeasible 
327// 15   CPX_ABORT_PRIM_INFEAS 
328//       Aborted in barrier, primal infeasible 
329// 16   CPX_ABORT_PRIM_DUAL_INFEAS 
330//       Aborted in barrier, primal and dual infeasible 
331// 17   CPX_ABORT_PRIM_DUAL_FEAS 
332//       Aborted in barrier, primal and dual feasible 
333// 18   CPX_ABORT_CROSSOVER 
334//       Aborted in crossover 
335// 19   CPX_INForUNBD 
336//       Infeasible or unbounded 
337// 20   CPX_PIVOT
338//       User pivot used
339//
340//     Ezeket hova tegyem:
341// ??case CPX_ABORT_DUAL_INFEAS           
342// ??case CPX_ABORT_CROSSOVER             
343// ??case CPX_INForUNBD                   
344// ??case CPX_PIVOT             
345         
346//Some more interesting stuff:
347
348// CPX_PARAM_LPMETHOD  1062  int  LPMETHOD
349// 0 Automatic
350// 1 Primal Simplex
351// 2 Dual Simplex
352// 3 Network Simplex
353// 4 Standard Barrier
354// Default: 0
355// Description: Method for linear optimization.
356// 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
357  //Hulye cplex
358  void statusSwitch(CPXENVptr env,int& stat){
359    int lpmethod;
360    CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);
361    if (lpmethod==2){
362      if (stat==CPX_UNBOUNDED){
363        stat=CPX_INFEASIBLE;
364      }
365      else{
366        if (stat==CPX_INFEASIBLE)
367          stat=CPX_UNBOUNDED;
368      }
369    }
370  }
371
372  LpCplex::SolutionStatus LpCplex::_getPrimalStatus()
373  {
374   
375    int stat = CPXgetstat(env, lp);
376    statusSwitch(env,stat);
377    //CPXgetstat(env, lp);
378    //printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL);
379    switch (stat) {
380    case 0:
381      return UNDEFINED; //Undefined
382    case CPX_OPTIMAL://Optimal
383      return OPTIMAL;
384    case CPX_UNBOUNDED://Unbounded
385      return INFEASIBLE;//In case of dual simplex
386      //return INFINITE;
387    case CPX_INFEASIBLE://Infeasible
388 //    case CPX_IT_LIM_INFEAS:
389//     case CPX_TIME_LIM_INFEAS:
390//     case CPX_NUM_BEST_INFEAS:             
391//     case CPX_OPTIMAL_INFEAS:             
392//     case CPX_ABORT_INFEAS:               
393//     case CPX_ABORT_PRIM_INFEAS:           
394//     case CPX_ABORT_PRIM_DUAL_INFEAS:     
395      return INFINITE;//In case of dual simplex
396      //return INFEASIBLE;
397//     case CPX_OBJ_LIM:                   
398//     case CPX_IT_LIM_FEAS:             
399//     case CPX_TIME_LIM_FEAS:               
400//     case CPX_NUM_BEST_FEAS:               
401//     case CPX_ABORT_FEAS:                 
402//     case CPX_ABORT_PRIM_DUAL_FEAS:       
403//       return FEASIBLE;
404    default:
405      return UNDEFINED; //Everything else comes here
406      //FIXME error
407    }
408
409  }
410
411//9.0-as cplex verzio statusai
412// CPX_STAT_ABORT_DUAL_OBJ_LIM
413// CPX_STAT_ABORT_IT_LIM
414// CPX_STAT_ABORT_OBJ_LIM
415// CPX_STAT_ABORT_PRIM_OBJ_LIM
416// CPX_STAT_ABORT_TIME_LIM
417// CPX_STAT_ABORT_USER
418// CPX_STAT_FEASIBLE_RELAXED
419// CPX_STAT_INFEASIBLE
420// CPX_STAT_INForUNBD
421// CPX_STAT_NUM_BEST
422// CPX_STAT_OPTIMAL
423// CPX_STAT_OPTIMAL_FACE_UNBOUNDED
424// CPX_STAT_OPTIMAL_INFEAS
425// CPX_STAT_OPTIMAL_RELAXED
426// CPX_STAT_UNBOUNDED
427
428  LpCplex::SolutionStatus LpCplex::_getDualStatus()
429  {
430    int stat = CPXgetstat(env, lp);
431    statusSwitch(env,stat);
432    switch (stat) {
433    case 0:
434      return UNDEFINED; //Undefined
435    case CPX_OPTIMAL://Optimal
436      return OPTIMAL;
437    case CPX_UNBOUNDED:
438     return INFEASIBLE;
439    default:
440      return UNDEFINED; //Everything else comes here
441      //FIXME error
442    }
443  }
444
445  LpCplex::ProblemTypes LpCplex::_getProblemType()
446  {
447    int stat = CPXgetstat(env, lp);
448    switch (stat) {
449    case CPX_OPTIMAL://Optimal
450        return PRIMAL_DUAL_FEASIBLE;
451    case CPX_UNBOUNDED:
452        return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
453//      return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
454//      return PRIMAL_DUAL_INFEASIBLE;
455
456//Seems to be that this is all we can say for sure
457    default:
458        //In all other cases
459        return UNKNOWN;
460      //FIXME error
461    }
462  }
463
464  void LpCplex::_setMax()
465  {
466    CPXchgobjsen(env, lp, CPX_MAX);
467   }
468  void LpCplex::_setMin()
469  {
470    CPXchgobjsen(env, lp, CPX_MIN);
471   }
472 
473} //namespace lemon
474
Note: See TracBrowser for help on using the repository browser.