OpenGM  2.3.x
Discrete Graphical Model Library
lpcplex.hxx
Go to the documentation of this file.
1 #pragma once
2 #ifndef OPENGM_LP_CPLEX_HXX
3 #define OPENGM_LP_CPLEX_HXX
4 
5 #include <vector>
6 #include <string>
7 #include <iostream>
8 #include <fstream>
9 #include <stdexcept>
10 #include <typeinfo>
11 
12 #include <ilcplex/ilocplex.h>
13 
14 #include "opengm/datastructures/marray/marray.hxx"
15 #include "opengm/opengm.hxx"
16 #include "opengm/operations/adder.hxx"
17 #include "opengm/operations/minimizer.hxx"
18 #include "opengm/operations/maximizer.hxx"
19 #include "opengm/inference/inference.hxx"
20 #include "opengm/inference/auxiliary/lpdef.hxx"
21 #include "opengm/inference/visitors/visitors.hxx"
22 
23 namespace opengm {
24 
37 template<class GM, class ACC>
38 class LPCplex : public Inference<GM, ACC>, public LPDef {
39 public:
40  typedef ACC AccumulationType;
41  typedef ACC AccumulatorType;
42  typedef GM GraphicalModelType;
43  OPENGM_GM_TYPE_TYPEDEFS;
44  typedef visitors::VerboseVisitor<LPCplex<GM,ACC> > VerboseVisitorType;
45  typedef visitors::EmptyVisitor<LPCplex<GM,ACC> > EmptyVisitorType;
46  typedef visitors::TimingVisitor<LPCplex<GM,ACC> > TimingVisitorType;
47 
48 
49 // enum LP_SOLVER {LP_SOLVER_AUTO, LP_SOLVER_PRIMAL_SIMPLEX, LP_SOLVER_DUAL_SIMPLEX, LP_SOLVER_NETWORK_SIMPLEX, LP_SOLVER_BARRIER, LP_SOLVER_SIFTING, LP_SOLVER_CONCURRENT};
50 // enum LP_PRESOLVE{LP_PRESOLVE_AUTO, LP_PRESOLVE_OFF, LP_PRESOLVE_CONSEVATIVE, LP_PRESOLVE_AGRESSIVE};
51 // enum MIP_EMPHASIS{MIP_EMPHASIS_BALANCED, MIP_EMPHASIS_FEASIBILITY, MIP_EMPHASIS_OPTIMALITY, MIP_EMPHASIS_BESTBOUND, MIP_EMPHASIS_HIDDENFEAS};
52 
53  class Parameter {
54  public:
55  bool integerConstraint_; // ILP=true, 1order-LP=false
56  int numberOfThreads_; // number of threads (0=autosect)
57  bool verbose_; // switch on/off verbode mode
58  double cutUp_; // upper cutoff
59  double epOpt_; // Optimality tolerance
60  double epMrk_; // Markowitz tolerance
61  double epRHS_; // Feasibility Tolerance
62  double epInt_; // amount by which an integer variable can differ from an integer
63  double epAGap_; // Absolute MIP gap tolerance
64  double epGap_; // Relative MIP gap tolerance
65  double workMem_; // maximal ammount of memory in MB used for workspace
66  double treeMemoryLimit_; // maximal ammount of memory in MB used for treee
67  double timeLimit_; // maximal time in seconds the solver has
68  int probeingLevel_;
69  //int coverCutLevel_;
70  //int disjunctiverCutLevel_;
71  //int cliqueCutLevel_;
72  //int MIRCutLevel_;
73  LP_SOLVER rootAlg_;
74  LP_SOLVER nodeAlg_;
75  LP_PRESOLVE presolve_;
76  MIP_EMPHASIS mipEmphasis_;
77  MIP_CUT cutLevel_; // Determines whether or not to cuts for the problem and how aggressively (will be overruled by specific ones).
78  MIP_CUT cliqueCutLevel_; // Determines whether or not to generate clique cuts for the problem and how aggressively.
79  MIP_CUT coverCutLevel_; // Determines whether or not to generate cover cuts for the problem and how aggressively.
80  MIP_CUT gubCutLevel_; // Determines whether or not to generate generalized upper bound (GUB) cuts for the problem and how aggressively.
81  MIP_CUT mirCutLevel_; // Determines whether or not mixed integer rounding (MIR) cuts should be generated for the problem and how aggressively.
82  MIP_CUT iboundCutLevel_; // Determines whether or not to generate implied bound cuts for the problem and how aggressively.
83  MIP_CUT flowcoverCutLevel_; //Determines whether or not to generate flow cover cuts for the problem and how aggressively.
84  MIP_CUT flowpathCutLevel_; //Determines whether or not to generate flow path cuts for the problem and how aggressively.
85  MIP_CUT disjunctCutLevel_; // Determines whether or not to generate disjunctive cuts for the problem and how aggressively.
86  MIP_CUT gomoryCutLevel_; // Determines whether or not to generate gomory fractional cuts for the problem and how aggressively.
87 
91  Parameter
92  (
93  int numberOfThreads = 0
94  )
95  : numberOfThreads_(numberOfThreads),
96  //integerConstraint_(false),
97  verbose_(false),
98  workMem_(128.0),
99  treeMemoryLimit_(1e+75),
100  timeLimit_(1e+75),
101  probeingLevel_(0),
102  // coverCutLevel_(0),
103  //disjunctiverCutLevel_(0),
104  //cliqueCutLevel_(0),
105  //MIRCutLevel_(0),
106  rootAlg_(LP_SOLVER_AUTO),
107  nodeAlg_(LP_SOLVER_AUTO),
108  presolve_(LP_PRESOLVE_AUTO),
109  mipEmphasis_(MIP_EMPHASIS_BALANCED),
110  cutLevel_(MIP_CUT_AUTO),
111  cliqueCutLevel_(MIP_CUT_AUTO),
112  coverCutLevel_(MIP_CUT_AUTO),
113  gubCutLevel_(MIP_CUT_AUTO),
114  mirCutLevel_(MIP_CUT_AUTO),
115  iboundCutLevel_(MIP_CUT_AUTO),
116  flowcoverCutLevel_(MIP_CUT_AUTO),
117  flowpathCutLevel_(MIP_CUT_AUTO),
118  disjunctCutLevel_(MIP_CUT_AUTO),
119  gomoryCutLevel_(MIP_CUT_AUTO)
120  {
121  numberOfThreads_ = numberOfThreads;
122  integerConstraint_ = false;
123  LPDef lpdef;
124  cutUp_ = lpdef.default_cutUp_;
125  epOpt_ = lpdef.default_epOpt_;
126  epMrk_ = lpdef.default_epMrk_;
127  epRHS_ = lpdef.default_epRHS_;
128  epInt_ = lpdef.default_epInt_;
129  epAGap_= lpdef.default_epAGap_;
130  epGap_ = lpdef.default_epGap_;
131  };
132 
133  int getCutLevel(MIP_CUT cl){
134  switch(cl){
135  case MIP_CUT_AUTO:
136  return 0;
137  case MIP_CUT_OFF:
138  return -1;
139  case MIP_CUT_ON:
140  return 1;
141  case MIP_CUT_AGGRESSIVE:
142  return 2;
143  case MIP_CUT_VERYAGGRESSIVE:
144  return 3;
145  }
146  return 0;
147  }
148  };
149 
150  LPCplex(const GraphicalModelType&, const Parameter& = Parameter());
151  ~LPCplex();
152  virtual std::string name() const
153  { return "LPCplex"; }
154  const GraphicalModelType& graphicalModel() const;
155  virtual InferenceTermination infer();
156  template<class VisitorType>
157  InferenceTermination infer(VisitorType&);
158  virtual InferenceTermination arg(std::vector<LabelType>&, const size_t = 1) const;
159  virtual InferenceTermination args(std::vector<std::vector<LabelType> >&) const
160  { return UNKNOWN; };
161  void variable(const size_t, IndependentFactorType& out) const;
162  void factorVariable(const size_t, IndependentFactorType& out) const;
163  typename GM::ValueType bound() const;
164  typename GM::ValueType value() const;
165  void setStartingPoint( typename std::vector<LabelType>::const_iterator );
166 
167 
168  size_t lpNodeVi(const IndexType variableIndex,const LabelType label)const;
169  size_t lpFactorVi(const IndexType factorIndex,const size_t labelingIndex)const;
170  template<class LABELING_ITERATOR>
171  size_t lpFactorVi(const IndexType factorIndex,LABELING_ITERATOR labelingBegin,LABELING_ITERATOR labelingEnd)const;
172  template<class LPVariableIndexIterator, class CoefficientIterator>
173  void addConstraint(LPVariableIndexIterator, LPVariableIndexIterator, CoefficientIterator,const ValueType&, const ValueType&, const char * name=0);
174 
175 private:
176  const GraphicalModelType& gm_;
177  Parameter parameter_;
178  std::vector<size_t> idNodesBegin_;
179  std::vector<size_t> idFactorsBegin_;
180  std::vector<std::vector<size_t> > unaryFactors_;
181  bool inferenceStarted_;
182 
183  IloEnv env_;
184  IloModel model_;
185  IloNumVarArray x_;
186  IloRangeArray c_;
187  IloObjective obj_;
188  IloNumArray sol_;
189  IloCplex cplex_;
190  ValueType constValue_;
191 };
192 
193 template<class GM, class ACC>
194 LPCplex<GM, ACC>::LPCplex
195 (
196  const GraphicalModelType& gm,
197  const Parameter& para
198 )
199 : gm_(gm), inferenceStarted_(false)
200 {
201  if(typeid(OperatorType) != typeid(opengm::Adder)) {
202  throw RuntimeError("This implementation does only supports Min-Plus-Semiring and Max-Plus-Semiring.");
203  }
204  parameter_ = para;
205  idNodesBegin_.resize(gm_.numberOfVariables());
206  unaryFactors_.resize(gm_.numberOfVariables());
207  idFactorsBegin_.resize(gm_.numberOfFactors());
208 
209  // temporal variables
210  IloInt numberOfElements = 0;
211  IloInt numberOfVariableElements = 0;
212  IloInt numberOfFactorElements = 0;
213  // enumerate variables
214  size_t idCounter = 0;
215  for(size_t node = 0; node < gm_.numberOfVariables(); ++node) {
216  numberOfVariableElements += gm_.numberOfLabels(node);
217  idNodesBegin_[node] = idCounter;
218  idCounter += gm_.numberOfLabels(node);
219  }
220  // enumerate factors
221  constValue_ = 0;
222  for(size_t f = 0; f < gm_.numberOfFactors(); ++f) {
223  if(gm_[f].numberOfVariables() == 0) {
224  LabelType l = 0;
225  constValue_ += gm_[f](&l);
226  }
227  else if(gm_[f].numberOfVariables() == 1) {
228  size_t node = gm_[f].variableIndex(0);
229  unaryFactors_[node].push_back(f);
230  idFactorsBegin_[f] = idNodesBegin_[node];
231  }
232  else {
233  idFactorsBegin_[f] = idCounter;
234  idCounter += gm_[f].size();
235  numberOfFactorElements += gm_[f].size();
236  }
237  }
238  numberOfElements = numberOfVariableElements + numberOfFactorElements;
239  // build LP
240  model_ = IloModel(env_);
241  x_ = IloNumVarArray(env_);
242  c_ = IloRangeArray(env_);
243  sol_ = IloNumArray(env_);
244 
245  if(typeid(ACC) == typeid(opengm::Minimizer)) {
246  obj_ = IloMinimize(env_);
247  } else if(typeid(ACC) == typeid(opengm::Maximizer)){
248  obj_ = IloMaximize(env_);
249  } else {
250  throw RuntimeError("This implementation does only support Minimizer or Maximizer accumulators");
251  }
252  // set variables and objective
253  if(parameter_.integerConstraint_) {
254  x_.add(IloNumVarArray(env_, numberOfVariableElements, 0, 1, ILOBOOL));
255  }
256  else {
257  x_.add(IloNumVarArray(env_, numberOfVariableElements, 0, 1));
258  }
259  x_.add(IloNumVarArray(env_, numberOfFactorElements, 0, 1));
260  IloNumArray obj(env_, numberOfElements);
261 
262  for(size_t node = 0; node < gm_.numberOfVariables(); ++node) {
263  for(size_t i = 0; i < gm_.numberOfLabels(node); ++i) {
264  ValueType t = 0;
265  for(size_t n=0; n<unaryFactors_[node].size();++n) {
266  t += gm_[unaryFactors_[node][n]](&i);
267  }
268  OPENGM_ASSERT_OP(idNodesBegin_[node]+i,<,numberOfElements);
269  obj[idNodesBegin_[node]+i] = t;
270  }
271  }
272  for(size_t f = 0; f < gm_.numberOfFactors(); ++f) {
273  if(gm_[f].numberOfVariables() == 2) {
274  size_t index[2];
275  size_t counter = idFactorsBegin_[f];
276  for(index[1]=0; index[1]<gm_[f].numberOfLabels(1);++index[1])
277  for(index[0]=0; index[0]<gm_[f].numberOfLabels(0);++index[0])
278  obj[counter++] = gm_[f](index);
279  }
280  else if(gm_[f].numberOfVariables() == 3) {
281  size_t index[3];
282  size_t counter = idFactorsBegin_[f] ;
283  for(index[2]=0; index[2]<gm_[f].numberOfLabels(2);++index[2])
284  for(index[1]=0; index[1]<gm_[f].numberOfLabels(1);++index[1])
285  for(index[0]=0; index[0]<gm_[f].numberOfLabels(0);++index[0])
286  obj[counter++] = gm_[f](index);
287  }
288  else if(gm_[f].numberOfVariables() == 4) {
289  size_t index[4];
290  size_t counter = idFactorsBegin_[f];
291  for(index[3]=0; index[3]<gm_[f].numberOfLabels(3);++index[3])
292  for(index[2]=0; index[2]<gm_[f].numberOfLabels(2);++index[2])
293  for(index[1]=0; index[1]<gm_[f].numberOfLabels(1);++index[1])
294  for(index[0]=0; index[0]<gm_[f].numberOfLabels(0);++index[0])
295  obj[counter++] = gm_[f](index);
296  }
297  else if(gm_[f].numberOfVariables() > 4) {
298  size_t counter = idFactorsBegin_[f];
299  std::vector<size_t> coordinate(gm_[f].numberOfVariables());
300  marray::Marray<bool> temp(gm_[f].shapeBegin(), gm_[f].shapeEnd());
301  for(marray::Marray<bool>::iterator mit = temp.begin(); mit != temp.end(); ++mit) {
302  mit.coordinate(coordinate.begin());
303  obj[counter++] = gm_[f](coordinate.begin());
304  }
305  }
306  }
307  obj_.setLinearCoefs(x_, obj);
308  // set constraints
309  size_t constraintCounter = 0;
310  // \sum_i \mu_i = 1
311  for(size_t node = 0; node < gm_.numberOfVariables(); ++node) {
312  c_.add(IloRange(env_, 1, 1));
313  for(size_t i = 0; i < gm_.numberOfLabels(node); ++i) {
314  c_[constraintCounter].setLinearCoef(x_[idNodesBegin_[node]+i], 1);
315  }
316  ++constraintCounter;
317  }
318  // \sum_i \mu_{f;i_1,...,i_n} - \mu{b;j}= 0
319  for(size_t f = 0; f < gm_.numberOfFactors(); ++f) {
320  if(gm_[f].numberOfVariables() > 1) {
321  marray::Marray<size_t> temp(gm_[f].shapeBegin(), gm_[f].shapeEnd());
322  size_t counter = idFactorsBegin_[f];
323  for(marray::Marray<size_t>::iterator mit = temp.begin(); mit != temp.end(); ++mit) {
324  *mit = counter++;
325  }
326  for(size_t n = 0; n < gm_[f].numberOfVariables(); ++n) {
327  size_t node = gm_[f].variableIndex(n);
328  for(size_t i = 0; i < gm_.numberOfLabels(node); ++i) {
329  c_.add(IloRange(env_, 0, 0));
330  c_[constraintCounter].setLinearCoef(x_[idNodesBegin_[node]+i], -1);
331  marray::View<size_t> view = temp.boundView(n, i);
332  for(marray::View<size_t>::iterator vit = view.begin(); vit != view.end(); ++vit) {
333  c_[constraintCounter].setLinearCoef(x_[*vit], 1);
334  }
335  ++constraintCounter;
336  }
337  }
338  }
339  }
340  model_.add(obj_);
341  model_.add(c_);
342  // initialize solver
343  try {
344  cplex_ = IloCplex(model_);
345  }
346  catch(IloCplex::Exception& e) {
347  throw std::runtime_error("CPLEX exception");
348  }
349 }
350 
351 template <class GM, class ACC>
352 InferenceTermination
353 LPCplex<GM, ACC>::infer() {
354  EmptyVisitorType v;
355  return infer(v);
356 }
357 
358 template<class GM, class ACC>
359 template<class VisitorType>
360 InferenceTermination
361 LPCplex<GM, ACC>::infer
362 (
363  VisitorType& visitor
364 ) {
365  visitor.begin(*this);
366  inferenceStarted_ = true;
367  try {
368  // Root Algorithm
369  switch(parameter_.rootAlg_) {
370  case LP_SOLVER_AUTO:
371  cplex_.setParam(IloCplex::RootAlg, 0);
372  break;
373  case LP_SOLVER_PRIMAL_SIMPLEX:
374  cplex_.setParam(IloCplex::RootAlg, 1);
375  break;
376  case LP_SOLVER_DUAL_SIMPLEX:
377  cplex_.setParam(IloCplex::RootAlg, 2);
378  break;
379  case LP_SOLVER_NETWORK_SIMPLEX:
380  cplex_.setParam(IloCplex::RootAlg, 3);
381  break;
382  case LP_SOLVER_BARRIER:
383  cplex_.setParam(IloCplex::RootAlg, 4);
384  break;
385  case LP_SOLVER_SIFTING:
386  cplex_.setParam(IloCplex::RootAlg, 5);
387  break;
388  case LP_SOLVER_CONCURRENT:
389  cplex_.setParam(IloCplex::RootAlg, 6);
390  break;
391  }
392 
393  // Node Algorithm
394  switch(parameter_.nodeAlg_) {
395  case LP_SOLVER_AUTO:
396  cplex_.setParam(IloCplex::NodeAlg, 0);
397  break;
398  case LP_SOLVER_PRIMAL_SIMPLEX:
399  cplex_.setParam(IloCplex::NodeAlg, 1);
400  break;
401  case LP_SOLVER_DUAL_SIMPLEX:
402  cplex_.setParam(IloCplex::NodeAlg, 2);
403  break;
404  case LP_SOLVER_NETWORK_SIMPLEX:
405  cplex_.setParam(IloCplex::NodeAlg, 3);
406  break;
407  case LP_SOLVER_BARRIER:
408  cplex_.setParam(IloCplex::NodeAlg, 4);
409  break;
410  case LP_SOLVER_SIFTING:
411  cplex_.setParam(IloCplex::NodeAlg, 5);
412  break;
413  case LP_SOLVER_CONCURRENT:
414  cplex_.setParam(IloCplex::NodeAlg, 6);
415  break;
416  }
417 
418  // presolve
419  switch(parameter_.presolve_) {
420  case LP_PRESOLVE_AUTO:
421  cplex_.setParam(IloCplex::PreInd, CPX_ON);
422  cplex_.setParam(IloCplex::RelaxPreInd, -1);
423  break;
424  case LP_PRESOLVE_OFF:
425  cplex_.setParam(IloCplex::PreInd, CPX_OFF);
426  cplex_.setParam(IloCplex::RelaxPreInd, 0);
427  break;
428  case LP_PRESOLVE_CONSERVATIVE:
429  cplex_.setParam(IloCplex::PreInd, CPX_ON);
430  cplex_.setParam(IloCplex::RelaxPreInd, -1);
431  break;
432  case LP_PRESOLVE_AGGRESSIVE:
433  cplex_.setParam(IloCplex::PreInd, CPX_ON);
434  cplex_.setParam(IloCplex::RelaxPreInd, 1);
435  break;
436  }
437 
438  // MIP EMPHASIS
439  switch(parameter_.mipEmphasis_) {
440  case MIP_EMPHASIS_BALANCED:
441  cplex_.setParam(IloCplex::MIPEmphasis, 0);
442  break;
443  case MIP_EMPHASIS_FEASIBILITY:
444  cplex_.setParam(IloCplex::MIPEmphasis, 1);
445  break;
446  case MIP_EMPHASIS_OPTIMALITY:
447  cplex_.setParam(IloCplex::MIPEmphasis, 2);
448  break;
449  case MIP_EMPHASIS_BESTBOUND:
450  cplex_.setParam(IloCplex::MIPEmphasis, 3);
451  break;
452  case MIP_EMPHASIS_HIDDENFEAS:
453  cplex_.setParam(IloCplex::MIPEmphasis, 4);
454  break;
455  }
456 
457  // verbose options
458  if(parameter_.verbose_ == false) {
459  cplex_.setParam(IloCplex::MIPDisplay, 0);
460  cplex_.setParam(IloCplex::BarDisplay, 0);
461  cplex_.setParam(IloCplex::SimDisplay, 0);
462  cplex_.setParam(IloCplex::NetDisplay, 0);
463  cplex_.setParam(IloCplex::SiftDisplay, 0);
464  }
465 
466  // tolarance settings
467  cplex_.setParam(IloCplex::EpOpt, parameter_.epOpt_); // Optimality Tolerance
468  cplex_.setParam(IloCplex::EpMrk, parameter_.epMrk_); // Markowitz tolerance
469  cplex_.setParam(IloCplex::EpRHS, parameter_.epRHS_); // Feasibility Tolerance
470  cplex_.setParam(IloCplex::EpInt, parameter_.epInt_); // amount by which an integer variable can differ from an integer
471  cplex_.setParam(IloCplex::EpAGap, parameter_.epAGap_); // Absolute MIP gap tolerance
472  cplex_.setParam(IloCplex::EpGap, parameter_.epGap_); // Relative MIP gap tolerance
473 
474  // set hints
475  cplex_.setParam(IloCplex::CutUp, parameter_.cutUp_);
476 
477  // memory setting
478  cplex_.setParam(IloCplex::WorkMem, parameter_.workMem_);
479  cplex_.setParam(IloCplex::ClockType,2);//wall-clock-time=2 cpu-time=1
480  cplex_.setParam(IloCplex::TreLim,parameter_.treeMemoryLimit_);
481  cplex_.setParam(IloCplex::MemoryEmphasis, 1);
482 
483  // time limit
484  cplex_.setParam(IloCplex::TiLim, parameter_.timeLimit_);
485 
486  // multo-threading options
487  cplex_.setParam(IloCplex::Threads, parameter_.numberOfThreads_);
488 
489  // Tuning
490  cplex_.setParam(IloCplex::Probe, parameter_.probeingLevel_);
491  if(parameter_.cutLevel_ != MIP_CUT_DEFAULT){
492  int cl = parameter_.getCutLevel(parameter_.cutLevel_);
493  cplex_.setParam(IloCplex::Covers, cl);
494  cplex_.setParam(IloCplex::Cliques, cl);
495  cplex_.setParam(IloCplex::DisjCuts, cl);
496  cplex_.setParam(IloCplex::Cliques, cl);
497  cplex_.setParam(IloCplex::MIRCuts, cl);
498  cplex_.setParam(IloCplex::GUBCovers, cl);
499  cplex_.setParam(IloCplex::FlowCovers, cl);
500  cplex_.setParam(IloCplex::FlowPaths, cl);
501  cplex_.setParam(IloCplex::ImplBd, cl);
502  cplex_.setParam(IloCplex::FracCuts, cl);
503  }
504 
505  // cplex_.setParam(IloCplex::Covers, parameter_.coverCutLevel_);
506  //cplex_.setParam(IloCplex::DisjCuts, parameter_.disjunctiverCutLevel_);
507  //cplex_.setParam(IloCplex::Cliques, parameter_.cliqueCutLevel_);
508  //cplex_.setParam(IloCplex::MIRCuts, parameter_.MIRCutLevel_);
509 
510  // solve problem
511  if(!cplex_.solve()) {
512  std::cout << "failed to optimize. " <<cplex_.getStatus() << std::endl;
513  return UNKNOWN;
514  }
515  cplex_.getValues(sol_, x_);
516  }
517  catch(IloCplex::Exception e) {
518  std::cout << "caught CPLEX exception: " << e << std::endl;
519  return UNKNOWN;
520  }
521  visitor.end(*this);
522  return NORMAL;
523 }
524 
525 template <class GM, class ACC>
526 LPCplex<GM, ACC>::~LPCplex() {
527  env_.end();
528 }
529 
530 template <class GM, class ACC>
531 inline InferenceTermination
532 LPCplex<GM, ACC>::arg
533 (
534  std::vector<typename LPCplex<GM, ACC>::LabelType>& x,
535  const size_t N
536 ) const {
537  x.resize(gm_.numberOfVariables());
538  if(inferenceStarted_) {
539  for(size_t node = 0; node < gm_.numberOfVariables(); ++node) {
540  ValueType value = sol_[idNodesBegin_[node]];
541  size_t state = 0;
542  for(size_t i = 1; i < gm_.numberOfLabels(node); ++i) {
543  if(sol_[idNodesBegin_[node]+i] > value) {
544  value = sol_[idNodesBegin_[node]+i];
545  state = i;
546  }
547  }
548  x[node] = state;
549  }
550  return NORMAL;
551  } else {
552  for(size_t node = 0; node < gm_.numberOfVariables(); ++node) {
553  x[node] = 0;
554  }
555  return UNKNOWN;
556  }
557 
558 }
559 
560 template <class GM, class ACC>
561 void LPCplex<GM, ACC>::variable
562 (
563  const size_t nodeId,
564  IndependentFactorType& out
565 ) const {
566  size_t var[] = {nodeId};
567  size_t shape[] = {gm_.numberOfLabels(nodeId)};
568  out.assign(var, var + 1, shape, shape + 1);
569  for(size_t i = 0; i < gm_.numberOfLabels(nodeId); ++i) {
570  out(i) = sol_[idNodesBegin_[nodeId]+i];
571  }
572  //return UNKNOWN;
573 }
574 
575 template <class GM, class ACC>
576 void LPCplex<GM, ACC>::factorVariable
577 (
578  const size_t factorId,
579  IndependentFactorType& out
580 ) const {
581  std::vector<size_t> var(gm_[factorId].numberOfVariables());
582  std::vector<size_t> shape(gm_[factorId].numberOfVariables());
583  for(size_t i = 0; i < gm_[factorId].numberOfVariables(); ++i) {
584  var[i] = gm_[factorId].variableIndex(i);
585  shape[i] = gm_[factorId].shape(i);
586  }
587  out.assign(var.begin(), var.end(), shape.begin(), shape.end());
588  if(gm_[factorId].numberOfVariables() == 1) {
589  size_t nodeId = gm_[factorId].variableIndex(0);
590  marginal(nodeId, out);
591  }
592  else {
593  size_t c = 0;
594  for(size_t n = idFactorsBegin_[factorId]; n<idFactorsBegin_[factorId]+gm_[factorId].size(); ++n) {
595  out(c++) = sol_[n];
596  }
597  }
598  //return UNKNOWN;
599 }
600 
601 template<class GM, class ACC>
602 inline void
603 LPCplex<GM, ACC>::setStartingPoint(
604  typename std::vector<typename LPCplex<GM, ACC>::LabelType>::const_iterator begin
605 ) {
606  IloNumVarArray vars(env_);
607  IloNumArray values(env_);
608  for(IndexType var=0; var<gm_.numberOfVariables(); ++var){
609  const IloNumVar lpvar = x_[lpNodeVi(var,*(begin+var))];
610  vars.add(lpvar);
611  values.add(1);
612  }
613  cplex_.addMIPStart(vars, values);
614 }
615 
616 
617 
618 template<class GM, class ACC>
619 inline const typename LPCplex<GM, ACC>::GraphicalModelType&
620 LPCplex<GM, ACC>::graphicalModel() const
621 {
622  return gm_;
623 }
624 
625 template<class GM, class ACC>
626 typename GM::ValueType LPCplex<GM, ACC>::value() const {
627  std::vector<LabelType> states;
628  arg(states);
629  return gm_.evaluate(states);
630 }
631 
632 template<class GM, class ACC>
633 typename GM::ValueType LPCplex<GM, ACC>::bound() const {
634  if(inferenceStarted_) {
635  if(parameter_.integerConstraint_) {
636  return cplex_.getBestObjValue()+constValue_;
637  }
638  else{
639  return cplex_.getObjValue()+constValue_;
640  }
641  }
642  else{
643  return ACC::template ineutral<ValueType>();
644  }
645 }
646 
647 
648 template <class GM, class ACC>
649 inline size_t
650 LPCplex<GM, ACC>::lpNodeVi
651 (
652  const typename LPCplex<GM, ACC>::IndexType variableIndex,
653  const typename LPCplex<GM, ACC>::LabelType label
654 )const{
655  OPENGM_ASSERT(variableIndex<gm_.numberOfVariables());
656  OPENGM_ASSERT(label<gm_.numberOfLabels(variableIndex));
657  return idNodesBegin_[variableIndex]+label;
658 }
659 
660 
661 template <class GM, class ACC>
662 inline size_t
663 LPCplex<GM, ACC>::lpFactorVi
664 (
665  const typename LPCplex<GM, ACC>::IndexType factorIndex,
666  const size_t labelingIndex
667 )const{
668  OPENGM_ASSERT(factorIndex<gm_.numberOfFactors());
669  OPENGM_ASSERT(labelingIndex<gm_[factorIndex].size());
670  return idFactorsBegin_[factorIndex]+labelingIndex;
671 }
672 
673 
674 template <class GM, class ACC>
675 template<class LABELING_ITERATOR>
676 inline size_t
677 LPCplex<GM, ACC>::lpFactorVi
678 (
679  const typename LPCplex<GM, ACC>::IndexType factorIndex,
680  LABELING_ITERATOR labelingBegin,
681  LABELING_ITERATOR labelingEnd
682 )const{
683  OPENGM_ASSERT(factorIndex<gm_.numberOfFactors());
684  OPENGM_ASSERT(std::distance(labelingBegin,labelingEnd)==gm_[factorIndex].numberOfVariables());
685  const size_t numVar=gm_[factorIndex].numberOfVariables();
686  size_t labelingIndex=labelingBegin[0];
687  size_t strides=gm_[factorIndex].numberOfLabels(0);
688  for(size_t vi=1;vi<numVar;++vi){
689  OPENGM_ASSERT(labelingBegin[vi]<gm_[factorIndex].numberOfLabels(vi));
690  labelingIndex+=strides*labelingBegin[vi];
691  strides*=gm_[factorIndex].numberOfLabels(vi);
692  }
693  return idFactorsBegin_[factorIndex]+labelingIndex;
694 }
695 
696 
697 
698 
710 template<class GM, class ACC>
711 template<class LPVariableIndexIterator, class CoefficientIterator>
712 inline void LPCplex<GM, ACC>::addConstraint(
713  LPVariableIndexIterator viBegin,
714  LPVariableIndexIterator viEnd,
715  CoefficientIterator coefficient,
716  const ValueType& lowerBound,
717  const ValueType& upperBound,
718  const char * name
719 ) {
720  IloRange constraint(env_, lowerBound, upperBound, name);
721  while(viBegin != viEnd) {
722  constraint.setLinearCoef(x_[*viBegin], *coefficient);
723  ++viBegin;
724  ++coefficient;
725  }
726  model_.add(constraint);
727  // adding constraints does not require a re-initialization of the
728  // object cplex_. cplex_ is initialized in the constructor.
729 }
730 
731 } // end namespace opengm
732 
733 #endif
opengm::LPCplex::setStartingPoint
void setStartingPoint(typename std::vector< LabelType >::const_iterator)
set initial labeling
Definition: lpcplex.hxx:603
opengm
The OpenGM namespace.
Definition: config.hxx:43
marray::Iterator
STL-compliant random access iterator for View and Marray.
Definition: marray.hxx:49
opengm::Adder
Addition as a binary operation.
Definition: adder.hxx:10
opengm::LPDef::default_epRHS_
static const double default_epRHS_
Definition: lpdef.hxx:17
opengm::LPCplex::bound
GM::ValueType bound() const
return a bound on the solution
Definition: lpcplex.hxx:633
opengm::LPCplex::VerboseVisitorType
visitors::VerboseVisitor< LPCplex< GM, ACC > > VerboseVisitorType
Definition: lpcplex.hxx:44
opengm::LPCplex::Parameter::mipEmphasis_
MIP_EMPHASIS mipEmphasis_
Definition: lpcplex.hxx:76
opengm::LPCplex::graphicalModel
const GraphicalModelType & graphicalModel() const
Definition: lpcplex.hxx:620
opengm::LPDef::default_cutUp_
static const double default_cutUp_
Definition: lpdef.hxx:14
opengm::LPCplex::args
virtual InferenceTermination args(std::vector< std::vector< LabelType > > &) const
Definition: lpcplex.hxx:159
opengm::LPDef::default_epInt_
static const double default_epInt_
Definition: lpdef.hxx:18
opengm::LPCplex::Parameter::getCutLevel
int getCutLevel(MIP_CUT cl)
Definition: lpcplex.hxx:133
marray::View
Array-Interface to an interval of memory.
Definition: marray.hxx:44
OPENGM_ASSERT
#define OPENGM_ASSERT(expression)
Definition: opengm.hxx:77
opengm::LPDef::default_epOpt_
static const double default_epOpt_
Definition: lpdef.hxx:15
opengm::LPDef::default_epAGap_
static const double default_epAGap_
Definition: lpdef.hxx:19
opengm::Inference::OperatorType
GraphicalModelType::OperatorType OperatorType
Definition: inference.hxx:42
opengm::LPCplex::TimingVisitorType
visitors::TimingVisitor< LPCplex< GM, ACC > > TimingVisitorType
Definition: lpcplex.hxx:46
opengm::LPCplex::value
GM::ValueType value() const
return the solution (value)
Definition: lpcplex.hxx:626
opengm::LPCplex::LPCplex
LPCplex(const GraphicalModelType &, const Parameter &=Parameter())
Definition: lpcplex.hxx:195
opengm::LPCplex::GraphicalModelType
GM GraphicalModelType
Definition: lpcplex.hxx:42
opengm::LPCplex::arg
virtual InferenceTermination arg(std::vector< LabelType > &, const size_t=1) const
output a solution
Definition: lpcplex.hxx:533
opengm::LPDef::default_epMrk_
static const double default_epMrk_
Definition: lpdef.hxx:16
opengm::Inference::IndexType
GraphicalModelType::IndexType IndexType
Definition: inference.hxx:40
opengm::LPDef::default_epGap_
static const double default_epGap_
Definition: lpdef.hxx:20
marray::View< T, false, A >::boundView
View< T, isConst, A > boundView(const size_t, const size_t=0) const
OPENGM_ASSERT_OP
#define OPENGM_ASSERT_OP(a, op, b)
runtime assertion
Definition: opengm.hxx:53
opengm::LPCplex::lpFactorVi
size_t lpFactorVi(const IndexType factorIndex, const size_t labelingIndex) const
opengm::LPCplex::variable
void variable(const size_t, IndependentFactorType &out) const
Definition: lpcplex.hxx:562
opengm::LPCplex
Optimization by Linear Programming (LP) or Integer LP using IBM ILOG CPLEX http://www.ilog.com/products/cplex/.
Definition: lpcplex.hxx:38
opengm::LPCplex::factorVariable
void factorVariable(const size_t, IndependentFactorType &out) const
Definition: lpcplex.hxx:577
opengm::Inference::ValueType
GraphicalModelType::ValueType ValueType
Definition: inference.hxx:41
opengm::LPCplex::EmptyVisitorType
visitors::EmptyVisitor< LPCplex< GM, ACC > > EmptyVisitorType
Definition: lpcplex.hxx:45
opengm::Inference
Inference algorithm interface.
Definition: inference.hxx:34
marray::Marray
Runtime-flexible multi-dimensional array.
Definition: marray.hxx:52
opengm::LPCplex::lpNodeVi
size_t lpNodeVi(const IndexType variableIndex, const LabelType label) const
Definition: lpcplex.hxx:651
opengm::Inference::LabelType
GraphicalModelType::LabelType LabelType
Definition: inference.hxx:39
opengm::Minimizer
Minimization as a unary accumulation.
Definition: minimizer.hxx:12
opengm::Maximizer
Maximization as a unary accumulation.
Definition: maximizer.hxx:10
opengm::LPCplex::AccumulatorType
ACC AccumulatorType
Definition: lpcplex.hxx:41
opengm::LPCplex::Parameter::Parameter
Parameter(int numberOfThreads=0)
constructor
Definition: lpcplex.hxx:92
opengm::LPCplex::AccumulationType
ACC AccumulationType
Definition: lpcplex.hxx:40
opengm::LPCplex::infer
virtual InferenceTermination infer()
Definition: lpcplex.hxx:353
opengm::RuntimeError
OpenGM runtime error.
Definition: opengm.hxx:100
opengm::LPCplex::name
virtual std::string name() const
Definition: lpcplex.hxx:152
opengm::LPCplex::addConstraint
void addConstraint(LPVariableIndexIterator, LPVariableIndexIterator, CoefficientIterator, const ValueType &, const ValueType &, const char *name=0)
add constraint
Definition: lpcplex.hxx:712
opengm::InferenceTermination
InferenceTermination
Definition: inference.hxx:24
opengm::Inference::IndependentFactorType
GraphicalModelType::IndependentFactorType IndependentFactorType
Definition: inference.hxx:44
Generated by   doxygen 1.8.9.1