OpenGM  2.3.x
Discrete Graphical Model Library
lp_inference_base.hxx
Go to the documentation of this file.
1 #ifndef OPENGM_LP_INFERENCE_BASE_HXX_
2 #define OPENGM_LP_INFERENCE_BASE_HXX_
3 
4 #include <utility>
5 #include <vector>
6 #include <map>
7 #include <list>
8 #include <typeinfo>
9 #include <limits>
10 
11 #include <opengm/datastructures/marray/marray.hxx>
12 #include <opengm/inference/inference.hxx>
13 #include <opengm/inference/visitors/visitors.hxx>
14 #include <opengm/datastructures/linear_constraint.hxx>
15 #include <opengm/inference/auxiliary/lp_functiontransfer.hxx>
16 #include <opengm/functions/constraint_functions/linear_constraint_function_base.hxx>
17 #include <opengm/utilities/metaprogramming.hxx>
18 #include <opengm/utilities/subsequence_iterator.hxx>
19 
20 namespace opengm {
21 
22 /********************
23  * class definition *
24  *******************/
25 template <class LP_INFERENCE_TYPE>
26 struct LPInferenceTraits;
27 
28 template <class LP_INFERENCE_TYPE>
29 class LPInferenceBase : public Inference<typename LPInferenceTraits<LP_INFERENCE_TYPE>::GraphicalModelType, typename LPInferenceTraits<LP_INFERENCE_TYPE>::AccumulationType> {
30 public:
31  // typedefs
32  typedef LP_INFERENCE_TYPE LPInferenceType;
33  typedef LPInferenceTraits<LPInferenceType> LPInferenceTraitsType;
34  typedef LPInferenceBase<LPInferenceType> LPInferenceBaseType;
35  typedef typename LPInferenceTraitsType::AccumulationType AccumulationType;
36  typedef typename LPInferenceTraitsType::GraphicalModelType GraphicalModelType;
37  OPENGM_GM_TYPE_TYPEDEFS;
38 
39  typedef visitors::VerboseVisitor<LPInferenceBaseType> VerboseVisitorType;
40  typedef visitors::EmptyVisitor<LPInferenceBaseType> EmptyVisitorType;
41  typedef visitors::TimingVisitor<LPInferenceBaseType> TimingVisitorType;
42 
43  typedef LinearConstraint<ValueType, IndexType, LabelType> LinearConstraintType;
44  typedef std::vector<LinearConstraintType> LinearConstraintsContainerType;
45  typedef typename LinearConstraintsContainerType::const_iterator LinearConstraintsIteratorType;
46  typedef typename LinearConstraintType::IndicatorVariableType IndicatorVariableType;
47  typedef typename LinearConstraintType::IndicatorVariablesContainerType IndicatorVariablesContainerType;
48  typedef typename LinearConstraintType::IndicatorVariablesIteratorType IndicatorVariablesIteratorType;
49  typedef typename LinearConstraintType::VariableLabelPairsIteratorType VariableLabelPairsIteratorType;
50 
51  typedef LPFunctionTransfer<ValueType, IndexType, LabelType> LPFunctionTransferType;
52 
53  typedef typename LPInferenceTraitsType::SolverType SolverType;
54  typedef typename LPInferenceTraitsType::SolverIndexType SolverIndexType;
55  typedef typename LPInferenceTraitsType::SolverValueType SolverValueType;
56  typedef typename LPInferenceTraitsType::SolverSolutionIteratorType SolverSolutionIteratorType;
57  typedef typename LPInferenceTraitsType::SolverTimingType SolverTimingType;
58  typedef typename LPInferenceTraitsType::SolverParameterType SolverParameterType;
59 
60  typedef SubsequenceIterator<typename std::vector<LabelType>::const_iterator, typename std::vector<size_t>::const_iterator> IntegerSolutionSubsequenceIterator;
61  typedef SubsequenceIterator<SolverSolutionIteratorType, typename std::vector<size_t>::const_iterator> RelaxedSolutionSubsequenceIterator;
62 
63  struct Parameter : public SolverParameterType {
64  // LocalPolytope will add a first order local polytope approximation of the marginal polytope, i.e. the affine instead of the convex hull.
65  // LoosePolytope will add no constraints at all. All linear constraints will be added iteratively only if they are violated.
66  // TightPolytope will add all constraints of the LocalPolytope relaxation and furthermore all constraints that are present in the model via constraint functions. Thus all constraints will be added before the first run of lp inference which leads to solving the problem in only one iteration.
67  enum Relaxation {LocalPolytope, LoosePolytope, TightPolytope};
68  enum ChallengeHeuristic{Random, Weighted};
69 
70  Parameter();
71 
72  // general options
73  bool integerConstraintNodeVar_; // use integer constraints for node variables
74  bool integerConstraintFactorVar_; // use integer constraints for factor variables
75  bool useSoftConstraints_; // if constraint factors are present in the model add them as soft constraints e.g. treat them as normal factors
76  bool useFunctionTransfer_; // use function transfer if available to generate more efficient lp models
77  bool mergeParallelFactors_; // merge factors which are connected to the same set of variables
78  bool nameConstraints_; // create unique names for the linear constraints added to the model (might be helpful for debugging models)
79  Relaxation relaxation_; // relaxation method
80  size_t maxNumIterations_; // maximum number of tightening iterations (infinite if set to 0)
81  size_t maxNumConstraintsPerIter_; // maximum number of added constraints per tightening iteration (all if set to 0)
82  ChallengeHeuristic challengeHeuristic_; // heuristic on how to select violated constraints
83  ValueType tolerance_; // tolerance for violation of linear constraints
84  };
85 
86  // public member functions
87  virtual const GraphicalModelType& graphicalModel() const;
88  virtual InferenceTermination infer();
89  template<class VISITOR_TYPE>
90  InferenceTermination infer(VISITOR_TYPE& visitor);
91  virtual ValueType bound() const;
92  virtual ValueType value() const;
93  virtual InferenceTermination arg(std::vector<LabelType>& x, const size_t N = 1) const;
94 
95 protected:
96  // structs
97  struct ConstraintStorage {
98  std::vector<SolverIndexType> variableIDs_;
99  std::vector<SolverValueType> coefficients_;
100  SolverValueType bound_;
101  typename LinearConstraintType::LinearConstraintOperatorValueType operator_;
102  std::string name_;
103  };
104 
105  // protected typedefs
106  typedef typename std::list<ConstraintStorage> InactiveConstraintsListType;
107  typedef typename InactiveConstraintsListType::iterator InactiveConstraintsListIteratorType;
108  typedef std::pair<IndexType, const LinearConstraintType*> FactorIndexConstraintPointerPairType;
109  typedef std::pair<InactiveConstraintsListIteratorType, FactorIndexConstraintPointerPairType> InactiveConstraintFactorConstraintPairType;
110  typedef std::multimap<double, InactiveConstraintFactorConstraintPairType> SortedViolatedConstraintsListType;
111 
112  // functors
113  struct GetIndicatorVariablesOrderBeginFunctor {
114  // storage
115  IndicatorVariablesIteratorType indicatorVariablesOrderBegin_;
116  // operator()
117  template<class LINEAR_CONSTRAINT_FUNCTION_TYPE>
118  void operator()(const LINEAR_CONSTRAINT_FUNCTION_TYPE& linearConstraintFunction);
119  // helper
120  template<class FUNCTION_TYPE, bool IS_LINEAR_CONSTRAINT_FUNCTION>
121  struct GetIndicatorVariablesOrderBeginFunctor_impl {
122  static void getIndicatorVariablesOrderBeginFunctor_impl(GetIndicatorVariablesOrderBeginFunctor& myself, const FUNCTION_TYPE& function);
123  };
124  template<class FUNCTION_TYPE>
125  struct GetIndicatorVariablesOrderBeginFunctor_impl<FUNCTION_TYPE, true> {
126  static void getIndicatorVariablesOrderBeginFunctor_impl(GetIndicatorVariablesOrderBeginFunctor& myself, const FUNCTION_TYPE& function);
127  };
128  };
129  struct GetIndicatorVariablesOrderEndFunctor {
130  // storage
131  IndicatorVariablesIteratorType indicatorVariablesOrderEnd_;
132  // operator()
133  template<class LINEAR_CONSTRAINT_FUNCTION_TYPE>
134  void operator()(const LINEAR_CONSTRAINT_FUNCTION_TYPE& linearConstraintFunction);
135  // helper
136  template<class FUNCTION_TYPE, bool IS_LINEAR_CONSTRAINT_FUNCTION>
137  struct GetIndicatorVariablesOrderEndFunctor_impl {
138  static void getIndicatorVariablesOrderEndFunctor_impl(GetIndicatorVariablesOrderEndFunctor& myself, const FUNCTION_TYPE& function);
139  };
140  template<class FUNCTION_TYPE>
141  struct GetIndicatorVariablesOrderEndFunctor_impl<FUNCTION_TYPE, true> {
142  static void getIndicatorVariablesOrderEndFunctor_impl(GetIndicatorVariablesOrderEndFunctor& myself, const FUNCTION_TYPE& function);
143  };
144  };
145  struct GetLinearConstraintsBeginFunctor {
146  // storage
147  LinearConstraintsIteratorType linearConstraintsBegin_;
148  // operator()
149  template<class LINEAR_CONSTRAINT_FUNCTION_TYPE>
150  void operator()(const LINEAR_CONSTRAINT_FUNCTION_TYPE& linearConstraintFunction);
151  // helper
152  template<class FUNCTION_TYPE, bool IS_LINEAR_CONSTRAINT_FUNCTION>
153  struct GetLinearConstraintsBeginFunctor_impl {
154  static void getLinearConstraintsBeginFunctor_impl(GetLinearConstraintsBeginFunctor& myself, const FUNCTION_TYPE& function);
155  };
156  template<class FUNCTION_TYPE>
157  struct GetLinearConstraintsBeginFunctor_impl<FUNCTION_TYPE, true> {
158  static void getLinearConstraintsBeginFunctor_impl(GetLinearConstraintsBeginFunctor& myself, const FUNCTION_TYPE& function);
159  };
160  };
161  struct GetLinearConstraintsEndFunctor {
162  // storage
163  LinearConstraintsIteratorType linearConstraintsEnd_;
164  // operator()
165  template<class LINEAR_CONSTRAINT_FUNCTION_TYPE>
166  void operator()(const LINEAR_CONSTRAINT_FUNCTION_TYPE& linearConstraintFunction);
167  // helper
168  template<class FUNCTION_TYPE, bool IS_LINEAR_CONSTRAINT_FUNCTION>
169  struct GetLinearConstraintsEndFunctor_impl {
170  static void getLinearConstraintsEndFunctor_impl(GetLinearConstraintsEndFunctor& myself, const FUNCTION_TYPE& function);
171  };
172  template<class FUNCTION_TYPE>
173  struct GetLinearConstraintsEndFunctor_impl<FUNCTION_TYPE, true> {
174  static void getLinearConstraintsEndFunctor_impl(GetLinearConstraintsEndFunctor& myself, const FUNCTION_TYPE& function);
175  };
176  };
177  struct AddAllViolatedLinearConstraintsFunctor {
178  // storage
179  ValueType tolerance_;
180  IntegerSolutionSubsequenceIterator labelingBegin_;
181  bool violatedConstraintAdded_;
182  LPInferenceBaseType* lpInference_;
183  IndexType linearConstraintID_;
184  // operator()
185  template<class LINEAR_CONSTRAINT_FUNCTION_TYPE>
186  void operator()(const LINEAR_CONSTRAINT_FUNCTION_TYPE& linearConstraintFunction);
187  // helper
188  template<class FUNCTION_TYPE, bool IS_LINEAR_CONSTRAINT_FUNCTION>
189  struct AddAllViolatedLinearConstraintsFunctor_impl {
190  static void addAllViolatedLinearConstraintsFunctor_impl(AddAllViolatedLinearConstraintsFunctor& myself, const FUNCTION_TYPE& function);
191  };
192  template<class FUNCTION_TYPE>
193  struct AddAllViolatedLinearConstraintsFunctor_impl<FUNCTION_TYPE, true> {
194  static void addAllViolatedLinearConstraintsFunctor_impl(AddAllViolatedLinearConstraintsFunctor& myself, const FUNCTION_TYPE& function);
195  };
196  };
197  struct AddAllViolatedLinearConstraintsRelaxedFunctor {
198  // storage
199  ValueType tolerance_;
200  RelaxedSolutionSubsequenceIterator labelingBegin_;
201  bool violatedConstraintAdded_;
202  LPInferenceBaseType* lpInference_;
203  IndexType linearConstraintID_;
204  // operator()
205  template<class LINEAR_CONSTRAINT_FUNCTION_TYPE>
206  void operator()(const LINEAR_CONSTRAINT_FUNCTION_TYPE& linearConstraintFunction);
207  // helper
208  template<class FUNCTION_TYPE, bool IS_LINEAR_CONSTRAINT_FUNCTION>
209  struct AddAllViolatedLinearConstraintsRelaxedFunctor_impl {
210  static void addAllViolatedLinearConstraintsRelaxedFunctor_impl(AddAllViolatedLinearConstraintsRelaxedFunctor& myself, const FUNCTION_TYPE& function);
211  };
212  template<class FUNCTION_TYPE>
213  struct AddAllViolatedLinearConstraintsRelaxedFunctor_impl<FUNCTION_TYPE, true> {
214  static void addAllViolatedLinearConstraintsRelaxedFunctor_impl(AddAllViolatedLinearConstraintsRelaxedFunctor& myself, const FUNCTION_TYPE& function);
215  };
216  };
217 
218  // meta
219  // note: LinearConstraintFunctionTypeList might be an empty type list containing only meta::ListEnd elements.
220  // This happens if GM::FunctionTypeList does not contain any linear constraint function
221  typedef typename meta::GetLinearConstraintFunctionTypeList<typename GraphicalModelType::FunctionTypeList>::type LinearConstraintFunctionTypeList;
222 
223  // storage
224  const GraphicalModelType& gm_;
225  const Parameter parameter_;
226  ValueType constValue_;
227  std::vector<IndexType> unaryFactors_;
228  std::vector<IndexType> higherOrderFactors_;
229  std::vector<IndexType> linearConstraintFactors_;
230  std::vector<IndexType> transferableFactors_;
231  bool inferenceStarted_;
232  SolverIndexType numLPVariables_;
233  SolverIndexType numNodesLPVariables_;
234  SolverIndexType numFactorsLPVariables_;
235  SolverIndexType numLinearConstraintsLPVariables_;
236  SolverIndexType numTransferedFactorsLPVariables;
237  SolverIndexType numSlackVariables_;
238 
239  // lookup tables
240  std::vector<SolverIndexType> nodesLPVariablesOffset_;
241  std::vector<SolverIndexType> factorsLPVariablesOffset_;
242  // TODO The lookups might be faster by using hashmaps instead of std::map (requires C++11)
243  std::vector<std::map<const IndicatorVariableType, SolverIndexType> > linearConstraintsLPVariablesIndicesLookupTable_;
244  std::vector<std::map<const IndicatorVariableType, SolverIndexType> > transferedFactorsLPVariablesIndicesLookupTable_;
245  std::vector<std::vector<size_t> > linearConstraintLPVariablesSubsequenceIndices_;
246 
247  // cache
248  IndexType addLocalPolytopeFactorConstraintCachePreviousFactorID_;
249  marray::Marray<SolverIndexType> addLocalPolytopeFactorConstraintCacheFactorLPVariableIDs_;
250  InactiveConstraintsListType inactiveConstraints_;
251 
252  // protected member functions
253  // construction
254  LPInferenceBase(const GraphicalModelType& gm, const Parameter& parameter = Parameter()); // no instance of LPInferenceBase is allowed
255  virtual ~LPInferenceBase();
256 
257  // initialization
258  void sortFactors();
259  void countLPVariables();
260  void fillLinearConstraintLPVariablesSubsequenceIndices();
261  void setAccumulation();
262  void addLPVariables();
263  void createObjectiveFunction();
264  void addLocalPolytopeConstraints();
265  void addLoosePolytopeConstraints();
266  void addTightPolytopeConstraints();
267 
268  // LP variables mapping functions
269  SolverIndexType nodeLPVariableIndex(const IndexType nodeID, const LabelType label) const;
270  SolverIndexType factorLPVariableIndex(const IndexType factorID, const size_t labelingIndex) const;
271  template<class LABELING_ITERATOR_TYPE>
272  SolverIndexType factorLPVariableIndex(const IndexType factorID, LABELING_ITERATOR_TYPE labelingBegin, const LABELING_ITERATOR_TYPE labelingEnd) const;
273  template <class HIGHER_ORDER_FACTORS_MAP_TYPE, class INDICATOR_VARIABLES_MAP_TYPE>
274  bool getLPVariableIndexFromIndicatorVariable(const HIGHER_ORDER_FACTORS_MAP_TYPE& higherOrderFactorVariablesLookupTable, const INDICATOR_VARIABLES_MAP_TYPE& indicatorVariablesLookupTable, const IndicatorVariableType& indicatorVariable, const IndexType linearConstraintFactorIndex, SolverIndexType& lpVariableIndex) const;
275 
276  // constraints creation helper
277  void addLocalPolytopeVariableConstraint(const IndexType variableID, const bool addToModel);
278  void addLocalPolytopeFactorConstraint(const IndexType factor, const IndexType variable, const LabelType label, const bool addToModel);
279  void addIndicatorVariableConstraints(const IndexType factor, const IndicatorVariableType& indicatorVariable, const SolverIndexType indicatorVariableLPVariable, const bool addToModel);
280  void addLinearConstraint(const IndexType linearConstraintFactor, const LinearConstraintType& constraint);
281 
282  // inference helper
283  template <class VISITOR_TYPE>
284  InferenceTermination infer_impl_selectRelaxation(VISITOR_TYPE& visitor);
285  template <class VISITOR_TYPE, typename Parameter::Relaxation RELAXATION>
286  InferenceTermination infer_impl_selectHeuristic(VISITOR_TYPE& visitor);
287  template <class VISITOR_TYPE, typename Parameter::Relaxation RELAXATION, typename Parameter::ChallengeHeuristic HEURISTIC>
288  InferenceTermination infer_impl_selectIterations(VISITOR_TYPE& visitor);
289  template <class VISITOR_TYPE, typename Parameter::Relaxation RELAXATION, typename Parameter::ChallengeHeuristic HEURISTIC, bool USE_INFINITE_ITERATIONS>
290  InferenceTermination infer_impl_selectViolatedConstraints(VISITOR_TYPE& visitor);
291  template <class VISITOR_TYPE, typename Parameter::Relaxation RELAXATION, typename Parameter::ChallengeHeuristic HEURISTIC, bool USE_INFINITE_ITERATIONS, bool ADD_ALL_VIOLATED_CONSTRAINTS>
292  InferenceTermination infer_impl_selectLPType(VISITOR_TYPE& visitor);
293  template <class VISITOR_TYPE, typename Parameter::Relaxation RELAXATION, typename Parameter::ChallengeHeuristic HEURISTIC, bool USE_INFINITE_ITERATIONS, bool ADD_ALL_VIOLATED_CONSTRAINTS, bool USE_INTEGER_CONSTRAINTS>
294  InferenceTermination infer_impl(VISITOR_TYPE& visitor);
295  template <typename Parameter::Relaxation RELAXATION, typename Parameter::ChallengeHeuristic HEURISTIC, bool ADD_ALL_VIOLATED_CONSTRAINTS>
296  bool tightenPolytope();
297  template <typename Parameter::Relaxation RELAXATION, typename Parameter::ChallengeHeuristic HEURISTIC, bool ADD_ALL_VIOLATED_CONSTRAINTS>
298  bool tightenPolytopeRelaxed();
299  void checkInactiveConstraint(const ConstraintStorage& constraint, double& weight) const;
300  void addInactiveConstraint(const ConstraintStorage& constraint);
301 
302  // friends
303  template <class LP_INFERENCE_BASE_TYPE, typename LP_INFERENCE_BASE_TYPE::Parameter::ChallengeHeuristic HEURISTIC>
304  friend struct AddViolatedLinearConstraintsFunctor;
305  template <class LP_INFERENCE_BASE_TYPE, typename LP_INFERENCE_BASE_TYPE::Parameter::ChallengeHeuristic HEURISTIC>
306  friend struct AddViolatedLinearConstraintsRelaxedFunctor;
307 };
308 
309 template <class LP_INFERENCE_BASE_TYPE, typename LP_INFERENCE_BASE_TYPE::Parameter::ChallengeHeuristic HEURISTIC>
310 struct AddViolatedLinearConstraintsFunctor {
311  // storage
312  typename LP_INFERENCE_BASE_TYPE::ValueType tolerance_;
313  typename LP_INFERENCE_BASE_TYPE::IntegerSolutionSubsequenceIterator labelingBegin_;
314  size_t numConstraintsAdded_;
315  LP_INFERENCE_BASE_TYPE* lpInference_;
316  typename LP_INFERENCE_BASE_TYPE::IndexType linearConstraintID_;
317  typename LP_INFERENCE_BASE_TYPE::SortedViolatedConstraintsListType* sortedViolatedConstraintsList_;
318  // operator()
319  template<class LINEAR_CONSTRAINT_FUNCTION_TYPE>
320  void operator()(const LINEAR_CONSTRAINT_FUNCTION_TYPE& linearConstraintFunction);
321  // helper
322  template<class FUNCTION_TYPE, bool IS_LINEAR_CONSTRAINT_FUNCTION>
323  struct AddViolatedLinearConstraintsFunctor_impl {
324  static void addViolatedLinearConstraintsFunctor_impl(AddViolatedLinearConstraintsFunctor<LP_INFERENCE_BASE_TYPE, HEURISTIC>& myself, const FUNCTION_TYPE& function);
325  };
326  template<class FUNCTION_TYPE>
327  struct AddViolatedLinearConstraintsFunctor_impl<FUNCTION_TYPE, true> {
328  static void addViolatedLinearConstraintsFunctor_impl(AddViolatedLinearConstraintsFunctor<LP_INFERENCE_BASE_TYPE, HEURISTIC>& myself, const FUNCTION_TYPE& function);
329  };
330 };
331 template <class LP_INFERENCE_BASE_TYPE, typename LP_INFERENCE_BASE_TYPE::Parameter::ChallengeHeuristic HEURISTIC>
332 struct AddViolatedLinearConstraintsRelaxedFunctor {
333  // storage
334  typename LP_INFERENCE_BASE_TYPE::ValueType tolerance_;
335  typename LP_INFERENCE_BASE_TYPE::RelaxedSolutionSubsequenceIterator labelingBegin_;
336  size_t numConstraintsAdded_;
337  LP_INFERENCE_BASE_TYPE* lpInference_;
338  typename LP_INFERENCE_BASE_TYPE::IndexType linearConstraintID_;
339  typename LP_INFERENCE_BASE_TYPE::SortedViolatedConstraintsListType* sortedViolatedConstraintsList_;
340  // operator()
341  template<class LINEAR_CONSTRAINT_FUNCTION_TYPE>
342  void operator()(const LINEAR_CONSTRAINT_FUNCTION_TYPE& linearConstraintFunction);
343  // helper
344  template<class FUNCTION_TYPE, bool IS_LINEAR_CONSTRAINT_FUNCTION>
345  struct AddViolatedLinearConstraintsRelaxedFunctor_impl {
346  static void addViolatedLinearConstraintsRelaxedFunctor_impl(AddViolatedLinearConstraintsRelaxedFunctor<LP_INFERENCE_BASE_TYPE, HEURISTIC>& myself, const FUNCTION_TYPE& function);
347  };
348  template<class FUNCTION_TYPE>
349  struct AddViolatedLinearConstraintsRelaxedFunctor_impl<FUNCTION_TYPE, true> {
350  static void addViolatedLinearConstraintsRelaxedFunctor_impl(AddViolatedLinearConstraintsRelaxedFunctor<LP_INFERENCE_BASE_TYPE, HEURISTIC>& myself, const FUNCTION_TYPE& function);
351  };
352 };
353 
354 /***********************
355  * class documentation *
356  **********************/
1748 /******************
1749  * implementation *
1750  *****************/
1751 template <class LP_INFERENCE_TYPE>
1752 inline LPInferenceBase<LP_INFERENCE_TYPE>::Parameter::Parameter()
1753  : SolverParameterType(), integerConstraintNodeVar_(false),
1754  integerConstraintFactorVar_(false), useSoftConstraints_(false),
1755  useFunctionTransfer_(false), mergeParallelFactors_(false),
1756  nameConstraints_(false), relaxation_(LocalPolytope),
1757  maxNumIterations_(1000), maxNumConstraintsPerIter_(0),
1758  challengeHeuristic_(Random), tolerance_(OPENGM_FLOAT_TOL) {
1759 
1760 }
1761 
1762 template <class LP_INFERENCE_TYPE>
1763 inline const typename LPInferenceBase<LP_INFERENCE_TYPE>::GraphicalModelType& LPInferenceBase<LP_INFERENCE_TYPE>::graphicalModel() const {
1764  return gm_;
1765 }
1766 
1767 template <class LP_INFERENCE_TYPE>
1768 inline InferenceTermination LPInferenceBase<LP_INFERENCE_TYPE>::infer() {
1769  EmptyVisitorType visitor;
1770  return infer(visitor);
1771 }
1772 
1773 template <class LP_INFERENCE_TYPE>
1774 template<class VISITOR_TYPE>
1775 inline InferenceTermination LPInferenceBase<LP_INFERENCE_TYPE>::infer(VISITOR_TYPE& visitor) {
1776  // Inference is performed in the method infer_impl(). Therefore appropriate
1777  // template parameters have to be selected. This is done by the
1778  // infer_impl_select... methods.
1779  return infer_impl_selectRelaxation(visitor);
1780 }
1781 
1782 template <class LP_INFERENCE_TYPE>
1783 inline typename LPInferenceBase<LP_INFERENCE_TYPE>::ValueType LPInferenceBase<LP_INFERENCE_TYPE>::bound() const {
1784  if(inferenceStarted_) {
1785  return static_cast<const LPInferenceType*>(this)->objectiveFunctionValueBound() + constValue_;
1786  }
1787  else{
1788  return AccumulationType::template ineutral<ValueType>();
1789  }
1790 }
1791 
1792 template <class LP_INFERENCE_TYPE>
1793 inline typename LPInferenceBase<LP_INFERENCE_TYPE>::ValueType LPInferenceBase<LP_INFERENCE_TYPE>::value() const {
1794  std::vector<LabelType> states;
1795  arg(states);
1796  return gm_.evaluate(states);
1797 }
1798 
1799 template <class LP_INFERENCE_TYPE>
1800 inline InferenceTermination LPInferenceBase<LP_INFERENCE_TYPE>::arg(std::vector<LabelType>& x, const size_t N) const {
1801  x.resize(gm_.numberOfVariables());
1802  if(inferenceStarted_) {
1803  SolverSolutionIteratorType solutionIterator = static_cast<const LPInferenceType*>(this)->solutionBegin();
1804  for(IndexType node = 0; node < gm_.numberOfVariables(); ++node) {
1805  SolverIndexType currentNodeLPVariable = nodesLPVariablesOffset_[node];
1806  SolverValueType bestValue = solutionIterator[currentNodeLPVariable];
1807  LabelType state = 0;
1808  for(LabelType i = 1; i < gm_.numberOfLabels(node); ++i) {
1809  ++currentNodeLPVariable;
1810  const SolverValueType currentValue = solutionIterator[currentNodeLPVariable];
1811  if(currentValue > bestValue) {
1812  bestValue = currentValue;
1813  state = i;
1814  }
1815  }
1816  x[node] = state;
1817  }
1818  return NORMAL;
1819  } else {
1820  for(IndexType node = 0; node < gm_.numberOfVariables(); ++node) {
1821  x[node] = 0;
1822  }
1823  return UNKNOWN;
1824  }
1825 }
1826 
1827 template <class LP_INFERENCE_TYPE>
1828 inline LPInferenceBase<LP_INFERENCE_TYPE>::LPInferenceBase(const GraphicalModelType& gm, const Parameter& parameter)
1829  : gm_(gm), parameter_(parameter), constValue_(0.0), unaryFactors_(),
1830  higherOrderFactors_(), linearConstraintFactors_(), transferableFactors_(),
1831  inferenceStarted_(false), numLPVariables_(0), numNodesLPVariables_(0),
1832  numFactorsLPVariables_(0), numLinearConstraintsLPVariables_(0),
1833  numTransferedFactorsLPVariables(0), numSlackVariables_(0),
1834  nodesLPVariablesOffset_(gm_.numberOfVariables()),
1835  factorsLPVariablesOffset_(gm_.numberOfFactors()),
1836  linearConstraintsLPVariablesIndicesLookupTable_(),
1837  transferedFactorsLPVariablesIndicesLookupTable_(),
1838  linearConstraintLPVariablesSubsequenceIndices_(),
1839  addLocalPolytopeFactorConstraintCachePreviousFactorID_(gm_.numberOfFactors()),
1840  addLocalPolytopeFactorConstraintCacheFactorLPVariableIDs_(),
1841  inactiveConstraints_() {
1842  if(!opengm::meta::Compare<OperatorType, opengm::Adder>::value) {
1843  throw RuntimeError("This implementation does only supports Min-Sum-Semiring and Max-Sum-Semiring.");
1844  }
1845  // sort factors
1846  sortFactors();
1847 
1848  // count number of required LP variables
1849  countLPVariables();
1850 
1851  // fill subsequence look up table for linear constraints
1852  fillLinearConstraintLPVariablesSubsequenceIndices();
1853 
1854  // set accumulation
1855  setAccumulation();
1856 
1857  // add variables
1858  addLPVariables();
1859 
1860  // create objective function
1861  createObjectiveFunction();
1862 
1863  // add constraints
1864  switch(parameter_.relaxation_){
1865  case Parameter::LocalPolytope : {
1866  addLocalPolytopeConstraints();
1867  break;
1868  }
1869  case Parameter::LoosePolytope : {
1870  addLoosePolytopeConstraints();
1871  break;
1872  }
1873  case Parameter::TightPolytope: {
1874  addTightPolytopeConstraints();
1875  break;
1876  }
1877  default : {
1878  throw RuntimeError("Unknown Relaxation");
1879  }
1880  }
1881 
1882  // Tell child class we are finished with adding constraints
1883  static_cast<LPInferenceType*>(this)->addConstraintsFinished();
1884 
1885  // clear cache (only needed durig construction)
1886  addLocalPolytopeFactorConstraintCacheFactorLPVariableIDs_ = marray::Marray<SolverIndexType>();
1887  addLocalPolytopeFactorConstraintCachePreviousFactorID_ = gm_.numberOfFactors();
1888 }
1889 
1890 template <class LP_INFERENCE_TYPE>
1891 inline LPInferenceBase<LP_INFERENCE_TYPE>::~LPInferenceBase() {
1892 
1893 }
1894 
1895 template <class LP_INFERENCE_TYPE>
1896 inline void LPInferenceBase<LP_INFERENCE_TYPE>::sortFactors() {
1897  typename LPFunctionTransferType::IsTransferableFunctor isTransferableFunctor;
1898  for(IndexType factorIndex = 0; factorIndex < gm_.numberOfFactors(); ++factorIndex){
1899  gm_[factorIndex].callFunctor(isTransferableFunctor);
1900  if((!parameter_.useSoftConstraints_) && gm_[factorIndex].isLinearConstraint()) {
1901  linearConstraintFactors_.push_back(factorIndex);
1902  } else if(parameter_.useFunctionTransfer_ && isTransferableFunctor.isTransferable_) {
1903  transferableFactors_.push_back(factorIndex);
1904  } else if(gm_[factorIndex].numberOfVariables() == 0) {
1905  const LabelType l = 0;
1906  constValue_ += gm_[factorIndex](&l);
1907  } else if(gm_[factorIndex].numberOfVariables() == 1) {
1908  unaryFactors_.push_back(factorIndex);
1909  } else if(gm_[factorIndex].numberOfVariables() > 1) {
1910  higherOrderFactors_.push_back(factorIndex);
1911  }
1912  }
1913 }
1914 
1915 template <class LP_INFERENCE_TYPE>
1916 inline void LPInferenceBase<LP_INFERENCE_TYPE>::countLPVariables() {
1917  // number of node LP variables
1918  for(IndexType node = 0; node < gm_.numberOfVariables(); ++node){
1919  numNodesLPVariables_ += gm_.numberOfLabels(node);
1920  nodesLPVariablesOffset_[node] = numLPVariables_;
1921  numLPVariables_ += gm_.numberOfLabels(node);
1922  }
1923 
1924  // set unary factors offset
1925  for(IndexType i = 0; i < unaryFactors_.size(); ++i) {
1926  const IndexType factorIndex = unaryFactors_[i];
1927  const IndexType node = gm_[factorIndex].variableIndex(0);
1928  factorsLPVariablesOffset_[factorIndex] = nodesLPVariablesOffset_[node];
1929  }
1930 
1931  // number of factor LP variables
1932  // lookup table to search for parallel factors
1933  // TODO The lookup might be faster by using a hashmap (requires C++11)
1934  std::map<std::vector<IndexType>, IndexType> higherOrderFactorVariablesLookupTable;
1935  for(IndexType i = 0; i < higherOrderFactors_.size(); ++i) {
1936  const IndexType factorIndex = higherOrderFactors_[i];
1937  bool duplicate = false;
1938  if(parameter_.mergeParallelFactors_) {
1939  // check if factor with same variables is already present in the model
1940  std::vector<IndexType> currentFactorVariables(gm_[factorIndex].numberOfVariables());
1941  for(IndexType j = 0; j < gm_[factorIndex].numberOfVariables(); ++j) {
1942  currentFactorVariables[j] = gm_[factorIndex].variableIndex(j);
1943  }
1944  const typename std::map<std::vector<IndexType>, IndexType>::const_iterator iter = higherOrderFactorVariablesLookupTable.find(currentFactorVariables);
1945  if(iter != higherOrderFactorVariablesLookupTable.end()) {
1946  // parallel factor found
1947  factorsLPVariablesOffset_[factorIndex] = factorsLPVariablesOffset_[iter->second];
1948  duplicate = true;
1949  } else {
1950  higherOrderFactorVariablesLookupTable[currentFactorVariables] = factorIndex;
1951  }
1952  }
1953  if(!duplicate) {
1954  const size_t currentSize = gm_[factorIndex].size();
1955  numFactorsLPVariables_ += currentSize;
1956  factorsLPVariablesOffset_[factorIndex] = numLPVariables_;
1957  numLPVariables_ += currentSize;
1958  }
1959  }
1960 
1961  OPENGM_ASSERT(numLPVariables_ == numNodesLPVariables_ + numFactorsLPVariables_);
1962 
1963  // count linear constraint variables
1964  // lookup table to search for parallel indicator variables
1965  // TODO The lookup might be faster by using a hashmap (requires C++11)
1966  std::map<std::pair<typename IndicatorVariableType::LogicalOperatorType, std::vector<std::pair<IndexType, LabelType> > >, SolverIndexType> linearConstraintIndicatorVariablesLookupTable;
1967  GetIndicatorVariablesOrderBeginFunctor getIndicatorVariablesOrderBegin;
1968  GetIndicatorVariablesOrderEndFunctor getIndicatorVariablesOrderEnd;
1969  for(IndexType i = 0; i < linearConstraintFactors_.size(); ++i) {
1970  const IndexType currentLinearConstraintFactorIndex = linearConstraintFactors_[i];
1971  factorsLPVariablesOffset_[currentLinearConstraintFactorIndex] = numLPVariables_;
1972  gm_[currentLinearConstraintFactorIndex].callFunctor(getIndicatorVariablesOrderBegin);
1973  IndicatorVariablesIteratorType currentIndicatorVariablesBegin = getIndicatorVariablesOrderBegin.indicatorVariablesOrderBegin_;
1974  gm_[currentLinearConstraintFactorIndex].callFunctor(getIndicatorVariablesOrderEnd);
1975  const IndicatorVariablesIteratorType currentIndicatorVariablesEnd = getIndicatorVariablesOrderEnd.indicatorVariablesOrderEnd_;
1976 
1977  linearConstraintsLPVariablesIndicesLookupTable_.push_back(std::map<const IndicatorVariableType, SolverIndexType>());
1978  const size_t numIndicatorVariables = std::distance(currentIndicatorVariablesBegin, currentIndicatorVariablesEnd);
1979  for(size_t j = 0; j < numIndicatorVariables; ++j) {
1980  const IndicatorVariableType& currentIndicatorVariable = *currentIndicatorVariablesBegin;
1981 
1982  SolverIndexType lpVariableIndex = std::numeric_limits<SolverIndexType>::max();
1983  const bool matchingLPVariableIndexFound = getLPVariableIndexFromIndicatorVariable(higherOrderFactorVariablesLookupTable, linearConstraintIndicatorVariablesLookupTable, currentIndicatorVariable, currentLinearConstraintFactorIndex, lpVariableIndex);
1984 
1985  if(matchingLPVariableIndexFound) {
1986  linearConstraintsLPVariablesIndicesLookupTable_.back()[currentIndicatorVariable] = lpVariableIndex;
1987  } else {
1988  // new LP variable required
1989  linearConstraintsLPVariablesIndicesLookupTable_.back()[currentIndicatorVariable] = numLPVariables_;
1990  const size_t currentIndicatorVariableSize = std::distance(currentIndicatorVariable.begin(), currentIndicatorVariable.end());
1991  std::vector<std::pair<IndexType, LabelType> > currentVariableLabelPairs(currentIndicatorVariableSize);
1992  for(size_t k = 0; k < currentIndicatorVariableSize; ++k) {
1993  currentVariableLabelPairs[k] = std::pair<IndexType, LabelType>(gm_[currentLinearConstraintFactorIndex].variableIndex((currentIndicatorVariable.begin() + k)->first), (currentIndicatorVariable.begin() + k)->second);
1994  }
1995  linearConstraintIndicatorVariablesLookupTable[make_pair(currentIndicatorVariable.getLogicalOperatorType(), currentVariableLabelPairs)] = numLPVariables_;
1996  ++numLinearConstraintsLPVariables_;
1997  ++numLPVariables_;
1998  }
1999  ++currentIndicatorVariablesBegin;
2000  }
2001  OPENGM_ASSERT(currentIndicatorVariablesBegin == currentIndicatorVariablesEnd);
2002  }
2003 
2004  OPENGM_ASSERT(linearConstraintFactors_.size() == linearConstraintsLPVariablesIndicesLookupTable_.size());
2005  OPENGM_ASSERT(numLPVariables_ == numNodesLPVariables_ + numFactorsLPVariables_ + numLinearConstraintsLPVariables_);
2006 
2007  // count lp variables for transferable factors
2008  typename LPFunctionTransferType::NumSlackVariablesFunctor numSlackVariablesFunctor;
2009  typename LPFunctionTransferType::GetIndicatorVariablesFunctor getIndicatorVariablesFunctor;
2010  for(IndexType i = 0; i < transferableFactors_.size(); ++i) {
2011  const IndexType currentTransferableFactorIndex = transferableFactors_[i];
2012  factorsLPVariablesOffset_[currentTransferableFactorIndex] = numLPVariables_;
2013 
2014  // get number of slack variables
2015  gm_[currentTransferableFactorIndex].callFunctor(numSlackVariablesFunctor);
2016 
2017  IndexType currentNumSlackVariables = 0;
2018 
2019  transferedFactorsLPVariablesIndicesLookupTable_.push_back(std::map<const IndicatorVariableType, SolverIndexType>());
2020 
2021  // get indicator variables of
2022  IndicatorVariablesContainerType currentIndicatorVariables;
2023  getIndicatorVariablesFunctor.variables_ = &currentIndicatorVariables;
2024  gm_[currentTransferableFactorIndex].callFunctor(getIndicatorVariablesFunctor);
2025 
2026  // fill transferedFactorsLPVariablesIndicesLookupTable_
2027  for(IndicatorVariablesIteratorType iter = currentIndicatorVariables.begin(); iter != currentIndicatorVariables.end(); ++iter) {
2028  const IndicatorVariableType& currentIndicatorVariable = *iter;
2029  const size_t currentIndicatorVariableSize = std::distance(currentIndicatorVariable.begin(), currentIndicatorVariable.end());
2030 
2031  if(currentIndicatorVariableSize == 1) {
2032  if(currentIndicatorVariable.begin()->first >= gm_[currentTransferableFactorIndex].numberOfVariables()) {
2033  // slack variable
2034  transferedFactorsLPVariablesIndicesLookupTable_.back()[currentIndicatorVariable] = numSlackVariables_ + currentNumSlackVariables; // note: slack variables indices will be shifted to the end of the indices later
2035  ++currentNumSlackVariables;
2036  continue;
2037  }
2038  }
2039 
2040  SolverIndexType lpVariableIndex;
2041  const bool matchingLPVariableIndexFound = getLPVariableIndexFromIndicatorVariable(higherOrderFactorVariablesLookupTable, linearConstraintIndicatorVariablesLookupTable, currentIndicatorVariable, currentTransferableFactorIndex, lpVariableIndex);
2042 
2043  if(matchingLPVariableIndexFound) {
2044  transferedFactorsLPVariablesIndicesLookupTable_.back()[currentIndicatorVariable] = lpVariableIndex;
2045  } else {
2046  // new LP variable required
2047  transferedFactorsLPVariablesIndicesLookupTable_.back()[currentIndicatorVariable] = numLPVariables_;
2048  const size_t currentIndicatorVariableSize = std::distance(currentIndicatorVariable.begin(), currentIndicatorVariable.end());
2049  std::vector<std::pair<IndexType, LabelType> > currentVariableLabelPairs(currentIndicatorVariableSize);
2050  for(size_t j = 0; j < currentIndicatorVariableSize; ++j) {
2051  currentVariableLabelPairs[j] = std::pair<IndexType, LabelType>(gm_[currentTransferableFactorIndex].variableIndex((currentIndicatorVariable.begin() + j)->first), (currentIndicatorVariable.begin() + j)->second);
2052  }
2053  linearConstraintIndicatorVariablesLookupTable[make_pair(currentIndicatorVariable.getLogicalOperatorType(), currentVariableLabelPairs)] = numLPVariables_;
2054  ++numTransferedFactorsLPVariables;
2055  ++numLPVariables_;
2056  }
2057  }
2058 
2059  OPENGM_ASSERT(currentNumSlackVariables == numSlackVariablesFunctor.numSlackVariables_);
2060  numSlackVariables_ += numSlackVariablesFunctor.numSlackVariables_;
2061  }
2062 
2063  // update slack variables indices to shift their indices to the end (indices >= numLPVariables_)
2064  typename LPFunctionTransferType::GetSlackVariablesOrderFunctor getSlackVariablesOrderFunctor;
2065  for(IndexType i = 0; i < transferableFactors_.size(); ++i) {
2066  const IndexType currentTransferableFactorIndex = transferableFactors_[i];
2067 
2068  // get slack variables
2069  IndicatorVariablesContainerType slackVariables;
2070  getSlackVariablesOrderFunctor.order_ = &slackVariables;
2071  gm_[currentTransferableFactorIndex].callFunctor(getSlackVariablesOrderFunctor);
2072 
2073  // shift indices
2074  for(IndicatorVariablesIteratorType iter = slackVariables.begin(); iter != slackVariables.end(); ++iter) {
2075  const IndicatorVariableType& currentSlackVariable = *iter;
2076  transferedFactorsLPVariablesIndicesLookupTable_[i][currentSlackVariable] += numLPVariables_;
2077  }
2078  }
2079 
2080  OPENGM_ASSERT(transferableFactors_.size() == transferedFactorsLPVariablesIndicesLookupTable_.size());
2081  OPENGM_ASSERT(numLPVariables_ == numNodesLPVariables_ + numFactorsLPVariables_ + numLinearConstraintsLPVariables_ + numTransferedFactorsLPVariables);
2082 }
2083 
2084 template <class LP_INFERENCE_TYPE>
2085 inline void LPInferenceBase<LP_INFERENCE_TYPE>::fillLinearConstraintLPVariablesSubsequenceIndices() {
2086  linearConstraintLPVariablesSubsequenceIndices_.resize(linearConstraintFactors_.size());
2087  if(parameter_.integerConstraintNodeVar_ || parameter_.integerConstraintFactorVar_) {
2088  for(size_t i = 0; i < linearConstraintFactors_.size(); ++i) {
2089  const IndexType currentFactor = linearConstraintFactors_[i];
2090  const size_t numVariables = gm_[currentFactor].numberOfVariables();
2091  linearConstraintLPVariablesSubsequenceIndices_[i].resize(numVariables);
2092  for(size_t j = 0; j < numVariables; ++j) {
2093  linearConstraintLPVariablesSubsequenceIndices_[i][j] = gm_[currentFactor].variableIndex(j);
2094  }
2095  }
2096  } else {
2097  GetIndicatorVariablesOrderBeginFunctor getIndicatorVariablesOrderBegin;
2098  GetIndicatorVariablesOrderEndFunctor getIndicatorVariablesOrderEnd;
2099  for(size_t i = 0; i < linearConstraintFactors_.size(); ++i) {
2100  const IndexType currentFactor = linearConstraintFactors_[i];
2101  gm_[currentFactor].callFunctor(getIndicatorVariablesOrderBegin);
2102  gm_[currentFactor].callFunctor(getIndicatorVariablesOrderEnd);
2103  const IndicatorVariablesIteratorType currentIndicatorVariablesEnd = getIndicatorVariablesOrderEnd.indicatorVariablesOrderEnd_;
2104  for(IndicatorVariablesIteratorType iter = getIndicatorVariablesOrderBegin.indicatorVariablesOrderBegin_; iter != currentIndicatorVariablesEnd; ++iter) {
2105  linearConstraintLPVariablesSubsequenceIndices_[i].push_back(linearConstraintsLPVariablesIndicesLookupTable_[i][*iter]);
2106  }
2107  }
2108  }
2109 }
2110 
2111 template <class LP_INFERENCE_TYPE>
2112 inline void LPInferenceBase<LP_INFERENCE_TYPE>::setAccumulation() {
2113  if(meta::Compare<AccumulationType, Minimizer>::value) {
2114  static_cast<LPInferenceType*>(this)->setObjective(LPInferenceType::Minimize);
2115  } else if(meta::Compare<AccumulationType, Maximizer>::value) {
2116  static_cast<LPInferenceType*>(this)->setObjective(LPInferenceType::Maximize);
2117  } else {
2118  throw RuntimeError("This implementation of lp inference does only support Minimizer or Maximizer accumulators");
2119  }
2120 }
2121 
2122 template <class LP_INFERENCE_TYPE>
2123 inline void LPInferenceBase<LP_INFERENCE_TYPE>::addLPVariables() {
2124  if(parameter_.integerConstraintNodeVar_) {
2125  static_cast<LPInferenceType*>(this)->addBinaryVariables(numNodesLPVariables_);
2126  } else {
2127  static_cast<LPInferenceType*>(this)->addContinuousVariables(numNodesLPVariables_, 0.0, 1.0);
2128  }
2129 
2130  if(parameter_.integerConstraintFactorVar_) {
2131  static_cast<LPInferenceType*>(this)->addBinaryVariables(numFactorsLPVariables_);
2132  static_cast<LPInferenceType*>(this)->addBinaryVariables(numLinearConstraintsLPVariables_);
2133  static_cast<LPInferenceType*>(this)->addBinaryVariables(numTransferedFactorsLPVariables);
2134  } else {
2135  static_cast<LPInferenceType*>(this)->addContinuousVariables(numFactorsLPVariables_, 0.0, 1.0);
2136  static_cast<LPInferenceType*>(this)->addContinuousVariables(numLinearConstraintsLPVariables_, 0.0, 1.0);
2137  static_cast<LPInferenceType*>(this)->addContinuousVariables(numTransferedFactorsLPVariables, 0.0, 1.0);
2138  }
2139 
2140  // add slack variables
2141  static_cast<LPInferenceType*>(this)->addContinuousVariables(numSlackVariables_, 0.0, LPInferenceType::infinity());
2142 }
2143 
2144 template <class LP_INFERENCE_TYPE>
2145 inline void LPInferenceBase<LP_INFERENCE_TYPE>::createObjectiveFunction() {
2146  std::vector<SolverValueType> objective(numNodesLPVariables_ + numFactorsLPVariables_ + numLinearConstraintsLPVariables_ + numTransferedFactorsLPVariables + numSlackVariables_, 0.0);
2147 
2148  // node lp variables coefficients
2149  for(IndexType i = 0; i < unaryFactors_.size(); i++) {
2150  const IndexType factorIndex = unaryFactors_[i];
2151  const IndexType node = gm_[factorIndex].variableIndex(0);
2152  for(LabelType j = 0; j < gm_.numberOfLabels(node); j++) {
2153  objective[nodeLPVariableIndex(node, j)] += static_cast<SolverValueType>(gm_[factorIndex](&j));
2154  }
2155  }
2156 
2157  // factor lp variables coefficients
2158  for(IndexType i = 0; i < higherOrderFactors_.size(); i++) {
2159  const IndexType factorIndex = higherOrderFactors_[i];
2160  // copy values
2161  std::vector<ValueType> tempValues(gm_[factorIndex].size());
2162  gm_[factorIndex].copyValues(tempValues.begin());
2163  for(size_t j = 0; j < tempValues.size(); ++j) {
2164  objective[factorLPVariableIndex(factorIndex, j)] += static_cast<SolverValueType>(tempValues[j]);
2165  }
2166  }
2167 
2168  // slack variables of transformed factors
2169  typename LPFunctionTransferType::GetSlackVariablesOrderFunctor getSlackVariablesOrderFunctor;
2170  typename LPFunctionTransferType::GetSlackVariablesObjectiveCoefficientsFunctor getSlackVariablesObjectiveCoefficientsFunctor;
2171  for(IndexType i = 0; i < transferableFactors_.size(); ++i) {
2172  const IndexType currentTransferableFactorIndex = transferableFactors_[i];
2173 
2174  // get slack variables
2175  IndicatorVariablesContainerType slackVariables;
2176  getSlackVariablesOrderFunctor.order_ = &slackVariables;
2177  gm_[currentTransferableFactorIndex].callFunctor(getSlackVariablesOrderFunctor);
2178 
2179  // get coefficients
2180  typename LPFunctionTransferType::SlackVariablesObjectiveCoefficientsContainerType coefficients;
2181  getSlackVariablesObjectiveCoefficientsFunctor.coefficients_ = &coefficients;
2182  gm_[currentTransferableFactorIndex].callFunctor(getSlackVariablesObjectiveCoefficientsFunctor);
2183 
2184  OPENGM_ASSERT(coefficients.size() == slackVariables.size());
2185 
2186  // add coefficients
2187  for(size_t j = 0; j < slackVariables.size(); ++j) {
2188  const IndicatorVariableType& currentSlackVariable = slackVariables[j];
2189  const ValueType currentCoefficient = coefficients[j];
2190  const SolverIndexType currentSlackVariableLPVariableIndex = transferedFactorsLPVariablesIndicesLookupTable_[i][currentSlackVariable];
2191  objective[currentSlackVariableLPVariableIndex] += static_cast<SolverValueType>(currentCoefficient);
2192  }
2193  }
2194  static_cast<LPInferenceType*>(this)->setObjectiveValue(objective.begin(), objective.end());
2195 }
2196 
2197 template <class LP_INFERENCE_TYPE>
2198 inline void LPInferenceBase<LP_INFERENCE_TYPE>::addLocalPolytopeConstraints() {
2199  // \sum_i \mu_i = 1
2200  for(IndexType i = 0; i < gm_.numberOfVariables(); ++i) {
2201  addLocalPolytopeVariableConstraint(i, true);
2202  }
2203 
2204  // \sum_i \mu_{f;i_1,...,i_n} - \mu{b;j}= 0
2205  for(IndexType i = 0; i < higherOrderFactors_.size(); ++i) {
2206  const IndexType factorIndex = higherOrderFactors_[i];
2207  for(IndexType j = 0; j < gm_[factorIndex].numberOfVariables(); ++j) {
2208  const IndexType node = gm_[factorIndex].variableIndex(j);
2209  for(LabelType k = 0; k < gm_.numberOfLabels(node); k++) {
2210  addLocalPolytopeFactorConstraint(i, j, k, true);
2211  }
2212  }
2213  }
2214 
2215  // add constraints for linear constraint factor variables
2216  GetIndicatorVariablesOrderBeginFunctor getIndicatorVariablesOrderBegin;
2217  GetIndicatorVariablesOrderEndFunctor getIndicatorVariablesOrderEnd;
2218  for(IndexType i = 0; i < linearConstraintFactors_.size(); ++i) {
2219  gm_[linearConstraintFactors_[i]].callFunctor(getIndicatorVariablesOrderBegin);
2220  gm_[linearConstraintFactors_[i]].callFunctor(getIndicatorVariablesOrderEnd);
2221  const size_t linearConstraintNumIndicatorVariables = std::distance(getIndicatorVariablesOrderBegin.indicatorVariablesOrderBegin_, getIndicatorVariablesOrderEnd.indicatorVariablesOrderEnd_);
2222  for(size_t j = 0; j < linearConstraintNumIndicatorVariables; ++j) {
2223  const IndexType currentFactor = linearConstraintFactors_[i];
2224  const IndicatorVariableType& currentIndicatorVariable = getIndicatorVariablesOrderBegin.indicatorVariablesOrderBegin_[j];
2225  const SolverIndexType currentLPVariable = linearConstraintsLPVariablesIndicesLookupTable_[i][currentIndicatorVariable];
2226  addIndicatorVariableConstraints(currentFactor, currentIndicatorVariable, currentLPVariable, true);
2227  }
2228  }
2229 
2230  // add constraints for transfered factor variables
2231  typename LPFunctionTransferType::GetIndicatorVariablesFunctor getIndicatorVariablesFunctor;
2232  for(IndexType i = 0; i < transferableFactors_.size(); ++i) {
2233  typename LPFunctionTransferType::IndicatorVariablesContainerType currentIndicatorVariables;
2234  getIndicatorVariablesFunctor.variables_ = &currentIndicatorVariables;
2235  gm_[transferableFactors_[i]].callFunctor(getIndicatorVariablesFunctor);
2236  const size_t transformedFactorsNumIndicatorVariables = currentIndicatorVariables.size();
2237  for(size_t j = 0; j < transformedFactorsNumIndicatorVariables; ++j) {
2238  const IndexType currentFactor = transferableFactors_[i];
2239  const IndicatorVariableType& currentIndicatorVariable = currentIndicatorVariables[j];
2240  const SolverIndexType currentLPVariable = transferedFactorsLPVariablesIndicesLookupTable_[i][currentIndicatorVariable];
2241  addIndicatorVariableConstraints(currentFactor, currentIndicatorVariable, currentLPVariable, true);
2242  }
2243  }
2244 
2245  // add constraints for transfered factors
2246  typename LPFunctionTransferType::GetLinearConstraintsFunctor getLinearConstraintsFunctor;
2247  for(IndexType i = 0; i < transferableFactors_.size(); ++i) {
2248  const IndexType currentTransferableFactorIndex = transferableFactors_[i];
2249  // get constraints
2250  typename LPFunctionTransferType::LinearConstraintsContainerType constraints;
2251  getLinearConstraintsFunctor.constraints_ = &constraints;
2252  gm_[currentTransferableFactorIndex].callFunctor(getLinearConstraintsFunctor);
2253  for(size_t j = 0; j < constraints.size(); ++j) {
2254  const LinearConstraintType& currentConstraint = constraints[j];
2255  std::vector<SolverIndexType> lpVariables(std::distance(currentConstraint.indicatorVariablesBegin(), currentConstraint.indicatorVariablesEnd()));
2256  for(size_t k = 0; k < lpVariables.size(); ++k) {
2257  lpVariables[k] = transferedFactorsLPVariablesIndicesLookupTable_[i][currentConstraint.indicatorVariablesBegin()[k]];
2258  }
2259  switch(currentConstraint.getConstraintOperator()) {
2260  case LinearConstraintType::LinearConstraintOperatorType::LessEqual : {
2261  static_cast<LPInferenceType*>(this)->addLessEqualConstraint(lpVariables.begin(), lpVariables.end(), currentConstraint.coefficientsBegin(), static_cast<const SolverValueType>(currentConstraint.getBound()));
2262  break;
2263  }
2264  case LinearConstraintType::LinearConstraintOperatorType::Equal : {
2265  static_cast<LPInferenceType*>(this)->addEqualityConstraint(lpVariables.begin(), lpVariables.end(), currentConstraint.coefficientsBegin(), static_cast<const SolverValueType>(currentConstraint.getBound()));
2266  break;
2267  }
2268  default: {
2269  // default corresponds to LinearConstraintType::LinearConstraintOperatorType::GreaterEqual case
2270  static_cast<LPInferenceType*>(this)->addGreaterEqualConstraint(lpVariables.begin(), lpVariables.end(), currentConstraint.coefficientsBegin(), static_cast<const SolverValueType>(currentConstraint.getBound()));
2271  }
2272  }
2273  }
2274  }
2275 }
2276 
2277 template <class LP_INFERENCE_TYPE>
2278 inline void LPInferenceBase<LP_INFERENCE_TYPE>::addLoosePolytopeConstraints() {
2279  // \sum_i \mu_i = 1
2280  for(IndexType i = 0; i < gm_.numberOfVariables(); ++i) {
2281  addLocalPolytopeVariableConstraint(i, true);
2282  }
2283 
2284  // \sum_i \mu_{f;i_1,...,i_n} - \mu{b;j}= 0
2285  for(IndexType i = 0; i < higherOrderFactors_.size(); ++i) {
2286  const IndexType factorIndex = higherOrderFactors_[i];
2287  for(IndexType j = 0; j < gm_[factorIndex].numberOfVariables(); ++j) {
2288  const IndexType node = gm_[factorIndex].variableIndex(j);
2289  for(LabelType k = 0; k < gm_.numberOfLabels(node); k++) {
2290  addLocalPolytopeFactorConstraint(i, j, k, false);
2291  }
2292  }
2293  }
2294 
2295  // add constraints for linear constraint factor variables
2296  GetIndicatorVariablesOrderBeginFunctor getIndicatorVariablesOrderBegin;
2297  GetIndicatorVariablesOrderEndFunctor getIndicatorVariablesOrderEnd;
2298  for(IndexType i = 0; i < linearConstraintFactors_.size(); ++i) {
2299  gm_[linearConstraintFactors_[i]].callFunctor(getIndicatorVariablesOrderBegin);
2300  gm_[linearConstraintFactors_[i]].callFunctor(getIndicatorVariablesOrderEnd);
2301  const size_t linearConstraintNumIndicatorVariables = std::distance(getIndicatorVariablesOrderBegin.indicatorVariablesOrderBegin_, getIndicatorVariablesOrderEnd.indicatorVariablesOrderEnd_);
2302  for(size_t j = 0; j < linearConstraintNumIndicatorVariables; ++j) {
2303  const IndexType currentFactor = linearConstraintFactors_[i];
2304  const IndicatorVariableType& currentIndicatorVariable = getIndicatorVariablesOrderBegin.indicatorVariablesOrderBegin_[j];
2305  const SolverIndexType currentLPVariable = linearConstraintsLPVariablesIndicesLookupTable_[i][currentIndicatorVariable];
2306  addIndicatorVariableConstraints(currentFactor, currentIndicatorVariable, currentLPVariable, false);
2307  }
2308  }
2309 
2310  // add constraints for transfered factor variables
2311  typename LPFunctionTransferType::GetIndicatorVariablesFunctor getIndicatorVariablesFunctor;
2312  for(IndexType i = 0; i < transferableFactors_.size(); ++i) {
2313  typename LPFunctionTransferType::IndicatorVariablesContainerType currentIndicatorVariables;
2314  getIndicatorVariablesFunctor.variables_ = &currentIndicatorVariables;
2315  gm_[transferableFactors_[i]].callFunctor(getIndicatorVariablesFunctor);
2316  const size_t transformedFactorsNumIndicatorVariables = currentIndicatorVariables.size();
2317  for(size_t j = 0; j < transformedFactorsNumIndicatorVariables; ++j) {
2318  const IndexType currentFactor = transferableFactors_[i];
2319  const IndicatorVariableType& currentIndicatorVariable = currentIndicatorVariables[j];
2320  const SolverIndexType currentLPVariable = transferedFactorsLPVariablesIndicesLookupTable_[i][currentIndicatorVariable];
2321  addIndicatorVariableConstraints(currentFactor, currentIndicatorVariable, currentLPVariable, false);
2322  }
2323  }
2324 
2325  // add constraints for transfered factors
2326  typename LPFunctionTransferType::GetLinearConstraintsFunctor getLinearConstraintsFunctor;
2327  for(IndexType i = 0; i < transferableFactors_.size(); ++i) {
2328  const IndexType currentTransferableFactorIndex = transferableFactors_[i];
2329  // get constraints
2330  typename LPFunctionTransferType::LinearConstraintsContainerType constraints;
2331  getLinearConstraintsFunctor.constraints_ = &constraints;
2332  gm_[currentTransferableFactorIndex].callFunctor(getLinearConstraintsFunctor);
2333  for(size_t j = 0; j < constraints.size(); ++j) {
2334  const LinearConstraintType& currentConstraint = constraints[j];
2335  std::vector<SolverIndexType> lpVariables(std::distance(currentConstraint.indicatorVariablesBegin(), currentConstraint.indicatorVariablesEnd()));
2336  for(size_t k = 0; k < lpVariables.size(); ++k) {
2337  lpVariables[k] = transferedFactorsLPVariablesIndicesLookupTable_[i][currentConstraint.indicatorVariablesBegin()[k]];
2338  }
2339 
2340  std::stringstream constraintName;
2341  if(parameter_.nameConstraints_) {
2342  constraintName << "transfered factor " << currentTransferableFactorIndex << " constraint " << j << " of " << constraints.size();
2343  }
2344  ConstraintStorage constraint;
2345  constraint.variableIDs_ = lpVariables;
2346  constraint.coefficients_ = std::vector<SolverValueType>(currentConstraint.coefficientsBegin(), currentConstraint.coefficientsEnd());
2347  constraint.bound_ = currentConstraint.getBound();
2348  constraint.operator_ = currentConstraint.getConstraintOperator();
2349  constraint.name_ = constraintName.str();
2350  inactiveConstraints_.push_back(constraint);
2351  }
2352  }
2353 }
2354 
2355 template <class LP_INFERENCE_TYPE>
2356 inline void LPInferenceBase<LP_INFERENCE_TYPE>::addTightPolytopeConstraints() {
2357  addLocalPolytopeConstraints();
2358 
2359  // Add all linear constraints from all linear constraint functions
2360  GetLinearConstraintsBeginFunctor getLinearConstraintsBegin;
2361  GetLinearConstraintsEndFunctor getLinearConstraintsEnd;
2362  for(IndexType i = 0; i < linearConstraintFactors_.size(); ++i) {
2363  const IndexType currentLinearConstraintFactorIndex = linearConstraintFactors_[i];
2364  gm_[currentLinearConstraintFactorIndex].callFunctor(getLinearConstraintsBegin);
2365  LinearConstraintsIteratorType currentLinearConstraintsBegin = getLinearConstraintsBegin.linearConstraintsBegin_;
2366  gm_[currentLinearConstraintFactorIndex].callFunctor(getLinearConstraintsEnd);
2367  const LinearConstraintsIteratorType currentLinearConstraintsEnd = getLinearConstraintsEnd.linearConstraintsEnd_;
2368  while(currentLinearConstraintsBegin != currentLinearConstraintsEnd) {
2369  addLinearConstraint(i, *currentLinearConstraintsBegin);
2370  ++currentLinearConstraintsBegin;
2371  }
2372  }
2373 }
2374 
2375 template <class LP_INFERENCE_TYPE>
2376 inline typename LPInferenceBase<LP_INFERENCE_TYPE>::SolverIndexType LPInferenceBase<LP_INFERENCE_TYPE>::nodeLPVariableIndex(const IndexType nodeID, const LabelType label) const {
2377  OPENGM_ASSERT(nodeID < gm_.numberOfVariables());
2378  OPENGM_ASSERT(label < gm_.numberOfLabels(nodeID));
2379  return nodesLPVariablesOffset_[nodeID] + label;
2380 }
2381 
2382 template <class LP_INFERENCE_TYPE>
2383 inline typename LPInferenceBase<LP_INFERENCE_TYPE>::SolverIndexType LPInferenceBase<LP_INFERENCE_TYPE>::factorLPVariableIndex (const IndexType factorID, const size_t labelingIndex) const {
2384  OPENGM_ASSERT(factorID < gm_.numberOfFactors());
2385  OPENGM_ASSERT(labelingIndex < gm_[factorID].size());
2386 
2387  return factorsLPVariablesOffset_[factorID] + labelingIndex;
2388 }
2389 
2390 template <class LP_INFERENCE_TYPE>
2391 template<class LABELING_ITERATOR_TYPE>
2392 inline typename LPInferenceBase<LP_INFERENCE_TYPE>::SolverIndexType LPInferenceBase<LP_INFERENCE_TYPE>::factorLPVariableIndex(const IndexType factorID, LABELING_ITERATOR_TYPE labelingBegin, const LABELING_ITERATOR_TYPE labelingEnd) const {
2393  OPENGM_ASSERT(factorID < gm_.numberOfFactors());
2394  OPENGM_ASSERT(static_cast<IndexType>(std::distance(labelingBegin, labelingEnd)) == gm_[factorID].numberOfVariables());
2395 
2396  const size_t numVar = gm_[factorID].numberOfVariables();
2397  size_t labelingIndex = *labelingBegin;
2398  labelingBegin++;
2399  size_t strides = gm_[factorID].numberOfLabels(0);
2400  for(size_t i = 1; i < numVar; i++){
2401  OPENGM_ASSERT(*labelingBegin < gm_[factorID].numberOfLabels(i));
2402  labelingIndex += strides * (*labelingBegin);
2403  strides *= gm_[factorID].numberOfLabels(i);
2404  labelingBegin++;
2405  }
2406 
2407  OPENGM_ASSERT(labelingBegin == labelingEnd);
2408 
2409  return factorLPVariableIndex(factorID, labelingIndex);
2410 }
2411 
2412 template <class LP_INFERENCE_TYPE>
2413 template <class HIGHER_ORDER_FACTORS_MAP_TYPE, class INDICATOR_VARIABLES_MAP_TYPE>
2414 inline bool LPInferenceBase<LP_INFERENCE_TYPE>::getLPVariableIndexFromIndicatorVariable(const HIGHER_ORDER_FACTORS_MAP_TYPE& higherOrderFactorVariablesLookupTable, const INDICATOR_VARIABLES_MAP_TYPE& indicatorVariablesLookupTable, const IndicatorVariableType& indicatorVariable, const IndexType linearConstraintFactorIndex, SolverIndexType& lpVariableIndex) const {
2415  const size_t indicatorVariableSize = std::distance(indicatorVariable.begin(), indicatorVariable.end());
2416  OPENGM_ASSERT(indicatorVariableSize > 0);
2417 
2418  if(indicatorVariableSize == 1) {
2419  const IndexType currentNode = gm_[linearConstraintFactorIndex].variableIndex(indicatorVariable.begin()->first);
2420  const LabelType currentLabel = indicatorVariable.begin()->second;
2421  if(indicatorVariable.getLogicalOperatorType() == IndicatorVariableType::Not) {
2422  if(gm_.numberOfLabels(currentNode) == 2) {
2423  OPENGM_ASSERT(currentLabel < 2);
2424  // use second label as not variable
2425  lpVariableIndex = nodeLPVariableIndex(currentNode, currentLabel == 0 ? LabelType(1) : LabelType(0));
2426  return true;
2427  } else {
2428  return false;
2429  }
2430  } else {
2431  lpVariableIndex = nodeLPVariableIndex(currentNode, currentLabel);
2432  return true;
2433  }
2434  } else {
2435  // search if any factor has the same variable combination
2436  if(indicatorVariable.getLogicalOperatorType() == IndicatorVariableType::And) {
2437  std::vector<IndexType> currentVariables(indicatorVariableSize);
2438  std::vector<LabelType> currentLabeling(indicatorVariableSize);
2439  for(size_t i = 0; i < indicatorVariableSize; ++i) {
2440  currentVariables[i] = gm_[linearConstraintFactorIndex].variableIndex((indicatorVariable.begin() + i)->first);
2441  currentLabeling[i] = (indicatorVariable.begin() + i)->second;
2442  }
2443  const typename HIGHER_ORDER_FACTORS_MAP_TYPE::const_iterator iter = higherOrderFactorVariablesLookupTable.find(currentVariables);
2444  if(iter != higherOrderFactorVariablesLookupTable.end()) {
2445  // matching factor found
2446  lpVariableIndex = factorLPVariableIndex(iter->second, currentLabeling.begin(), currentLabeling.end());
2447  return true;
2448  }
2449  }
2450  // search if any previous linear constraint has the same variable combination
2451  std::vector<std::pair<IndexType, LabelType> > currentVariableLabelPairs(indicatorVariableSize);
2452  for(size_t i = 0; i < indicatorVariableSize; ++i) {
2453  currentVariableLabelPairs[i] = std::pair<IndexType, LabelType>(gm_[linearConstraintFactorIndex].variableIndex((indicatorVariable.begin() + i)->first), (indicatorVariable.begin() + i)->second);
2454  }
2455  const typename INDICATOR_VARIABLES_MAP_TYPE::const_iterator iter = indicatorVariablesLookupTable.find(make_pair(indicatorVariable.getLogicalOperatorType(), currentVariableLabelPairs));
2456  if(iter != indicatorVariablesLookupTable.end()) {
2457  // indicator variable with same variable label combination found
2458  lpVariableIndex = iter->second;
2459  return true;
2460  } else {
2461  return false;
2462  }
2463  }
2464 }
2465 
2466 template <class LP_INFERENCE_TYPE>
2467 inline void LPInferenceBase<LP_INFERENCE_TYPE>::addLocalPolytopeVariableConstraint(const IndexType variableID, const bool addToModel) {
2468  OPENGM_ASSERT(variableID < gm_.numberOfVariables());
2469  static std::vector<SolverIndexType> variableIDs;
2470  static std::vector<SolverValueType> coefficients;
2471 
2472  // \sum_i \mu_i = 1
2473  const LabelType size = gm_.numberOfLabels(variableID);
2474  if(variableIDs.size() != size) {
2475  variableIDs.resize(size);
2476  coefficients.resize(size, 1.0);
2477  }
2478  for(LabelType j = 0; j < size; j++) {
2479  variableIDs[j] = nodeLPVariableIndex(variableID, j);
2480  }
2481 
2482  std::stringstream constraintName;
2483  if(parameter_.nameConstraints_) {
2484  constraintName << "local polytope variable constraint of variable " << variableID;
2485  }
2486  if(addToModel) {
2487  static_cast<LPInferenceType*>(this)->addEqualityConstraint(variableIDs.begin(), variableIDs.end(), coefficients.begin(), 1.0, constraintName.str());
2488  } else {
2489  ConstraintStorage constraint;
2490  constraint.variableIDs_ = variableIDs;
2491  constraint.coefficients_ = coefficients;
2492  constraint.bound_ = 1.0;
2493  constraint.operator_ = LinearConstraintType::LinearConstraintOperatorType::Equal;
2494  constraint.name_ = constraintName.str();
2495  inactiveConstraints_.push_back(constraint);
2496  }
2497 }
2498 
2499 template <class LP_INFERENCE_TYPE>
2500 inline void LPInferenceBase<LP_INFERENCE_TYPE>::addLocalPolytopeFactorConstraint(const IndexType factor, const IndexType variable, const LabelType label, const bool addToModel) {
2501  OPENGM_ASSERT(factor < higherOrderFactors_.size());
2502  OPENGM_ASSERT(variable < gm_[higherOrderFactors_[factor]].numberOfVariables());
2503  OPENGM_ASSERT(label < gm_[higherOrderFactors_[factor]].shape(variable));
2504 
2505  static std::vector<SolverIndexType> variableIDs;
2506  static std::vector<SolverValueType> coefficients;
2507  if(addLocalPolytopeFactorConstraintCachePreviousFactorID_ != higherOrderFactors_[factor]) {
2508  // update lookup table
2509  addLocalPolytopeFactorConstraintCachePreviousFactorID_ = higherOrderFactors_[factor];
2510  addLocalPolytopeFactorConstraintCacheFactorLPVariableIDs_.resize(gm_[higherOrderFactors_[factor]].shapeBegin(), gm_[higherOrderFactors_[factor]].shapeEnd());
2511  SolverIndexType counter = factorLPVariableIndex(higherOrderFactors_[factor], 0);
2512  for(typename marray::Marray<SolverIndexType>::iterator factorLPVariableIDsIter = addLocalPolytopeFactorConstraintCacheFactorLPVariableIDs_.begin(); factorLPVariableIDsIter != addLocalPolytopeFactorConstraintCacheFactorLPVariableIDs_.end(); ++factorLPVariableIDsIter) {
2513  *factorLPVariableIDsIter = counter++;
2514  }
2515  }
2516 
2517  marray::View<SolverIndexType> view = addLocalPolytopeFactorConstraintCacheFactorLPVariableIDs_.boundView(variable, label);
2518  const IndexType node = gm_[higherOrderFactors_[factor]].variableIndex(variable);
2519  const size_t size = view.size() + 1;
2520  const size_t containerSize = variableIDs.size();
2521  if(containerSize != size) {
2522  variableIDs.resize(size);
2523  // reset coefficients
2524  if(containerSize > 0) {
2525  coefficients[containerSize - 1] = 1.0;
2526  }
2527  coefficients.resize(size, 1.0);
2528  coefficients[size - 1] = -1.0;
2529  }
2530  SolverIndexType currentVariableIDsIndex = 0;
2531  for(typename marray::View<SolverIndexType>::iterator viewIter = view.begin(); viewIter != view.end(); ++viewIter) {
2532  variableIDs[currentVariableIDsIndex] = *viewIter;
2533  currentVariableIDsIndex++;
2534  }
2535  OPENGM_ASSERT(static_cast<size_t>(currentVariableIDsIndex) == size - 1);
2536  variableIDs[size - 1] = nodeLPVariableIndex(node, label);
2537 
2538  std::stringstream constraintName;
2539  if(parameter_.nameConstraints_) {
2540  constraintName << "local polytope factor constraint of higher order factor " << factor << " variable " << variable << " and label " << label;
2541  }
2542  if(addToModel) {
2543  static_cast<LPInferenceType*>(this)->addEqualityConstraint(variableIDs.begin(), variableIDs.end(), coefficients.begin(), 0.0, constraintName.str());
2544  } else {
2545  ConstraintStorage constraint;
2546  constraint.variableIDs_ = variableIDs;
2547  constraint.coefficients_ = coefficients;
2548  constraint.bound_ = 0.0;
2549  constraint.operator_ = LinearConstraintType::LinearConstraintOperatorType::Equal;
2550  constraint.name_ = constraintName.str();
2551  inactiveConstraints_.push_back(constraint);
2552  }
2553 }
2554 
2555 template <class LP_INFERENCE_TYPE>
2556 inline void LPInferenceBase<LP_INFERENCE_TYPE>::addIndicatorVariableConstraints(const IndexType factor, const IndicatorVariableType& indicatorVariable, const SolverIndexType indicatorVariableLPVariable, const bool addToModel) {
2557  OPENGM_ASSERT(factor < gm_.numberOfFactors());
2558  OPENGM_ASSERT(indicatorVariableLPVariable < numLPVariables_ + numSlackVariables_);
2559  if(indicatorVariableLPVariable >= numLPVariables_) {
2560  // slack variable nothing to do.
2561  } else {
2562  if(indicatorVariableLPVariable >= factorsLPVariablesOffset_[factor]) {
2563  // new constraints needed
2564  OPENGM_ASSERT(std::distance(indicatorVariable.begin(), indicatorVariable.end()) > 0);
2565 
2566  const SolverIndexType numVariables = static_cast<const SolverIndexType>(std::distance(indicatorVariable.begin(), indicatorVariable.end()));
2567  if(numVariables == 1) {
2568  // Only Not requires a new variable if the IndicatorVariable has size 1
2569  OPENGM_ASSERT(indicatorVariable.getLogicalOperatorType() == IndicatorVariableType::Not);
2570  // Not: currentLPVariable + lpNodeVar(node; label) == 1.0
2571  std::vector<SolverValueType> coefficients(2, 1.0);
2572  std::vector<SolverIndexType> lpVariableIDs(2, indicatorVariableLPVariable);
2573  lpVariableIDs[0] = nodeLPVariableIndex(gm_[factor].variableIndex(indicatorVariable.begin()->first), indicatorVariable.begin()->second);
2574  std::stringstream constraintName;
2575  if(parameter_.nameConstraints_) {
2576  constraintName << "indicator variable constraint of factor " << factor << "of type Not for node" << indicatorVariable.begin()->first << " and label " << indicatorVariable.begin()->second;
2577  }
2578  if(addToModel) {
2579  static_cast<LPInferenceType*>(this)->addEqualityConstraint(lpVariableIDs.begin(), lpVariableIDs.end(), coefficients.begin(), 1.0, constraintName.str());
2580  } else {
2581  ConstraintStorage constraint;
2582  constraint.variableIDs_ = lpVariableIDs;
2583  constraint.coefficients_ = coefficients;
2584  constraint.bound_ = 1.0;
2585  constraint.operator_ = LinearConstraintType::LinearConstraintOperatorType::Equal;
2586  constraint.name_ = constraintName.str();
2587  inactiveConstraints_.push_back(constraint);
2588  }
2589  } else {
2590  OPENGM_ASSERT((indicatorVariable.getLogicalOperatorType() == IndicatorVariableType::And) || (indicatorVariable.getLogicalOperatorType() == IndicatorVariableType::Or) || (indicatorVariable.getLogicalOperatorType() == IndicatorVariableType::Not) )
2591 
2592  // And: currentLPVariable - lpNodeVar(node; label) <= 0.0 for all node label pairs of the indicator variable
2593  // Or: currentLPVariable - lpNodeVar(node; label) >= 0.0 for all node label pairs of the indicator variable
2594  // Not: currentLPVariable + lpNodeVar(node; label) <= 1.0 for all node label pairs of the indicator variable
2595  std::vector<SolverValueType> coefficients(2, 1.0);
2596  if((indicatorVariable.getLogicalOperatorType() == IndicatorVariableType::And) || (indicatorVariable.getLogicalOperatorType() == IndicatorVariableType::Or)) {
2597  coefficients.back() = -1.0;
2598  }
2599  std::vector<SolverIndexType> lpVariableIDs(2, indicatorVariableLPVariable);
2600  for(VariableLabelPairsIteratorType iter = indicatorVariable.begin(); iter != indicatorVariable.end(); ++iter) {
2601  lpVariableIDs[1] = nodeLPVariableIndex(gm_[factor].variableIndex(iter->first), iter->second);
2602  std::stringstream constraintName;
2603  if(parameter_.nameConstraints_) {
2604  constraintName << "indicator variable constraint of factor " << factor << "of type ";
2605  switch(indicatorVariable.getLogicalOperatorType()) {
2606  case IndicatorVariableType::And : {
2607  constraintName << "And";
2608  break;
2609  }
2610  case IndicatorVariableType::Or : {
2611  constraintName << "Or";
2612  break;
2613  }
2614  default : {
2615  // default corresponds to IndicatorVariableType::Not
2616  constraintName << "Not";
2617  }
2618  }
2619  constraintName << " for node" << iter->first << " and label " << iter->second;
2620  }
2621 
2622  if(addToModel) {
2623  switch(indicatorVariable.getLogicalOperatorType()) {
2624  case IndicatorVariableType::And : {
2625  static_cast<LPInferenceType*>(this)->addLessEqualConstraint(lpVariableIDs.begin(), lpVariableIDs.end(), coefficients.begin(), 0.0, constraintName.str());
2626  break;
2627  }
2628  case IndicatorVariableType::Or : {
2629  static_cast<LPInferenceType*>(this)->addGreaterEqualConstraint(lpVariableIDs.begin(), lpVariableIDs.end(), coefficients.begin(), 0.0, constraintName.str());
2630  break;
2631  }
2632  default : {
2633  // default corresponds to IndicatorVariableType::Not
2634  static_cast<LPInferenceType*>(this)->addLessEqualConstraint(lpVariableIDs.begin(), lpVariableIDs.end(), coefficients.begin(), 1.0, constraintName.str());
2635  }
2636  }
2637  } else {
2638  ConstraintStorage constraint;
2639  constraint.variableIDs_ = lpVariableIDs;
2640  constraint.coefficients_ = coefficients;
2641  switch(indicatorVariable.getLogicalOperatorType()) {
2642  case IndicatorVariableType::And : {
2643  constraint.bound_ = 0.0;
2644  constraint.operator_ = LinearConstraintType::LinearConstraintOperatorType::LessEqual;
2645  break;
2646  }
2647  case IndicatorVariableType::Or : {
2648  constraint.bound_ = 0.0;
2649  constraint.operator_ = LinearConstraintType::LinearConstraintOperatorType::GreaterEqual;
2650  break;
2651  }
2652  default : {
2653  // default corresponds to IndicatorVariableType::Not
2654  constraint.bound_ = 1.0;
2655  constraint.operator_ = LinearConstraintType::LinearConstraintOperatorType::LessEqual;
2656  }
2657  }
2658  constraint.name_ = constraintName.str();
2659  inactiveConstraints_.push_back(constraint);
2660  }
2661  }
2662 
2663  // And: \sum_i lpNodeVar(node_i; label_i) - currentLPVariable <= n - 1.0
2664  // Or: \sum_i lpNodeVar(node_i; label_i) - currentLPVariable >= 0.0
2665  // Not: \sum_i lpNodeVar(node_i; label_i) + currentLPVariable >= 1.0
2666  if((indicatorVariable.getLogicalOperatorType() == IndicatorVariableType::And) || (indicatorVariable.getLogicalOperatorType() == IndicatorVariableType::Or)) {
2667  coefficients.back() = 1.0;
2668  }
2669  coefficients.resize(numVariables + 1, 1.0);
2670  if((indicatorVariable.getLogicalOperatorType() == IndicatorVariableType::And) || (indicatorVariable.getLogicalOperatorType() == IndicatorVariableType::Or)) {
2671  coefficients.back() = -1.0;
2672  }
2673  lpVariableIDs.clear();
2674  for(VariableLabelPairsIteratorType iter = indicatorVariable.begin(); iter != indicatorVariable.end(); ++iter) {
2675  lpVariableIDs.push_back(nodeLPVariableIndex(gm_[factor].variableIndex(iter->first), iter->second));
2676  }
2677  lpVariableIDs.push_back(indicatorVariableLPVariable);
2678  std::stringstream constraintName;
2679  if(parameter_.nameConstraints_) {
2680  constraintName << "indicator variable sum constraint of factor " << factor << "of type ";
2681  switch(indicatorVariable.getLogicalOperatorType()) {
2682  case IndicatorVariableType::And : {
2683  constraintName << "And";
2684  break;
2685  }
2686  case IndicatorVariableType::Or : {
2687  constraintName << "Or";
2688  break;
2689  }
2690  default : {
2691  // default corresponds to IndicatorVariableType::Not
2692  constraintName << "Not";
2693  }
2694  }
2695  constraintName << " for lp variable" << indicatorVariableLPVariable;
2696  }
2697  if(addToModel) {
2698  switch(indicatorVariable.getLogicalOperatorType()) {
2699  case IndicatorVariableType::And : {
2700  static_cast<LPInferenceType*>(this)->addLessEqualConstraint(lpVariableIDs.begin(), lpVariableIDs.end(), coefficients.begin(), static_cast<const SolverValueType>(numVariables - 1.0), constraintName.str());
2701  break;
2702  }
2703  case IndicatorVariableType::Or : {
2704  static_cast<LPInferenceType*>(this)->addGreaterEqualConstraint(lpVariableIDs.begin(), lpVariableIDs.end(), coefficients.begin(), static_cast<const SolverValueType>(0.0), constraintName.str());
2705  break;
2706  }
2707  default : {
2708  // default corresponds to IndicatorVariableType::Not
2709  static_cast<LPInferenceType*>(this)->addGreaterEqualConstraint(lpVariableIDs.begin(), lpVariableIDs.end(), coefficients.begin(), static_cast<const SolverValueType>(1.0), constraintName.str());
2710  }
2711  }
2712  } else {
2713  ConstraintStorage constraint;
2714  constraint.variableIDs_ = lpVariableIDs;
2715  constraint.coefficients_ = coefficients;
2716  switch(indicatorVariable.getLogicalOperatorType()) {
2717  case IndicatorVariableType::And : {
2718  constraint.bound_ = static_cast<const SolverValueType>(numVariables - 1.0);
2719  constraint.operator_ = LinearConstraintType::LinearConstraintOperatorType::LessEqual;
2720  break;
2721  }
2722  case IndicatorVariableType::Or : {
2723  constraint.bound_ = static_cast<const SolverValueType>(0.0);
2724  constraint.operator_ = LinearConstraintType::LinearConstraintOperatorType::GreaterEqual;
2725  break;
2726  }
2727  default : {
2728  // default corresponds to IndicatorVariableType::Not
2729  constraint.bound_ = static_cast<const SolverValueType>(1.0);
2730  constraint.operator_ = LinearConstraintType::LinearConstraintOperatorType::GreaterEqual;
2731  }
2732  }
2733  constraint.name_ = constraintName.str();
2734  inactiveConstraints_.push_back(constraint);
2735  }
2736  }
2737  }
2738  }
2739 }
2740 
2741 template <class LP_INFERENCE_TYPE>
2742 inline void LPInferenceBase<LP_INFERENCE_TYPE>::addLinearConstraint(const IndexType linearConstraintFactor, const LinearConstraintType& constraint) {
2743  OPENGM_ASSERT(linearConstraintFactor < linearConstraintsLPVariablesIndicesLookupTable_.size());
2744  std::vector<SolverIndexType> lpVariables(std::distance(constraint.indicatorVariablesBegin(), constraint.indicatorVariablesEnd()));
2745  for(size_t i = 0; i < lpVariables.size(); ++i) {
2746  lpVariables[i] = linearConstraintsLPVariablesIndicesLookupTable_[linearConstraintFactor][constraint.indicatorVariablesBegin()[i]];
2747  }
2748  switch(constraint.getConstraintOperator()) {
2749  case LinearConstraintType::LinearConstraintOperatorType::LessEqual : {
2750  static_cast<LPInferenceType*>(this)->addLessEqualConstraint(lpVariables.begin(), lpVariables.end(), constraint.coefficientsBegin(), static_cast<const SolverValueType>(constraint.getBound()));
2751  break;
2752  }
2753  case LinearConstraintType::LinearConstraintOperatorType::Equal : {
2754  static_cast<LPInferenceType*>(this)->addEqualityConstraint(lpVariables.begin(), lpVariables.end(), constraint.coefficientsBegin(), static_cast<const SolverValueType>(constraint.getBound()));
2755  break;
2756  }
2757  default: {
2758  // default corresponds to LinearConstraintOperatorType::LinearConstraintOperator::GreaterEqual case
2759  static_cast<LPInferenceType*>(this)->addGreaterEqualConstraint(lpVariables.begin(), lpVariables.end(), constraint.coefficientsBegin(), static_cast<const SolverValueType>(constraint.getBound()));
2760  }
2761  }
2762 }
2763 
2764 template <class LP_INFERENCE_TYPE>
2765 template <class VISITOR_TYPE>
2766 inline InferenceTermination LPInferenceBase<LP_INFERENCE_TYPE>::infer_impl_selectRelaxation(VISITOR_TYPE& visitor) {
2767  switch(parameter_.relaxation_){
2768  case Parameter::LocalPolytope : {
2769  return infer_impl_selectHeuristic<VISITOR_TYPE, Parameter::LocalPolytope>(visitor);
2770  }
2771  case Parameter::LoosePolytope : {
2772  return infer_impl_selectHeuristic<VISITOR_TYPE, Parameter::LoosePolytope>(visitor);
2773  }
2774  case Parameter::TightPolytope: {
2775  return infer_impl_selectHeuristic<VISITOR_TYPE, Parameter::TightPolytope>(visitor);
2776  }
2777  default : {
2778  throw RuntimeError("Unknown Relaxation");
2779  }
2780  }
2781 }
2782 
2783 template <class LP_INFERENCE_TYPE>
2784 template <class VISITOR_TYPE, typename LPInferenceBase<LP_INFERENCE_TYPE>::Parameter::Relaxation RELAXATION>
2785 inline InferenceTermination LPInferenceBase<LP_INFERENCE_TYPE>::infer_impl_selectHeuristic(VISITOR_TYPE& visitor) {
2786  switch(parameter_.challengeHeuristic_){
2787  case Parameter::Random : {
2788  return infer_impl_selectIterations<VISITOR_TYPE, RELAXATION, Parameter::Random>(visitor);
2789  }
2790  case Parameter::Weighted : {
2791  return infer_impl_selectIterations<VISITOR_TYPE, RELAXATION, Parameter::Weighted>(visitor);
2792  }
2793  default : {
2794  throw RuntimeError("Unknown Heuristic");
2795  }
2796  }
2797 }
2798 
2799 template <class LP_INFERENCE_TYPE>
2800 template <class VISITOR_TYPE, typename LPInferenceBase<LP_INFERENCE_TYPE>::Parameter::Relaxation RELAXATION, typename LPInferenceBase<LP_INFERENCE_TYPE>::Parameter::ChallengeHeuristic HEURISTIC>
2801 inline InferenceTermination LPInferenceBase<LP_INFERENCE_TYPE>::infer_impl_selectIterations(VISITOR_TYPE& visitor) {
2802  if(parameter_.maxNumIterations_ == 0) {
2803  return infer_impl_selectViolatedConstraints<VISITOR_TYPE, RELAXATION, HEURISTIC, true>(visitor);
2804  } else {
2805  return infer_impl_selectViolatedConstraints<VISITOR_TYPE, RELAXATION, HEURISTIC, false>(visitor);
2806  }
2807 }
2808 
2809 template <class LP_INFERENCE_TYPE>
2810 template <class VISITOR_TYPE, typename LPInferenceBase<LP_INFERENCE_TYPE>::Parameter::Relaxation RELAXATION, typename LPInferenceBase<LP_INFERENCE_TYPE>::Parameter::ChallengeHeuristic HEURISTIC, bool USE_INFINITE_ITERATIONS>
2811 inline InferenceTermination LPInferenceBase<LP_INFERENCE_TYPE>::infer_impl_selectViolatedConstraints(VISITOR_TYPE& visitor) {
2812  if(parameter_.maxNumConstraintsPerIter_ == 0) {
2813  return infer_impl_selectLPType<VISITOR_TYPE, RELAXATION, HEURISTIC, USE_INFINITE_ITERATIONS, true>(visitor);
2814  } else {
2815  return infer_impl_selectLPType<VISITOR_TYPE, RELAXATION, HEURISTIC, USE_INFINITE_ITERATIONS, false>(visitor);
2816  }
2817 }
2818 
2819 template <class LP_INFERENCE_TYPE>
2820 template <class VISITOR_TYPE, typename LPInferenceBase<LP_INFERENCE_TYPE>::Parameter::Relaxation RELAXATION, typename LPInferenceBase<LP_INFERENCE_TYPE>::Parameter::ChallengeHeuristic HEURISTIC, bool USE_INFINITE_ITERATIONS, bool ADD_ALL_VIOLATED_CONSTRAINTS>
2821 inline InferenceTermination LPInferenceBase<LP_INFERENCE_TYPE>::infer_impl_selectLPType(VISITOR_TYPE& visitor) {
2822  if(parameter_.integerConstraintNodeVar_ || parameter_.integerConstraintFactorVar_) {
2823  return infer_impl<VISITOR_TYPE, RELAXATION, HEURISTIC, USE_INFINITE_ITERATIONS, ADD_ALL_VIOLATED_CONSTRAINTS, true>(visitor);
2824  } else {
2825  return infer_impl<VISITOR_TYPE, RELAXATION, HEURISTIC, USE_INFINITE_ITERATIONS, ADD_ALL_VIOLATED_CONSTRAINTS, false>(visitor);
2826  }
2827 }
2828 
2829 template <class LP_INFERENCE_TYPE>
2830 template <class VISITOR_TYPE, typename LPInferenceBase<LP_INFERENCE_TYPE>::Parameter::Relaxation RELAXATION, typename LPInferenceBase<LP_INFERENCE_TYPE>::Parameter::ChallengeHeuristic HEURISTIC, bool USE_INFINITE_ITERATIONS, bool ADD_ALL_VIOLATED_CONSTRAINTS, bool USE_INTEGER_CONSTRAINTS>
2831 inline InferenceTermination LPInferenceBase<LP_INFERENCE_TYPE>::infer_impl(VISITOR_TYPE& visitor) {
2832  if(meta::Compare<VISITOR_TYPE, TimingVisitorType>::value) {
2833  visitor.addLog("LP Solver Time");
2834  visitor.addLog("Search Violated Constraints Time");
2835  visitor.addLog("Add Violated Constraints Time");
2836  }
2837 
2838  visitor.begin(*this);
2839  inferenceStarted_ = true;
2840  for(size_t i = 0; USE_INFINITE_ITERATIONS || (i < parameter_.maxNumIterations_);) {
2841  // solve problem
2842  if(meta::Compare<VISITOR_TYPE, TimingVisitorType>::value) {
2843  SolverTimingType solverTime;
2844  const bool solveSuccess = static_cast<LPInferenceType*>(this)->solve(solverTime);
2845  if(!solveSuccess) {
2846  // LPSOLVER failed to optimize
2847  return UNKNOWN;
2848  }
2849  const size_t visitorReturnFlag = visitor(*this);
2850  visitor.log("LP Solver Time", solverTime);
2851  if(visitorReturnFlag != visitors::VisitorReturnFlag::ContinueInf) {
2852  // timeout or bound reached
2853  break;
2854  }
2855  } else {
2856  if(!static_cast<LPInferenceType*>(this)->solve()) {
2857  // LPSOLVER failed to optimize
2858  return UNKNOWN;
2859  }
2860  if(visitor(*this) != visitors::VisitorReturnFlag::ContinueInf) {
2861  // timeout or bound reached
2862  break;
2863  }
2864  }
2865  // search violated constraints
2866  if(meta::Compare<VISITOR_TYPE, TimingVisitorType>::value) {
2867  static Timer searchViolatedConstraintsTimer;
2868  searchViolatedConstraintsTimer.reset();
2869  searchViolatedConstraintsTimer.tic();
2870  const bool newViolatedConstraintsFound = USE_INTEGER_CONSTRAINTS ? tightenPolytope<RELAXATION, HEURISTIC, ADD_ALL_VIOLATED_CONSTRAINTS>() : tightenPolytopeRelaxed<RELAXATION, HEURISTIC, ADD_ALL_VIOLATED_CONSTRAINTS>();
2871  searchViolatedConstraintsTimer.toc();
2872  visitor.log("Search Violated Constraints Time", searchViolatedConstraintsTimer.elapsedTime());
2873  if(newViolatedConstraintsFound){
2874  SolverTimingType addConstraintsTime;
2875  static_cast<LPInferenceType*>(this)->addConstraintsFinished(addConstraintsTime);
2876  visitor.log("Add Violated Constraints Time", addConstraintsTime);
2877  } else {
2878  // all constraints are satisfied
2879  break;
2880  }
2881  } else {
2882  if(USE_INTEGER_CONSTRAINTS ? tightenPolytope<RELAXATION, HEURISTIC, ADD_ALL_VIOLATED_CONSTRAINTS>() : tightenPolytopeRelaxed<RELAXATION, HEURISTIC, ADD_ALL_VIOLATED_CONSTRAINTS>()){
2883  static_cast<LPInferenceType*>(this)->addConstraintsFinished();
2884  } else {
2885  // all constraints are satisfied
2886  break;
2887  }
2888  }
2889  if(!USE_INFINITE_ITERATIONS) {
2890  ++i;
2891  }
2892  }
2893  visitor.end(*this);
2894  return NORMAL;
2895 }
2896 
2897 template <class LP_INFERENCE_TYPE>
2898 template <typename LPInferenceBase<LP_INFERENCE_TYPE>::Parameter::Relaxation RELAXATION, typename LPInferenceBase<LP_INFERENCE_TYPE>::Parameter::ChallengeHeuristic HEURISTIC, bool ADD_ALL_VIOLATED_CONSTRAINTS>
2899 inline bool LPInferenceBase<LP_INFERENCE_TYPE>::tightenPolytope() {
2900  if(RELAXATION == Parameter::TightPolytope) {
2901  // nothing to tighten!
2902  return false;
2903  }
2904 
2905  // get current solution
2906  static std::vector<LabelType> currentArg;
2907  arg(currentArg);
2908 
2909  if(ADD_ALL_VIOLATED_CONSTRAINTS) {
2910  bool violatedConstraintAdded = false;
2911  if(RELAXATION == Parameter::LoosePolytope) {
2912  double currentWeight;
2913  InactiveConstraintsListIteratorType inactiveConstraintsBegin = inactiveConstraints_.begin();
2914  InactiveConstraintsListIteratorType inactiveConstraintsEnd = inactiveConstraints_.end();
2915  while(inactiveConstraintsBegin != inactiveConstraintsEnd) {
2916  checkInactiveConstraint(*inactiveConstraintsBegin, currentWeight);
2917  if(currentWeight > parameter_.tolerance_) {
2918  addInactiveConstraint(*inactiveConstraintsBegin);
2919  violatedConstraintAdded = true;
2920  const InactiveConstraintsListIteratorType removeInactiveConstraintIterator = inactiveConstraintsBegin;
2921  ++inactiveConstraintsBegin;
2922  inactiveConstraints_.erase(removeInactiveConstraintIterator);
2923  break;
2924  } else {
2925  ++inactiveConstraintsBegin;
2926  }
2927  }
2928  while(inactiveConstraintsBegin != inactiveConstraintsEnd) {
2929  checkInactiveConstraint(*inactiveConstraintsBegin, currentWeight);
2930  if(currentWeight > parameter_.tolerance_) {
2931  addInactiveConstraint(*inactiveConstraintsBegin);
2932  const InactiveConstraintsListIteratorType removeInactiveConstraintIterator = inactiveConstraintsBegin;
2933  ++inactiveConstraintsBegin;
2934  inactiveConstraints_.erase(removeInactiveConstraintIterator);
2935  } else {
2936  ++inactiveConstraintsBegin;
2937  }
2938  }
2939  }
2940 
2941  // add violated linear constraints from linear constraint factors
2942  size_t i = 0;
2943  AddAllViolatedLinearConstraintsFunctor addAllViolatedLinearConstraintsFunctor;
2944  addAllViolatedLinearConstraintsFunctor.tolerance_ = parameter_.tolerance_;
2945  addAllViolatedLinearConstraintsFunctor.lpInference_ = this;
2946  addAllViolatedLinearConstraintsFunctor.violatedConstraintAdded_ = false;
2947  if(!violatedConstraintAdded) {
2948  for(; i < linearConstraintFactors_.size(); ++i) {
2949  addAllViolatedLinearConstraintsFunctor.labelingBegin_ = IntegerSolutionSubsequenceIterator(currentArg.begin(), linearConstraintLPVariablesSubsequenceIndices_[i].begin());
2950  addAllViolatedLinearConstraintsFunctor.linearConstraintID_ = i;
2951  const IndexType currentFactor = linearConstraintFactors_[i];
2952  gm_[currentFactor].callFunctor(addAllViolatedLinearConstraintsFunctor);
2953  if(addAllViolatedLinearConstraintsFunctor.violatedConstraintAdded_) {
2954  violatedConstraintAdded = true;
2955  break;
2956  }
2957  }
2958  }
2959  for(; i < linearConstraintFactors_.size(); ++i) {
2960  for(; i < linearConstraintFactors_.size(); ++i) {
2961  addAllViolatedLinearConstraintsFunctor.labelingBegin_ = IntegerSolutionSubsequenceIterator(currentArg.begin(), linearConstraintLPVariablesSubsequenceIndices_[i].begin());
2962  addAllViolatedLinearConstraintsFunctor.linearConstraintID_ = i;
2963  const IndexType currentFactor = linearConstraintFactors_[i];
2964  gm_[currentFactor].callFunctor(addAllViolatedLinearConstraintsFunctor);
2965  }
2966  }
2967  return violatedConstraintAdded;
2968  } else {
2969  size_t numConstraintsAdded = 0;
2970  SortedViolatedConstraintsListType sortedViolatedConstraints;
2971 
2972  if(RELAXATION == Parameter::LoosePolytope) {
2973  double currentWeight;
2974  InactiveConstraintsListIteratorType inactiveConstraintsBegin = inactiveConstraints_.begin();
2975  InactiveConstraintsListIteratorType inactiveConstraintsEnd = inactiveConstraints_.end();
2976  while(inactiveConstraintsBegin != inactiveConstraintsEnd) {
2977  checkInactiveConstraint(*inactiveConstraintsBegin, currentWeight);
2978  if(currentWeight > parameter_.tolerance_) {
2979  if(HEURISTIC == Parameter::Random) {
2980  addInactiveConstraint(*inactiveConstraintsBegin);
2981  ++numConstraintsAdded;
2982  const InactiveConstraintsListIteratorType removeInactiveConstraintIterator = inactiveConstraintsBegin;
2983  ++inactiveConstraintsBegin;
2984  inactiveConstraints_.erase(removeInactiveConstraintIterator);
2985  if(numConstraintsAdded == parameter_.maxNumConstraintsPerIter_) {
2986  break;
2987  }
2988  } else {
2989  sortedViolatedConstraints.insert(typename SortedViolatedConstraintsListType::value_type(currentWeight, std::make_pair(inactiveConstraintsBegin, std::make_pair(linearConstraintFactors_.size(), static_cast<const LinearConstraintType*>(NULL)))));
2990  if(sortedViolatedConstraints.size() > parameter_.maxNumConstraintsPerIter_) {
2991  // remove constraints with to small weight
2992  sortedViolatedConstraints.erase(sortedViolatedConstraints.begin());
2993  OPENGM_ASSERT(sortedViolatedConstraints.size() == parameter_.maxNumConstraintsPerIter_);
2994  }
2995  ++inactiveConstraintsBegin;
2996  }
2997  } else {
2998  ++inactiveConstraintsBegin;
2999  }
3000  }
3001  }
3002 
3003  // add violated linear constraints from linear constraint factors
3004  AddViolatedLinearConstraintsFunctor<LPInferenceBaseType, HEURISTIC> addViolatedLinearConstraintsFunctor;
3005  addViolatedLinearConstraintsFunctor.tolerance_ = parameter_.tolerance_;
3006  addViolatedLinearConstraintsFunctor.lpInference_ = this;
3007  addViolatedLinearConstraintsFunctor.numConstraintsAdded_ = numConstraintsAdded;
3008  addViolatedLinearConstraintsFunctor.sortedViolatedConstraintsList_ = &sortedViolatedConstraints;
3009  for(size_t i = 0; i < linearConstraintFactors_.size(); ++i) {
3010  addViolatedLinearConstraintsFunctor.labelingBegin_ = IntegerSolutionSubsequenceIterator(currentArg.begin(), linearConstraintLPVariablesSubsequenceIndices_[i].begin());
3011  addViolatedLinearConstraintsFunctor.linearConstraintID_ = i;
3012  const IndexType currentFactor = linearConstraintFactors_[i];
3013  gm_[currentFactor].callFunctor(addViolatedLinearConstraintsFunctor);
3014  if(addViolatedLinearConstraintsFunctor.numConstraintsAdded_ == parameter_.maxNumConstraintsPerIter_) {
3015  break;
3016  }
3017  }
3018 
3019  numConstraintsAdded = addViolatedLinearConstraintsFunctor.numConstraintsAdded_;
3020  typename SortedViolatedConstraintsListType::reverse_iterator sortedViolatedConstraintsListRBegin = sortedViolatedConstraints.rbegin();
3021  const typename SortedViolatedConstraintsListType::reverse_iterator sortedViolatedConstraintsListREnd = sortedViolatedConstraints.rend();
3022  OPENGM_ASSERT(sortedViolatedConstraints.size() <= parameter_.maxNumConstraintsPerIter_);
3023  while(sortedViolatedConstraintsListRBegin != sortedViolatedConstraintsListREnd) {
3024  if(sortedViolatedConstraintsListRBegin->second.first == inactiveConstraints_.end()) {
3025  addLinearConstraint(sortedViolatedConstraintsListRBegin->second.second.first, *(sortedViolatedConstraintsListRBegin->second.second.second));
3026  } else {
3027  addInactiveConstraint(*(sortedViolatedConstraintsListRBegin->second.first));
3028  inactiveConstraints_.erase(sortedViolatedConstraintsListRBegin->second.first);
3029  }
3030  ++numConstraintsAdded;
3031  ++sortedViolatedConstraintsListRBegin;
3032  }
3033  if(numConstraintsAdded == 0) {
3034  return false;
3035  } else {
3036  return true;
3037  }
3038  }
3039 }
3040 
3041 template <class LP_INFERENCE_TYPE>
3042 template <typename LPInferenceBase<LP_INFERENCE_TYPE>::Parameter::Relaxation RELAXATION, typename LPInferenceBase<LP_INFERENCE_TYPE>::Parameter::ChallengeHeuristic HEURISTIC, bool ADD_ALL_VIOLATED_CONSTRAINTS>
3043 inline bool LPInferenceBase<LP_INFERENCE_TYPE>::tightenPolytopeRelaxed() {
3044  if(RELAXATION == Parameter::TightPolytope) {
3045  // nothing to tighten!
3046  return false;
3047  }
3048 
3049  // get current solution
3050  SolverSolutionIteratorType relaxedArgBegin = static_cast<const LPInferenceType*>(this)->solutionBegin();
3051 
3052  if(ADD_ALL_VIOLATED_CONSTRAINTS) {
3053  bool violatedConstraintAdded = false;
3054  if(RELAXATION == Parameter::LoosePolytope) {
3055  double currentWeight;
3056  InactiveConstraintsListIteratorType inactiveConstraintsBegin = inactiveConstraints_.begin();
3057  InactiveConstraintsListIteratorType inactiveConstraintsEnd = inactiveConstraints_.end();
3058  while(inactiveConstraintsBegin != inactiveConstraintsEnd) {
3059  checkInactiveConstraint(*inactiveConstraintsBegin, currentWeight);
3060  if(currentWeight > parameter_.tolerance_) {
3061  addInactiveConstraint(*inactiveConstraintsBegin);
3062  violatedConstraintAdded = true;
3063  const InactiveConstraintsListIteratorType removeInactiveConstraintIterator = inactiveConstraintsBegin;
3064  ++inactiveConstraintsBegin;
3065  inactiveConstraints_.erase(removeInactiveConstraintIterator);
3066  break;
3067  } else {
3068  ++inactiveConstraintsBegin;
3069  }
3070  }
3071  while(inactiveConstraintsBegin != inactiveConstraintsEnd) {
3072  checkInactiveConstraint(*inactiveConstraintsBegin, currentWeight);
3073  if(currentWeight > parameter_.tolerance_) {
3074  addInactiveConstraint(*inactiveConstraintsBegin);
3075  const InactiveConstraintsListIteratorType removeInactiveConstraintIterator = inactiveConstraintsBegin;
3076  ++inactiveConstraintsBegin;
3077  inactiveConstraints_.erase(removeInactiveConstraintIterator);
3078  } else {
3079  ++inactiveConstraintsBegin;
3080  }
3081  }
3082  }
3083 
3084  // add violated linear constraints from linear constraint factors
3085  size_t i = 0;
3086  AddAllViolatedLinearConstraintsRelaxedFunctor addAllViolatedLinearConstraintsRelaxedFunctor;
3087  addAllViolatedLinearConstraintsRelaxedFunctor.tolerance_ = parameter_.tolerance_;
3088  addAllViolatedLinearConstraintsRelaxedFunctor.lpInference_ = this;
3089  addAllViolatedLinearConstraintsRelaxedFunctor.violatedConstraintAdded_ = false;
3090  if(!violatedConstraintAdded) {
3091  for(; i < linearConstraintFactors_.size(); ++i) {
3092  addAllViolatedLinearConstraintsRelaxedFunctor.labelingBegin_ = RelaxedSolutionSubsequenceIterator(relaxedArgBegin, linearConstraintLPVariablesSubsequenceIndices_[i].begin());
3093  addAllViolatedLinearConstraintsRelaxedFunctor.linearConstraintID_ = i;
3094  const IndexType currentFactor = linearConstraintFactors_[i];
3095  gm_[currentFactor].callFunctor(addAllViolatedLinearConstraintsRelaxedFunctor);
3096  if(addAllViolatedLinearConstraintsRelaxedFunctor.violatedConstraintAdded_) {
3097  violatedConstraintAdded = true;
3098  break;
3099  }
3100  }
3101  }
3102  for(; i < linearConstraintFactors_.size(); ++i) {
3103  for(; i < linearConstraintFactors_.size(); ++i) {
3104  addAllViolatedLinearConstraintsRelaxedFunctor.labelingBegin_ = RelaxedSolutionSubsequenceIterator(relaxedArgBegin, linearConstraintLPVariablesSubsequenceIndices_[i].begin());
3105  addAllViolatedLinearConstraintsRelaxedFunctor.linearConstraintID_ = i;
3106  const IndexType currentFactor = linearConstraintFactors_[i];
3107  gm_[currentFactor].callFunctor(addAllViolatedLinearConstraintsRelaxedFunctor);
3108  }
3109  }
3110  return violatedConstraintAdded;
3111  } else {
3112  size_t numConstraintsAdded = 0;
3113  SortedViolatedConstraintsListType sortedViolatedConstraints;
3114 
3115  if(RELAXATION == Parameter::LoosePolytope) {
3116  double currentWeight;
3117  InactiveConstraintsListIteratorType inactiveConstraintsBegin = inactiveConstraints_.begin();
3118  InactiveConstraintsListIteratorType inactiveConstraintsEnd = inactiveConstraints_.end();
3119  while(inactiveConstraintsBegin != inactiveConstraintsEnd) {
3120  checkInactiveConstraint(*inactiveConstraintsBegin, currentWeight);
3121  if(currentWeight > parameter_.tolerance_) {
3122  if(HEURISTIC == Parameter::Random) {
3123  addInactiveConstraint(*inactiveConstraintsBegin);
3124  ++numConstraintsAdded;
3125  const InactiveConstraintsListIteratorType removeInactiveConstraintIterator = inactiveConstraintsBegin;
3126  ++inactiveConstraintsBegin;
3127  inactiveConstraints_.erase(removeInactiveConstraintIterator);
3128  if(numConstraintsAdded == parameter_.maxNumConstraintsPerIter_) {
3129  break;
3130  }
3131  } else {
3132  sortedViolatedConstraints.insert(typename SortedViolatedConstraintsListType::value_type(currentWeight, std::make_pair(inactiveConstraintsBegin, std::make_pair(linearConstraintFactors_.size(), static_cast<LinearConstraintType*>(NULL)))));
3133  if(sortedViolatedConstraints.size() > parameter_.maxNumConstraintsPerIter_) {
3134  // remove constraints with to small weight
3135  sortedViolatedConstraints.erase(sortedViolatedConstraints.begin());
3136  OPENGM_ASSERT(sortedViolatedConstraints.size() == parameter_.maxNumConstraintsPerIter_);
3137  }
3138  ++inactiveConstraintsBegin;
3139  }
3140  } else {
3141  ++inactiveConstraintsBegin;
3142  }
3143  }
3144  }
3145 
3146  // add violated linear constraints from linear constraint factors
3147  AddViolatedLinearConstraintsRelaxedFunctor<LPInferenceBaseType, HEURISTIC> addViolatedLinearConstraintsRelaxedFunctor;
3148  addViolatedLinearConstraintsRelaxedFunctor.tolerance_ = parameter_.tolerance_;
3149  addViolatedLinearConstraintsRelaxedFunctor.lpInference_ = this;
3150  addViolatedLinearConstraintsRelaxedFunctor.numConstraintsAdded_ = numConstraintsAdded;
3151  addViolatedLinearConstraintsRelaxedFunctor.sortedViolatedConstraintsList_ = &sortedViolatedConstraints;
3152  for(size_t i = 0; i < linearConstraintFactors_.size(); ++i) {
3153  addViolatedLinearConstraintsRelaxedFunctor.labelingBegin_ = RelaxedSolutionSubsequenceIterator(relaxedArgBegin, linearConstraintLPVariablesSubsequenceIndices_[i].begin());
3154  addViolatedLinearConstraintsRelaxedFunctor.linearConstraintID_ = i;
3155  const IndexType currentFactor = linearConstraintFactors_[i];
3156  gm_[currentFactor].callFunctor(addViolatedLinearConstraintsRelaxedFunctor);
3157  if(addViolatedLinearConstraintsRelaxedFunctor.numConstraintsAdded_ == parameter_.maxNumConstraintsPerIter_) {
3158  break;
3159  }
3160  }
3161 
3162  numConstraintsAdded = addViolatedLinearConstraintsRelaxedFunctor.numConstraintsAdded_;
3163  typename SortedViolatedConstraintsListType::reverse_iterator sortedViolatedConstraintsListRBegin = sortedViolatedConstraints.rbegin();
3164  const typename SortedViolatedConstraintsListType::reverse_iterator sortedViolatedConstraintsListREnd = sortedViolatedConstraints.rend();
3165  OPENGM_ASSERT(sortedViolatedConstraints.size() <= parameter_.maxNumConstraintsPerIter_);
3166  while(sortedViolatedConstraintsListRBegin != sortedViolatedConstraintsListREnd) {
3167  if(sortedViolatedConstraintsListRBegin->second.first == inactiveConstraints_.end()) {
3168  addLinearConstraint(sortedViolatedConstraintsListRBegin->second.second.first, *(sortedViolatedConstraintsListRBegin->second.second.second));
3169  } else {
3170  addInactiveConstraint(*(sortedViolatedConstraintsListRBegin->second.first));
3171  inactiveConstraints_.erase(sortedViolatedConstraintsListRBegin->second.first);
3172  }
3173  ++numConstraintsAdded;
3174  if(numConstraintsAdded == parameter_.maxNumConstraintsPerIter_) {
3175  break;
3176  }
3177  ++sortedViolatedConstraintsListRBegin;
3178  }
3179  if(numConstraintsAdded == 0) {
3180  return false;
3181  } else {
3182  return true;
3183  }
3184  }
3185 }
3186 
3187 template <class LP_INFERENCE_TYPE>
3188 inline void LPInferenceBase<LP_INFERENCE_TYPE>::checkInactiveConstraint(const ConstraintStorage& constraint, double& weight) const {
3189  const SolverSolutionIteratorType currentSolution = static_cast<const LPInferenceType*>(this)->solutionBegin();
3190  double sum = 0.0;
3191  for(size_t i = 0; i < constraint.variableIDs_.size(); ++i) {
3192  sum += constraint.coefficients_[i] * currentSolution[constraint.variableIDs_[i]];
3193  }
3194  switch(constraint.operator_) {
3195  case LinearConstraintType::LinearConstraintOperatorType::LessEqual : {
3196  if(sum <= constraint.bound_) {
3197  weight = 0.0;
3198  } else {
3199  weight = sum - constraint.bound_;
3200  }
3201  break;
3202  }
3203  case LinearConstraintType::LinearConstraintOperatorType::Equal : {
3204  if(sum == constraint.bound_) {
3205  weight = 0.0;
3206  } else {
3207  weight = std::abs(sum - constraint.bound_);
3208  }
3209  break;
3210  }
3211  default: {
3212  // default corresponds to LinearConstraintType::LinearConstraintOperatorType::GreaterEqual case
3213  if(sum >= constraint.bound_) {
3214  weight = 0.0;
3215  } else {
3216  weight = constraint.bound_ - sum;
3217  }
3218  break;
3219  }
3220  }
3221 }
3222 
3223 template <class LP_INFERENCE_TYPE>
3224 inline void LPInferenceBase<LP_INFERENCE_TYPE>::addInactiveConstraint(const ConstraintStorage& constraint) {
3225  switch(constraint.operator_) {
3226  case LinearConstraintType::LinearConstraintOperatorType::LessEqual : {
3227  static_cast<LPInferenceType*>(this)->addLessEqualConstraint(constraint.variableIDs_.begin(), constraint.variableIDs_.end(), constraint.coefficients_.begin(), constraint.bound_, constraint.name_);
3228  break;
3229  }
3230  case LinearConstraintType::LinearConstraintOperatorType::Equal : {
3231  static_cast<LPInferenceType*>(this)->addEqualityConstraint(constraint.variableIDs_.begin(), constraint.variableIDs_.end(), constraint.coefficients_.begin(), constraint.bound_, constraint.name_);
3232  break;
3233  }
3234  default: {
3235  // default corresponds to LinearConstraintType::LinearConstraintOperatorType::GreaterEqual case
3236  static_cast<LPInferenceType*>(this)->addGreaterEqualConstraint(constraint.variableIDs_.begin(), constraint.variableIDs_.end(), constraint.coefficients_.begin(), constraint.bound_, constraint.name_);
3237  break;
3238  }
3239  }
3240 }
3241 
3242 template <class LP_INFERENCE_TYPE>
3243 template<class LINEAR_CONSTRAINT_FUNCTION_TYPE>
3244 inline void LPInferenceBase<LP_INFERENCE_TYPE>::GetIndicatorVariablesOrderBeginFunctor::operator()(const LINEAR_CONSTRAINT_FUNCTION_TYPE& linearConstraintFunction) {
3245  GetIndicatorVariablesOrderBeginFunctor_impl<LINEAR_CONSTRAINT_FUNCTION_TYPE, meta::HasTypeInTypeList<LinearConstraintFunctionTypeList, LINEAR_CONSTRAINT_FUNCTION_TYPE>::value>::getIndicatorVariablesOrderBeginFunctor_impl(*this, linearConstraintFunction);
3246 }
3247 
3248 template <class LP_INFERENCE_TYPE>
3249 template<class FUNCTION_TYPE, bool IS_LINEAR_CONSTRAINT_FUNCTION>
3250 inline void LPInferenceBase<LP_INFERENCE_TYPE>::GetIndicatorVariablesOrderBeginFunctor::GetIndicatorVariablesOrderBeginFunctor_impl<FUNCTION_TYPE, IS_LINEAR_CONSTRAINT_FUNCTION>::getIndicatorVariablesOrderBeginFunctor_impl(GetIndicatorVariablesOrderBeginFunctor& myself, const FUNCTION_TYPE& function) {
3251  throw RuntimeError(std::string("GetIndicatorVariablesOrderBeginFunctor: Unsupported linear constraint function type") + typeid(FUNCTION_TYPE).name());
3252 }
3253 
3254 template <class LP_INFERENCE_TYPE>
3255 template<class FUNCTION_TYPE>
3256 inline void LPInferenceBase<LP_INFERENCE_TYPE>::GetIndicatorVariablesOrderBeginFunctor::GetIndicatorVariablesOrderBeginFunctor_impl<FUNCTION_TYPE, true>::getIndicatorVariablesOrderBeginFunctor_impl(GetIndicatorVariablesOrderBeginFunctor& myself, const FUNCTION_TYPE& function) {
3257  myself.indicatorVariablesOrderBegin_ = function.indicatorVariablesOrderBegin();
3258 }
3259 
3260 template <class LP_INFERENCE_TYPE>
3261 template<class LINEAR_CONSTRAINT_FUNCTION_TYPE>
3262 inline void LPInferenceBase<LP_INFERENCE_TYPE>::GetIndicatorVariablesOrderEndFunctor::operator()(const LINEAR_CONSTRAINT_FUNCTION_TYPE& linearConstraintFunction) {
3263  GetIndicatorVariablesOrderEndFunctor_impl<LINEAR_CONSTRAINT_FUNCTION_TYPE, meta::HasTypeInTypeList<LinearConstraintFunctionTypeList, LINEAR_CONSTRAINT_FUNCTION_TYPE>::value>::getIndicatorVariablesOrderEndFunctor_impl(*this, linearConstraintFunction);
3264 }
3265 
3266 template <class LP_INFERENCE_TYPE>
3267 template<class FUNCTION_TYPE, bool IS_LINEAR_CONSTRAINT_FUNCTION>
3268 inline void LPInferenceBase<LP_INFERENCE_TYPE>::GetIndicatorVariablesOrderEndFunctor::GetIndicatorVariablesOrderEndFunctor_impl<FUNCTION_TYPE, IS_LINEAR_CONSTRAINT_FUNCTION>::getIndicatorVariablesOrderEndFunctor_impl(GetIndicatorVariablesOrderEndFunctor& myself, const FUNCTION_TYPE& function) {
3269  throw RuntimeError(std::string("GetIndicatorVariablesOrderEnd: Unsupported linear constraint function type") + typeid(FUNCTION_TYPE).name());
3270 }
3271 
3272 template <class LP_INFERENCE_TYPE>
3273 template<class FUNCTION_TYPE>
3274 inline void LPInferenceBase<LP_INFERENCE_TYPE>::GetIndicatorVariablesOrderEndFunctor::GetIndicatorVariablesOrderEndFunctor_impl<FUNCTION_TYPE, true>::getIndicatorVariablesOrderEndFunctor_impl(GetIndicatorVariablesOrderEndFunctor& myself, const FUNCTION_TYPE& function) {
3275  myself.indicatorVariablesOrderEnd_ = function.indicatorVariablesOrderEnd();
3276 }
3277 
3278 template <class LP_INFERENCE_TYPE>
3279 template<class LINEAR_CONSTRAINT_FUNCTION_TYPE>
3280 inline void LPInferenceBase<LP_INFERENCE_TYPE>::GetLinearConstraintsBeginFunctor::operator()(const LINEAR_CONSTRAINT_FUNCTION_TYPE& linearConstraintFunction) {
3281  GetLinearConstraintsBeginFunctor_impl<LINEAR_CONSTRAINT_FUNCTION_TYPE, meta::HasTypeInTypeList<LinearConstraintFunctionTypeList, LINEAR_CONSTRAINT_FUNCTION_TYPE>::value>::getLinearConstraintsBeginFunctor_impl(*this, linearConstraintFunction);
3282 }
3283 
3284 template <class LP_INFERENCE_TYPE>
3285 template<class FUNCTION_TYPE, bool IS_LINEAR_CONSTRAINT_FUNCTION>
3286 inline void LPInferenceBase<LP_INFERENCE_TYPE>::GetLinearConstraintsBeginFunctor::GetLinearConstraintsBeginFunctor_impl<FUNCTION_TYPE, IS_LINEAR_CONSTRAINT_FUNCTION>::getLinearConstraintsBeginFunctor_impl(GetLinearConstraintsBeginFunctor& myself, const FUNCTION_TYPE& function) {
3287  throw RuntimeError(std::string("GetLinearConstraintsBeginFunctor: Unsupported linear constraint function type") + typeid(FUNCTION_TYPE).name());
3288 }
3289 
3290 template <class LP_INFERENCE_TYPE>
3291 template<class FUNCTION_TYPE>
3292 inline void LPInferenceBase<LP_INFERENCE_TYPE>::GetLinearConstraintsBeginFunctor::GetLinearConstraintsBeginFunctor_impl<FUNCTION_TYPE, true>::getLinearConstraintsBeginFunctor_impl(GetLinearConstraintsBeginFunctor& myself, const FUNCTION_TYPE& function) {
3293  myself.linearConstraintsBegin_ = function.linearConstraintsBegin();
3294 }
3295 
3296 template <class LP_INFERENCE_TYPE>
3297 template<class LINEAR_CONSTRAINT_FUNCTION_TYPE>
3298 inline void LPInferenceBase<LP_INFERENCE_TYPE>::GetLinearConstraintsEndFunctor::operator()(const LINEAR_CONSTRAINT_FUNCTION_TYPE& linearConstraintFunction) {
3299  GetLinearConstraintsEndFunctor_impl<LINEAR_CONSTRAINT_FUNCTION_TYPE, meta::HasTypeInTypeList<LinearConstraintFunctionTypeList, LINEAR_CONSTRAINT_FUNCTION_TYPE>::value>::getLinearConstraintsEndFunctor_impl(*this, linearConstraintFunction);
3300 }
3301 
3302 template <class LP_INFERENCE_TYPE>
3303 template<class FUNCTION_TYPE, bool IS_LINEAR_CONSTRAINT_FUNCTION>
3304 inline void LPInferenceBase<LP_INFERENCE_TYPE>::GetLinearConstraintsEndFunctor::GetLinearConstraintsEndFunctor_impl<FUNCTION_TYPE, IS_LINEAR_CONSTRAINT_FUNCTION>::getLinearConstraintsEndFunctor_impl(GetLinearConstraintsEndFunctor& myself, const FUNCTION_TYPE& function) {
3305  throw RuntimeError(std::string("GetLinearConstraintsEndFunctor: Unsupported linear constraint function type") + typeid(FUNCTION_TYPE).name());
3306 }
3307 
3308 template <class LP_INFERENCE_TYPE>
3309 template<class FUNCTION_TYPE>
3310 inline void LPInferenceBase<LP_INFERENCE_TYPE>::GetLinearConstraintsEndFunctor::GetLinearConstraintsEndFunctor_impl<FUNCTION_TYPE, true>::getLinearConstraintsEndFunctor_impl(GetLinearConstraintsEndFunctor& myself, const FUNCTION_TYPE& function) {
3311  myself.linearConstraintsEnd_ = function.linearConstraintsEnd();
3312 }
3313 
3314 template <class LP_INFERENCE_TYPE>
3315 template<class LINEAR_CONSTRAINT_FUNCTION_TYPE>
3316 inline void LPInferenceBase<LP_INFERENCE_TYPE>::AddAllViolatedLinearConstraintsFunctor::operator()(const LINEAR_CONSTRAINT_FUNCTION_TYPE& linearConstraintFunction) {
3317  AddAllViolatedLinearConstraintsFunctor_impl<LINEAR_CONSTRAINT_FUNCTION_TYPE, meta::HasTypeInTypeList<LinearConstraintFunctionTypeList, LINEAR_CONSTRAINT_FUNCTION_TYPE>::value>::addAllViolatedLinearConstraintsFunctor_impl(*this, linearConstraintFunction);
3318 }
3319 
3320 template <class LP_INFERENCE_TYPE>
3321 template<class FUNCTION_TYPE, bool IS_LINEAR_CONSTRAINT_FUNCTION>
3322 inline void LPInferenceBase<LP_INFERENCE_TYPE>::AddAllViolatedLinearConstraintsFunctor::AddAllViolatedLinearConstraintsFunctor_impl<FUNCTION_TYPE, IS_LINEAR_CONSTRAINT_FUNCTION>::addAllViolatedLinearConstraintsFunctor_impl(AddAllViolatedLinearConstraintsFunctor& myself, const FUNCTION_TYPE& function) {
3323  throw RuntimeError(std::string("AddAllViolatedLinearConstraintsFunctor: Unsupported linear constraint function type") + typeid(FUNCTION_TYPE).name());
3324 }
3325 
3326 template <class LP_INFERENCE_TYPE>
3327 template<class FUNCTION_TYPE>
3328 inline void LPInferenceBase<LP_INFERENCE_TYPE>::AddAllViolatedLinearConstraintsFunctor::AddAllViolatedLinearConstraintsFunctor_impl<FUNCTION_TYPE, true>::addAllViolatedLinearConstraintsFunctor_impl(AddAllViolatedLinearConstraintsFunctor& myself, const FUNCTION_TYPE& function) {
3329  typename FUNCTION_TYPE::ViolatedLinearConstraintsIteratorType violatedConstraintsBegin;
3330  typename FUNCTION_TYPE::ViolatedLinearConstraintsIteratorType violatedConstraintsEnd;
3331  typename FUNCTION_TYPE::ViolatedLinearConstraintsWeightsIteratorType violatedConstraintsWeightsBegin;
3332  function.challenge(violatedConstraintsBegin, violatedConstraintsEnd, violatedConstraintsWeightsBegin, myself.labelingBegin_, myself.tolerance_);
3333  if(std::distance(violatedConstraintsBegin, violatedConstraintsEnd) > 0) {
3334  while(violatedConstraintsBegin != violatedConstraintsEnd) {
3335  myself.lpInference_->addLinearConstraint(myself.linearConstraintID_, *violatedConstraintsBegin);
3336  ++violatedConstraintsBegin;
3337  }
3338  myself.violatedConstraintAdded_ = true;
3339  }
3340 }
3341 
3342 template <class LP_INFERENCE_TYPE>
3343 template<class LINEAR_CONSTRAINT_FUNCTION_TYPE>
3344 inline void LPInferenceBase<LP_INFERENCE_TYPE>::AddAllViolatedLinearConstraintsRelaxedFunctor::operator()(const LINEAR_CONSTRAINT_FUNCTION_TYPE& linearConstraintFunction) {
3345  AddAllViolatedLinearConstraintsRelaxedFunctor_impl<LINEAR_CONSTRAINT_FUNCTION_TYPE, meta::HasTypeInTypeList<LinearConstraintFunctionTypeList, LINEAR_CONSTRAINT_FUNCTION_TYPE>::value>::addAllViolatedLinearConstraintsRelaxedFunctor_impl(*this, linearConstraintFunction);
3346 }
3347 
3348 template <class LP_INFERENCE_TYPE>
3349 template<class FUNCTION_TYPE, bool IS_LINEAR_CONSTRAINT_FUNCTION>
3350 inline void LPInferenceBase<LP_INFERENCE_TYPE>::AddAllViolatedLinearConstraintsRelaxedFunctor::AddAllViolatedLinearConstraintsRelaxedFunctor_impl<FUNCTION_TYPE, IS_LINEAR_CONSTRAINT_FUNCTION>::addAllViolatedLinearConstraintsRelaxedFunctor_impl(AddAllViolatedLinearConstraintsRelaxedFunctor& myself, const FUNCTION_TYPE& function) {
3351  throw RuntimeError(std::string("AddAllViolatedLinearConstraintsRelaxedFunctor: Unsupported linear constraint function type") + typeid(FUNCTION_TYPE).name());
3352 }
3353 
3354 template <class LP_INFERENCE_TYPE>
3355 template<class FUNCTION_TYPE>
3356 inline void LPInferenceBase<LP_INFERENCE_TYPE>::AddAllViolatedLinearConstraintsRelaxedFunctor::AddAllViolatedLinearConstraintsRelaxedFunctor_impl<FUNCTION_TYPE, true>::addAllViolatedLinearConstraintsRelaxedFunctor_impl(AddAllViolatedLinearConstraintsRelaxedFunctor& myself, const FUNCTION_TYPE& function) {
3357  typename FUNCTION_TYPE::ViolatedLinearConstraintsIteratorType violatedConstraintsBegin;
3358  typename FUNCTION_TYPE::ViolatedLinearConstraintsIteratorType violatedConstraintsEnd;
3359  typename FUNCTION_TYPE::ViolatedLinearConstraintsWeightsIteratorType violatedConstraintsWeightsBegin;
3360  function.challengeRelaxed(violatedConstraintsBegin, violatedConstraintsEnd, violatedConstraintsWeightsBegin, myself.labelingBegin_, myself.tolerance_);
3361  if(std::distance(violatedConstraintsBegin, violatedConstraintsEnd) > 0) {
3362  while(violatedConstraintsBegin != violatedConstraintsEnd) {
3363  myself.lpInference_->addLinearConstraint(myself.linearConstraintID_, *violatedConstraintsBegin);
3364  ++violatedConstraintsBegin;
3365  }
3366  myself.violatedConstraintAdded_ = true;
3367  }
3368 }
3369 
3370 template <class LP_INFERENCE_BASE_TYPE, typename LP_INFERENCE_BASE_TYPE::Parameter::ChallengeHeuristic HEURISTIC>
3371 template<class LINEAR_CONSTRAINT_FUNCTION_TYPE>
3372 inline void AddViolatedLinearConstraintsFunctor<LP_INFERENCE_BASE_TYPE, HEURISTIC>::operator()(const LINEAR_CONSTRAINT_FUNCTION_TYPE& linearConstraintFunction) {
3373  AddViolatedLinearConstraintsFunctor_impl<LINEAR_CONSTRAINT_FUNCTION_TYPE, meta::HasTypeInTypeList<typename LP_INFERENCE_BASE_TYPE::LinearConstraintFunctionTypeList, LINEAR_CONSTRAINT_FUNCTION_TYPE>::value>::addViolatedLinearConstraintsFunctor_impl(*this, linearConstraintFunction);
3374 }
3375 
3376 template <class LP_INFERENCE_BASE_TYPE, typename LP_INFERENCE_BASE_TYPE::Parameter::ChallengeHeuristic HEURISTIC>
3377 template<class FUNCTION_TYPE, bool IS_LINEAR_CONSTRAINT_FUNCTION>
3378 inline void AddViolatedLinearConstraintsFunctor<LP_INFERENCE_BASE_TYPE, HEURISTIC>::AddViolatedLinearConstraintsFunctor_impl<FUNCTION_TYPE, IS_LINEAR_CONSTRAINT_FUNCTION>::addViolatedLinearConstraintsFunctor_impl(AddViolatedLinearConstraintsFunctor<LP_INFERENCE_BASE_TYPE, HEURISTIC>& myself, const FUNCTION_TYPE& function) {
3379  throw RuntimeError(std::string("AddViolatedLinearConstraintsFunctor: Unsupported linear constraint function type") + typeid(FUNCTION_TYPE).name());
3380 }
3381 
3382 template <class LP_INFERENCE_BASE_TYPE, typename LP_INFERENCE_BASE_TYPE::Parameter::ChallengeHeuristic HEURISTIC>
3383 template<class FUNCTION_TYPE>
3384 inline void AddViolatedLinearConstraintsFunctor<LP_INFERENCE_BASE_TYPE, HEURISTIC>::AddViolatedLinearConstraintsFunctor_impl<FUNCTION_TYPE, true>::addViolatedLinearConstraintsFunctor_impl(AddViolatedLinearConstraintsFunctor<LP_INFERENCE_BASE_TYPE, HEURISTIC>& myself, const FUNCTION_TYPE& function) {
3385  typename FUNCTION_TYPE::ViolatedLinearConstraintsIteratorType violatedConstraintsBegin;
3386  typename FUNCTION_TYPE::ViolatedLinearConstraintsIteratorType violatedConstraintsEnd;
3387  typename FUNCTION_TYPE::ViolatedLinearConstraintsWeightsIteratorType violatedConstraintsWeightsBegin;
3388  function.challenge(violatedConstraintsBegin, violatedConstraintsEnd, violatedConstraintsWeightsBegin, myself.labelingBegin_, myself.tolerance_);
3389  if(std::distance(violatedConstraintsBegin, violatedConstraintsEnd) > 0) {
3390  while(violatedConstraintsBegin != violatedConstraintsEnd) {
3391  if(HEURISTIC == LP_INFERENCE_BASE_TYPE::Parameter::Random) {
3392  myself.lpInference_->addLinearConstraint(myself.linearConstraintID_, *violatedConstraintsBegin);
3393  ++violatedConstraintsBegin;
3394  ++myself.numConstraintsAdded_;
3395  if(myself.numConstraintsAdded_ == myself.lpInference_->parameter_.maxNumConstraintsPerIter_) {
3396  break;
3397  }
3398  } else {
3399  myself.sortedViolatedConstraintsList_->insert(typename LP_INFERENCE_BASE_TYPE::SortedViolatedConstraintsListType::value_type(*violatedConstraintsWeightsBegin, std::make_pair(myself.lpInference_->inactiveConstraints_.end(), std::make_pair(myself.linearConstraintID_, &(*violatedConstraintsBegin)))));
3400  if(myself.sortedViolatedConstraintsList_->size() > myself.lpInference_->parameter_.maxNumConstraintsPerIter_) {
3401  // remove constraints with to small weight
3402  myself.sortedViolatedConstraintsList_->erase(myself.sortedViolatedConstraintsList_->begin());
3403  OPENGM_ASSERT(myself.sortedViolatedConstraintsList_->size() == myself.lpInference_->parameter_.maxNumConstraintsPerIter_);
3404  }
3405  ++violatedConstraintsBegin;
3406  ++violatedConstraintsWeightsBegin;
3407  }
3408  }
3409  }
3410 }
3411 
3412 template <class LP_INFERENCE_BASE_TYPE, typename LP_INFERENCE_BASE_TYPE::Parameter::ChallengeHeuristic HEURISTIC>
3413 template<class LINEAR_CONSTRAINT_FUNCTION_TYPE>
3414 inline void AddViolatedLinearConstraintsRelaxedFunctor<LP_INFERENCE_BASE_TYPE, HEURISTIC>::operator()(const LINEAR_CONSTRAINT_FUNCTION_TYPE& linearConstraintFunction) {
3415  AddViolatedLinearConstraintsRelaxedFunctor_impl<LINEAR_CONSTRAINT_FUNCTION_TYPE, meta::HasTypeInTypeList<typename LP_INFERENCE_BASE_TYPE::LinearConstraintFunctionTypeList, LINEAR_CONSTRAINT_FUNCTION_TYPE>::value>::addViolatedLinearConstraintsRelaxedFunctor_impl(*this, linearConstraintFunction);
3416 }
3417 
3418 template <class LP_INFERENCE_BASE_TYPE, typename LP_INFERENCE_BASE_TYPE::Parameter::ChallengeHeuristic HEURISTIC>
3419 template<class FUNCTION_TYPE, bool IS_LINEAR_CONSTRAINT_FUNCTION>
3420 inline void AddViolatedLinearConstraintsRelaxedFunctor<LP_INFERENCE_BASE_TYPE, HEURISTIC>::AddViolatedLinearConstraintsRelaxedFunctor_impl<FUNCTION_TYPE, IS_LINEAR_CONSTRAINT_FUNCTION>::addViolatedLinearConstraintsRelaxedFunctor_impl(AddViolatedLinearConstraintsRelaxedFunctor<LP_INFERENCE_BASE_TYPE, HEURISTIC>& myself, const FUNCTION_TYPE& function) {
3421  throw RuntimeError(std::string("AddViolatedLinearConstraintsRelaxedFunctor: Unsupported linear constraint function type") + typeid(FUNCTION_TYPE).name());
3422 }
3423 
3424 template <class LP_INFERENCE_BASE_TYPE, typename LP_INFERENCE_BASE_TYPE::Parameter::ChallengeHeuristic HEURISTIC>
3425 template<class FUNCTION_TYPE>
3426 inline void AddViolatedLinearConstraintsRelaxedFunctor<LP_INFERENCE_BASE_TYPE, HEURISTIC>::AddViolatedLinearConstraintsRelaxedFunctor_impl<FUNCTION_TYPE, true>::addViolatedLinearConstraintsRelaxedFunctor_impl(AddViolatedLinearConstraintsRelaxedFunctor<LP_INFERENCE_BASE_TYPE, HEURISTIC>& myself, const FUNCTION_TYPE& function) {
3427  typename FUNCTION_TYPE::ViolatedLinearConstraintsIteratorType violatedConstraintsBegin;
3428  typename FUNCTION_TYPE::ViolatedLinearConstraintsIteratorType violatedConstraintsEnd;
3429  typename FUNCTION_TYPE::ViolatedLinearConstraintsWeightsIteratorType violatedConstraintsWeightsBegin;
3430  function.challengeRelaxed(violatedConstraintsBegin, violatedConstraintsEnd, violatedConstraintsWeightsBegin, myself.labelingBegin_, myself.tolerance_);
3431  if(std::distance(violatedConstraintsBegin, violatedConstraintsEnd) > 0) {
3432  while(violatedConstraintsBegin != violatedConstraintsEnd) {
3433  if(HEURISTIC == LP_INFERENCE_BASE_TYPE::Parameter::Random) {
3434  myself.lpInference_->addLinearConstraint(myself.linearConstraintID_, *violatedConstraintsBegin);
3435  ++violatedConstraintsBegin;
3436  ++myself.numConstraintsAdded_;
3437  if(myself.numConstraintsAdded_ == myself.lpInference_->parameter_.maxNumConstraintsPerIter_) {
3438  break;
3439  }
3440  } else {
3441  myself.sortedViolatedConstraintsList_->insert(typename LP_INFERENCE_BASE_TYPE::SortedViolatedConstraintsListType::value_type(*violatedConstraintsWeightsBegin, std::make_pair(myself.lpInference_->inactiveConstraints_.end(), std::make_pair(myself.linearConstraintID_, &(*violatedConstraintsBegin)))));
3442  if(myself.sortedViolatedConstraintsList_->size() > myself.lpInference_->parameter_.maxNumConstraintsPerIter_) {
3443  // remove constraints with to small weight
3444  myself.sortedViolatedConstraintsList_->erase(myself.sortedViolatedConstraintsList_->begin());
3445  OPENGM_ASSERT(myself.sortedViolatedConstraintsList_->size() == myself.lpInference_->parameter_.maxNumConstraintsPerIter_);
3446  }
3447  ++violatedConstraintsBegin;
3448  ++violatedConstraintsWeightsBegin;
3449  }
3450  }
3451  }
3452 }
3453 
3454 } // namespace opengm
3455 
3456 #endif /* OPENGM_LP_INFERENCE_BASE_HXX_ */
opengm::LinearConstraint::indicatorVariablesBegin
IndicatorVariablesIteratorType indicatorVariablesBegin() const
Get the begin iterator to the set of indicator variables.
Definition: linear_constraint.hxx:507
opengm::LPInferenceBase::LPInferenceBase
LPInferenceBase(const GraphicalModelType &gm, const Parameter &parameter=Parameter())
LPInferenceBase constructor.
Definition: lp_inference_base.hxx:1828
OPENGM_FLOAT_TOL
#define OPENGM_FLOAT_TOL
Definition: function_properties_base.hxx:23
opengm::LPInferenceBase::InactiveConstraintsListIteratorType
InactiveConstraintsListType::iterator InactiveConstraintsListIteratorType
Typedef of the iterator type used to iterate over a set of LPInferenceBase::ConstraintStorage objects...
Definition: lp_inference_base.hxx:107
opengm::LPInferenceBase::GetLinearConstraintsBeginFunctor::GetLinearConstraintsBeginFunctor_impl
Helper struct to distinguish between linear constraint functions and other function types...
Definition: lp_inference_base.hxx:153
opengm::LPInferenceBase::SolverIndexType
LPInferenceTraitsType::SolverIndexType SolverIndexType
Typedef of the index type used by the LP/MIP solver.
Definition: lp_inference_base.hxx:54
opengm::LPFunctionTransfer::GetLinearConstraintsFunctor
Functor to call LPFunctionTransfer::getLinearConstraints() for a factor of the graphical model...
Definition: lp_functiontransfer.hxx:67
opengm::LPInferenceBase::bound
virtual ValueType bound() const
Get the current bound.
Definition: lp_inference_base.hxx:1783
opengm::LPInferenceBase::AddAllViolatedLinearConstraintsRelaxedFunctor
Functor used to access the method challengeRelaxed() of the underlying linear constraint function of ...
Definition: lp_inference_base.hxx:197
opengm::LPInferenceBase::LinearConstraintsIteratorType
LinearConstraintsContainerType::const_iterator LinearConstraintsIteratorType
Typedef of the iterator type used to iterate over a set of linear constraints.
Definition: lp_inference_base.hxx:45
opengm::LPInferenceBase::AddAllViolatedLinearConstraintsRelaxedFunctor::linearConstraintID_
IndexType linearConstraintID_
Index of the linear constraint factor.
Definition: lp_inference_base.hxx:203
opengm::LPInferenceBase::IndicatorVariableType
LinearConstraintType::IndicatorVariableType IndicatorVariableType
Typedef of the indicator variable type used within linear constraints.
Definition: lp_inference_base.hxx:46
opengm::LinearConstraint::coefficientsBegin
CoefficientsIteratorType coefficientsBegin() const
Get the begin iterator to the set of coefficients for the indicator variables.
Definition: linear_constraint.hxx:517
opengm::LPInferenceBase::GraphicalModelType
LPInferenceTraitsType::GraphicalModelType GraphicalModelType
Typedef of the graphical model type.
Definition: lp_inference_base.hxx:36
opengm::LPInferenceBase::LPInferenceBaseType
LPInferenceBase< LPInferenceType > LPInferenceBaseType
Typedef of the opengm::LPInferenceBase class with appropriate template parameter. ...
Definition: lp_inference_base.hxx:34
opengm
The OpenGM namespace.
Definition: config.hxx:43
opengm::LPInferenceBase::GetIndicatorVariablesOrderEndFunctor::indicatorVariablesOrderEnd_
IndicatorVariablesIteratorType indicatorVariablesOrderEnd_
Storage for the iterator returned by the method indicatorVariablesOrderEnd().
Definition: lp_inference_base.hxx:131
opengm::LPInferenceBase::IndicatorVariablesIteratorType
LinearConstraintType::IndicatorVariablesIteratorType IndicatorVariablesIteratorType
Typedef of the iterator type used to iterate over a set of indicator variables.
Definition: lp_inference_base.hxx:48
opengm::LPInferenceBase
Base class for Linear Programming based inference.
Definition: lp_inference_base.hxx:29
opengm::LPInferenceBase::Parameter::LocalPolytope
LocalPolytope will use a first order local polytope approximation of the marginal polytope...
Definition: lp_inference_base.hxx:67
opengm::LPInferenceBase::infer_impl_selectHeuristic
InferenceTermination infer_impl_selectHeuristic(VISITOR_TYPE &visitor)
Helper function for LPInferenceBase::infer_impl to select the challenge heuristic template parameter...
Definition: lp_inference_base.hxx:2785
opengm::LPInferenceBase::linearConstraintFactors_
std::vector< IndexType > linearConstraintFactors_
List of all linear constraint factors.
Definition: lp_inference_base.hxx:229
opengm::LPInferenceBase::ConstraintStorage::variableIDs_
std::vector< SolverIndexType > variableIDs_
The variables of the LP/MIP model which are used in the constraint.
Definition: lp_inference_base.hxx:98
marray::Iterator
STL-compliant random access iterator for View and Marray.
Definition: marray.hxx:49
opengm::Timer::reset
void reset()
Definition: timer.hxx:124
opengm::LPInferenceBase::IndicatorVariablesContainerType
LinearConstraintType::IndicatorVariablesContainerType IndicatorVariablesContainerType
Typedef of the container type used to store a set of indicator variables.
Definition: lp_inference_base.hxx:47
opengm::LPFunctionTransfer::GetSlackVariablesOrderFunctor::order_
IndicatorVariablesContainerType * order_
Pointer to the storage for the return value of the LPFunctionTransfer::getSlackVariablesOrder() metho...
Definition: lp_functiontransfer.hxx:53
opengm::LPInferenceBase::Parameter::LoosePolytope
LoosePolytope will add no constraints at all. All linear constraints will be added iteratively only i...
Definition: lp_inference_base.hxx:67
opengm::LPInferenceBase::SolverValueType
LPInferenceTraitsType::SolverValueType SolverValueType
Typedef of the value type used by the LP/MIP solver.
Definition: lp_inference_base.hxx:55
opengm::LPInferenceBase::Parameter::TightPolytope
TightPolytope will add all constraints of the LocalPolytope relaxation and furthermore all constraint...
Definition: lp_inference_base.hxx:67
opengm::LinearConstraint::IndicatorVariablesIteratorType
IndicatorVariablesContainerType::const_iterator IndicatorVariablesIteratorType
Defines the const iterator type to iterate over the set of indicator variables.
Definition: linear_constraint.hxx:36
opengm::LPInferenceBase::Parameter::useFunctionTransfer_
bool useFunctionTransfer_
Use function transfer if available to generate more efficient LP/MIP models.
Definition: lp_inference_base.hxx:76
opengm::IndicatorVariable::begin
IteratorType begin() const
Get the iterator over the sequence of variable label pairs from the indicator variable.
Definition: indicator_variable.hxx:539
opengm::LPInferenceBase::addLoosePolytopeConstraints
void addLoosePolytopeConstraints()
Add all constraints to the lp model which are required by the loose polytope relaxation.
Definition: lp_inference_base.hxx:2278
opengm::LPInferenceBase::numSlackVariables_
SolverIndexType numSlackVariables_
The number of slack variables for the transferable factors of the graphical model.
Definition: lp_inference_base.hxx:237
linear_constraint_function_base.hxx
Provides interface for liner constraint functions.
opengm::LPInferenceBase::addLinearConstraint
void addLinearConstraint(const IndexType linearConstraintFactor, const LinearConstraintType &constraint)
Add a new linear constraint from a linear constraint function to the lp model.
Definition: lp_inference_base.hxx:2742
opengm::LinearConstraint::VariableLabelPairsIteratorType
IndicatorVariableType::IteratorType VariableLabelPairsIteratorType
Defines the const iterator type to iterate over the variable label pairs of an indicator variable...
Definition: linear_constraint.hxx:35
opengm::LPInferenceBase::~LPInferenceBase
virtual ~LPInferenceBase()
LPInferenceBase destructor.
Definition: lp_inference_base.hxx:1891
opengm::LPInferenceBase::GetIndicatorVariablesOrderBeginFunctor::GetIndicatorVariablesOrderBeginFunctor_impl
Helper struct to distinguish between linear constraint functions and other function types...
Definition: lp_inference_base.hxx:121
opengm::LPInferenceBase::gm_
const GraphicalModelType & gm_
Reference to the graphical model.
Definition: lp_inference_base.hxx:224
opengm::LPInferenceBase::GetLinearConstraintsBeginFunctor
Functor used to access the method linearConstraintsBegin() of the underlying linear constraint functi...
Definition: lp_inference_base.hxx:145
marray::View::end
iterator end()
Get the end-iterator.
Definition: marray.hxx:2727
opengm::AddViolatedLinearConstraintsRelaxedFunctor::labelingBegin_
LP_INFERENCE_BASE_TYPE::RelaxedSolutionSubsequenceIterator labelingBegin_
Iterator used to iterate over the current solution.
Definition: lp_inference_base.hxx:335
opengm::LPInferenceBase::GetIndicatorVariablesOrderEndFunctor::GetIndicatorVariablesOrderEndFunctor_impl
Helper struct to distinguish between linear constraint functions and other function types...
Definition: lp_inference_base.hxx:137
opengm::LinearConstraint::coefficientsEnd
CoefficientsIteratorType coefficientsEnd() const
Get the end iterator to the set of coefficients for the indicator variables.
Definition: linear_constraint.hxx:522
opengm::LPInferenceBase::LinearConstraintsContainerType
std::vector< LinearConstraintType > LinearConstraintsContainerType
Typedef of the container type used to store a set of linear constraints.
Definition: lp_inference_base.hxx:44
opengm::LPInferenceBase::tightenPolytope
bool tightenPolytope()
Search for linear constraints which are violated by the current integer solution and add them to the ...
Definition: lp_inference_base.hxx:2899
opengm::LPInferenceBase::higherOrderFactors_
std::vector< IndexType > higherOrderFactors_
List of all higher order factors.
Definition: lp_inference_base.hxx:228
opengm::LPInferenceBase::addLPVariables
void addLPVariables()
Add the number of lp variables computed by LPInferenceBase::countLPVariables to the lp model...
Definition: lp_inference_base.hxx:2123
opengm::LPInferenceBase::value
virtual ValueType value() const
Get the current value.
Definition: lp_inference_base.hxx:1793
opengm::Timer::toc
void toc()
Definition: timer.hxx:109
opengm::LinearConstraint::IndicatorVariablesContainerType
std::vector< IndicatorVariableType > IndicatorVariablesContainerType
Defines the storage type for the set of indicator variables.
Definition: linear_constraint.hxx:29
opengm::LPInferenceBase::addInactiveConstraint
void addInactiveConstraint(const ConstraintStorage &constraint)
Add a linear constraint from the local polytope constraint to the LP/MIP model.
Definition: lp_inference_base.hxx:3224
opengm::AddViolatedLinearConstraintsFunctor::tolerance_
LP_INFERENCE_BASE_TYPE::ValueType tolerance_
The tolerance used for the method challenge() of the underlying linear constraint function of a graph...
Definition: lp_inference_base.hxx:312
opengm::AddViolatedLinearConstraintsRelaxedFunctor::AddViolatedLinearConstraintsRelaxedFunctor_impl
Helper struct to distinguish between linear constraint functions and other function types...
Definition: lp_inference_base.hxx:345
opengm::AddViolatedLinearConstraintsFunctor::lpInference_
LP_INFERENCE_BASE_TYPE * lpInference_
Pointer pointing to the instance of opengm::LPInferenceBase to get access to the LP/MIP model...
Definition: lp_inference_base.hxx:315
marray::View
Array-Interface to an interval of memory.
Definition: marray.hxx:44
opengm::LPInferenceBase::countLPVariables
void countLPVariables()
Count the number of lp variables required to build a lp model for inference of the graphical model...
Definition: lp_inference_base.hxx:1916
opengm::SubsequenceIterator
Defines the const iterator type to iterate over the subset of a sequence.
Definition: subsequence_iterator.hxx:12
opengm::Timer
Platform-independent runtime measurements.
Definition: timer.hxx:29
opengm::LPInferenceBase::GetLinearConstraintsEndFunctor
Functor used to access the method linearConstraintsEnd() of the underlying linear constraint function...
Definition: lp_inference_base.hxx:161
opengm::LPInferenceBase::AddAllViolatedLinearConstraintsRelaxedFunctor::AddAllViolatedLinearConstraintsRelaxedFunctor_impl
Helper struct to distinguish between linear constraint functions and other function types...
Definition: lp_inference_base.hxx:209
opengm::AddViolatedLinearConstraintsFunctor::numConstraintsAdded_
size_t numConstraintsAdded_
Indicator used to tell how many constraints were added to the LP/MIP model.
Definition: lp_inference_base.hxx:314
opengm::LPInferenceBase::TimingVisitorType
visitors::TimingVisitor< LPInferenceBaseType > TimingVisitorType
Typedef of the opengm::visitors::TimingVisitor class with appropriate template parameter.
Definition: lp_inference_base.hxx:41
opengm::LPFunctionTransfer::NumSlackVariablesFunctor
Functor to call LPFunctionTransfer::numSlackVariables() for a graphical model factor.
Definition: lp_functiontransfer.hxx:47
opengm::LPInferenceBase::SolverType
LPInferenceTraitsType::SolverType SolverType
Typedef of the solver type used to solve the LP or MIP which is generated from the graphical model...
Definition: lp_inference_base.hxx:53
opengm::LPInferenceBase::Parameter::mergeParallelFactors_
bool mergeParallelFactors_
Merge factors which are connected to the same set of variables. Might increase construction time but ...
Definition: lp_inference_base.hxx:77
OPENGM_ASSERT
#define OPENGM_ASSERT(expression)
Definition: opengm.hxx:77
opengm::LPInferenceBase::VerboseVisitorType
visitors::VerboseVisitor< LPInferenceBaseType > VerboseVisitorType
Typedef of the opengm::visitors::VerboseVisitor class with appropriate template parameter.
Definition: lp_inference_base.hxx:39
opengm::LPInferenceBase::numTransferedFactorsLPVariables
SolverIndexType numTransferedFactorsLPVariables
The number of lp variables for the transferable factors of the graphical model.
Definition: lp_inference_base.hxx:236
opengm::LPInferenceBase::infer
virtual InferenceTermination infer()
Run inference with empty visitor.
Definition: lp_inference_base.hxx:1768
opengm::LPInferenceBase::Parameter::tolerance_
ValueType tolerance_
Tolerance for violation of linear constraints.
Definition: lp_inference_base.hxx:83
opengm::LPInferenceBase::InactiveConstraintsListType
std::list< ConstraintStorage > InactiveConstraintsListType
Typedef of the container type used to sore a set of LPInferenceBase::ConstraintStorage objects...
Definition: lp_inference_base.hxx:106
opengm::LPInferenceBase::infer_impl_selectLPType
InferenceTermination infer_impl_selectLPType(VISITOR_TYPE &visitor)
Helper function for LPInferenceBase::infer_impl to select the use integer constraints template parame...
Definition: lp_inference_base.hxx:2821
marray::View::boundView
View< T, isConst, A > boundView(const size_t, const size_t=0) const
Get a View where one coordinate is bound to a value.
Definition: marray.hxx:2374
opengm::AddViolatedLinearConstraintsFunctor::linearConstraintID_
LP_INFERENCE_BASE_TYPE::IndexType linearConstraintID_
Index of the linear constraint factor.
Definition: lp_inference_base.hxx:316
opengm::LPInferenceBase::ConstraintStorage
Storage class for linear constraints representing the local polytope constraints. They are generated ...
Definition: lp_inference_base.hxx:97
opengm::LPFunctionTransfer::SlackVariablesObjectiveCoefficientsContainerType
std::vector< ValueType > SlackVariablesObjectiveCoefficientsContainerType
Defines the container type which is used to store the coefficients of the slack variables for the obj...
Definition: lp_functiontransfer.hxx:25
opengm::LPInferenceBase::setAccumulation
void setAccumulation()
Set the accumulation for the lp solver.
Definition: lp_inference_base.hxx:2112
opengm::LPInferenceBase::Parameter::Relaxation
Relaxation
This enum defines the type of the linear programming model which is used for inference.
Definition: lp_inference_base.hxx:67
opengm::LPInferenceBase::arg
virtual InferenceTermination arg(std::vector< LabelType > &x, const size_t N=1) const
Get the current argument.
Definition: lp_inference_base.hxx:1800
opengm::LPInferenceBase::SolverTimingType
LPInferenceTraitsType::SolverTimingType SolverTimingType
Typedef of the type used by the LP/MIP solver to measure timings.
Definition: lp_inference_base.hxx:57
opengm::LPInferenceBase::SolverParameterType
LPInferenceTraitsType::SolverParameterType SolverParameterType
Typedef of the parameter class used by the LP/MIP solver.
Definition: lp_inference_base.hxx:58
opengm::LPInferenceBase::createObjectiveFunction
void createObjectiveFunction()
Create the objective function for the lp model.
Definition: lp_inference_base.hxx:2145
opengm::LPInferenceBase::EmptyVisitorType
visitors::EmptyVisitor< LPInferenceBaseType > EmptyVisitorType
Typedef of the opengm::visitors::EmptyVisitor class with appropriate template parameter.
Definition: lp_inference_base.hxx:40
opengm::LPInferenceBase::LPInferenceType
LP_INFERENCE_TYPE LPInferenceType
Typedef of the child class which inherits from opengm::LPInferenceBase.
Definition: lp_inference_base.hxx:32
opengm::LPInferenceBase::ConstraintStorage::name_
std::string name_
The name of the constraint.
Definition: lp_inference_base.hxx:102
opengm::LPInferenceBase::tightenPolytopeRelaxed
bool tightenPolytopeRelaxed()
Search for linear constraints which are violated by the current relaxed solution and add them to the ...
Definition: lp_inference_base.hxx:3043
marray::View::begin
iterator begin()
Get an iterator to the beginning.
Definition: marray.hxx:2714
opengm::LPInferenceBase::Parameter::maxNumIterations_
size_t maxNumIterations_
Maximum number of tightening iterations (infinite if set to 0).
Definition: lp_inference_base.hxx:80
opengm::LPInferenceBase::Parameter::challengeHeuristic_
ChallengeHeuristic challengeHeuristic_
Heuristic on how to select violated constraints.
Definition: lp_inference_base.hxx:82
opengm::LPInferenceBase::inactiveConstraints_
InactiveConstraintsListType inactiveConstraints_
Storage for all linear constraints representing the local polytope constraints. They are generated an...
Definition: lp_inference_base.hxx:250
opengm::LPInferenceBase::GetLinearConstraintsEndFunctor::GetLinearConstraintsEndFunctor_impl
Helper struct to distinguish between linear constraint functions and other function types...
Definition: lp_inference_base.hxx:169
opengm::LPInferenceBase::GetIndicatorVariablesOrderBeginFunctor::indicatorVariablesOrderBegin_
IndicatorVariablesIteratorType indicatorVariablesOrderBegin_
Storage for the iterator returned by the method indicatorVariablesOrderBegin().
Definition: lp_inference_base.hxx:115
opengm::LPFunctionTransfer::GetLinearConstraintsFunctor::constraints_
LinearConstraintsContainerType * constraints_
Pointer to the storage for the return value of the LPFunctionTransfer::getLinearConstraints() method...
Definition: lp_functiontransfer.hxx:68
opengm::LPFunctionTransfer::NumSlackVariablesFunctor::numSlackVariables_
IndexType numSlackVariables_
Storage for the return value of the LPFunctionTransfer::numSlackVariables() method.
Definition: lp_functiontransfer.hxx:48
opengm::AddViolatedLinearConstraintsRelaxedFunctor::lpInference_
LP_INFERENCE_BASE_TYPE * lpInference_
Pointer pointing to the instance of opengm::LPInferenceBase to get access to the LP/MIP model...
Definition: lp_inference_base.hxx:337
opengm::LPInferenceBase::addLocalPolytopeVariableConstraint
void addLocalPolytopeVariableConstraint(const IndexType variableID, const bool addToModel)
Add a new variable constraint to the lp model.
Definition: lp_inference_base.hxx:2467
opengm::LPInferenceBase::numLinearConstraintsLPVariables_
SolverIndexType numLinearConstraintsLPVariables_
The number of lp variables for the linear constraint factors of the graphical model.
Definition: lp_inference_base.hxx:235
opengm::LPInferenceBase::Parameter::maxNumConstraintsPerIter_
size_t maxNumConstraintsPerIter_
Maximum number of violated constraints which are added per tightening iteration (all if set to 0)...
Definition: lp_inference_base.hxx:81
opengm::LPInferenceBase::AddAllViolatedLinearConstraintsFunctor::lpInference_
LPInferenceBaseType * lpInference_
Pointer pointing to the instance of opengm::LPInferenceBase to get access to the LP/MIP model...
Definition: lp_inference_base.hxx:182
opengm::LPInferenceBase::Parameter::Parameter
Parameter()
Parameter constructor setting default value for all options.
Definition: lp_inference_base.hxx:1752
opengm::LPInferenceBase::ConstraintStorage::bound_
SolverValueType bound_
The value for the right hand side of the constraint.
Definition: lp_inference_base.hxx:100
lp_functiontransfer.hxx
opengm::LPInferenceBase::sortFactors
void sortFactors()
Sorts the factors of the graphical model into the lists unaryFactors_, higherOrderFactors_, linearConstraintFactors_ and transferableFactors_.
Definition: lp_inference_base.hxx:1896
opengm::LPInferenceBase::AddAllViolatedLinearConstraintsRelaxedFunctor::lpInference_
LPInferenceBaseType * lpInference_
Pointer pointing to the instance of opengm::LPInferenceBase to get access to the LP/MIP model...
Definition: lp_inference_base.hxx:202
opengm::AddViolatedLinearConstraintsRelaxedFunctor::numConstraintsAdded_
size_t numConstraintsAdded_
Indicator used to tell how many constraints were added to the LP/MIP model.
Definition: lp_inference_base.hxx:336
opengm::LPFunctionTransfer::GetSlackVariablesObjectiveCoefficientsFunctor::coefficients_
SlackVariablesObjectiveCoefficientsContainerType * coefficients_
Pointer to the storage for the return value of the LPFunctionTransfer::getSlackVariablesObjectiveCoef...
Definition: lp_functiontransfer.hxx:58
opengm::LPFunctionTransfer
Provides transformations for some function types when they are used in inference algorithms which use...
Definition: lp_functiontransfer.hxx:15
opengm::LPInferenceBase::AddAllViolatedLinearConstraintsFunctor::tolerance_
ValueType tolerance_
The tolerance used for the method challenge() of the underlying linear constraint function of a graph...
Definition: lp_inference_base.hxx:179
opengm::LPInferenceBase::numLPVariables_
SolverIndexType numLPVariables_
The total number of lp variables except slack variables.
Definition: lp_inference_base.hxx:232
opengm::LPInferenceBase::IntegerSolutionSubsequenceIterator
SubsequenceIterator< typename std::vector< LabelType >::const_iterator, typename std::vector< size_t >::const_iterator > IntegerSolutionSubsequenceIterator
Typedef of the iterator type used to iterate over a subset of the computed solution. This iterator type is used to challenge the linear constraint functions present in the model. Only used when the problem is solved as a MIP.
Definition: lp_inference_base.hxx:60
opengm::LPInferenceBase::Parameter::relaxation_
Relaxation relaxation_
Selected relaxation method.
Definition: lp_inference_base.hxx:79
opengm::LPFunctionTransfer::GetSlackVariablesOrderFunctor
Functor to call LPFunctionTransfer::getSlackVariablesOrder() for a factor of the graphical model...
Definition: lp_functiontransfer.hxx:52
opengm::IndicatorVariable::getLogicalOperatorType
LogicalOperatorType getLogicalOperatorType() const
Get the logical operator type of the indicator variable.
Definition: indicator_variable.hxx:549
opengm::LPInferenceBase::addTightPolytopeConstraints
void addTightPolytopeConstraints()
Add all constraints to the lp model which are required by the tight polytope relaxation.
Definition: lp_inference_base.hxx:2356
opengm::LPFunctionTransfer::IndicatorVariablesContainerType
std::vector< IndicatorVariableType > IndicatorVariablesContainerType
Defines the indicator variables container type which is used to store multiple indicator variables...
Definition: lp_functiontransfer.hxx:24
opengm::LPInferenceBase::LinearConstraintFunctionTypeList
meta::GetLinearConstraintFunctionTypeList< typename GraphicalModelType::FunctionTypeList >::type LinearConstraintFunctionTypeList
Typelist of all linear constraint function types which are present in the graphical model type...
Definition: lp_inference_base.hxx:221
opengm::Timer::tic
void tic()
Definition: timer.hxx:96
opengm::LPInferenceBase::AddAllViolatedLinearConstraintsFunctor::violatedConstraintAdded_
bool violatedConstraintAdded_
Indicator used to tell if at least one constraint was added to the LP/MIP model.
Definition: lp_inference_base.hxx:181
opengm::IndicatorVariable::end
IteratorType end() const
Get the end iterator of the sequence of variable label pairs from the indicator variable.
Definition: indicator_variable.hxx:544
opengm::LPInferenceBase::LPFunctionTransferType
LPFunctionTransfer< ValueType, IndexType, LabelType > LPFunctionTransferType
Typedef of the opengm::LPFunctionTransfer class with appropriate template parameter.
Definition: lp_inference_base.hxx:51
opengm::LPInferenceBase::infer_impl_selectViolatedConstraints
InferenceTermination infer_impl_selectViolatedConstraints(VISITOR_TYPE &visitor)
Helper function for LPInferenceBase::infer_impl to select the add all violated constraints template p...
Definition: lp_inference_base.hxx:2811
opengm::LPFunctionTransfer::GetIndicatorVariablesFunctor::variables_
IndicatorVariablesContainerType * variables_
Pointer to the storage for the return value of the LPFunctionTransfer::getIndicatorVariables() method...
Definition: lp_functiontransfer.hxx:63
opengm::LPInferenceBase::Parameter::integerConstraintNodeVar_
bool integerConstraintNodeVar_
Use integer constraints for node variables.
Definition: lp_inference_base.hxx:73
opengm::LinearConstraint::indicatorVariablesEnd
IndicatorVariablesIteratorType indicatorVariablesEnd() const
Get the end iterator to the set of indicator variables.
Definition: linear_constraint.hxx:512
opengm::LPInferenceBase::SolverSolutionIteratorType
LPInferenceTraitsType::SolverSolutionIteratorType SolverSolutionIteratorType
Typedef of the iterator type used to iterate over the computed solution from the LP/MIP solver...
Definition: lp_inference_base.hxx:56
opengm::LPInferenceBase::LPInferenceTraitsType
LPInferenceTraits< LPInferenceType > LPInferenceTraitsType
Typedef of the opengm::LPInferenceTraits class with appropriate template parameter.
Definition: lp_inference_base.hxx:33
opengm::LPInferenceBase::AddAllViolatedLinearConstraintsRelaxedFunctor::tolerance_
ValueType tolerance_
The tolerance used for the method challengeRelaxed() of the underlying linear constraint function of ...
Definition: lp_inference_base.hxx:199
opengm::LPInferenceBase::constValue_
ValueType constValue_
Constant value offset.
Definition: lp_inference_base.hxx:226
opengm::IndicatorVariable
Combine a group of variables to a new variable.
Definition: indicator_variable.hxx:14
opengm::Inference
Inference algorithm interface.
Definition: inference.hxx:43
opengm::LPInferenceBase::unaryFactors_
std::vector< IndexType > unaryFactors_
List of all unary factors.
Definition: lp_inference_base.hxx:227
opengm::LPInferenceBase::addLocalPolytopeFactorConstraint
void addLocalPolytopeFactorConstraint(const IndexType factor, const IndexType variable, const LabelType label, const bool addToModel)
Add a new factor constraint to the lp model.
Definition: lp_inference_base.hxx:2500
opengm::LPInferenceBase::GetLinearConstraintsEndFunctor::linearConstraintsEnd_
LinearConstraintsIteratorType linearConstraintsEnd_
Storage for the iterator returned by the method linearConstraintsEnd().
Definition: lp_inference_base.hxx:163
opengm::LPInferenceBase::Parameter::Weighted
Weighted will add constraints sorted by their weights. This is only meaningful if the maximum number ...
Definition: lp_inference_base.hxx:68
opengm::LPInferenceBase::checkInactiveConstraint
void checkInactiveConstraint(const ConstraintStorage &constraint, double &weight) const
Check if a given linear constraint from the local polytope constraints is violated.
Definition: lp_inference_base.hxx:3188
opengm::LPInferenceBase::Parameter::integerConstraintFactorVar_
bool integerConstraintFactorVar_
Use integer constraints for factor variables.
Definition: lp_inference_base.hxx:74
opengm::LPInferenceBase::addLocalPolytopeFactorConstraintCacheFactorLPVariableIDs_
marray::Marray< SolverIndexType > addLocalPolytopeFactorConstraintCacheFactorLPVariableIDs_
Lookup table for the factor lp variable ids required by the LPInferenceBase::addLocalPolytopeFactorCo...
Definition: lp_inference_base.hxx:249
opengm::LPInferenceBase::factorLPVariableIndex
SolverIndexType factorLPVariableIndex(const IndexType factorID, const size_t labelingIndex) const
Get the lp variable which corresponds to the labeling of the factor.
Definition: lp_inference_base.hxx:2383
linear_constraint.hxx
Provides implementation for class LinearConstraint.
opengm::LPInferenceBase::AccumulationType
LPInferenceTraitsType::AccumulationType AccumulationType
Typedef of the Accumulation type.
Definition: lp_inference_base.hxx:35
opengm::LPInferenceBase::numFactorsLPVariables_
SolverIndexType numFactorsLPVariables_
The number of lp variables for the factors of the graphical model.
Definition: lp_inference_base.hxx:234
opengm::LPInferenceBase::transferedFactorsLPVariablesIndicesLookupTable_
std::vector< std::map< const IndicatorVariableType, SolverIndexType > > transferedFactorsLPVariablesIndicesLookupTable_
Lookup table for the lp variable indices of each transferable factor.
Definition: lp_inference_base.hxx:244
opengm::LPInferenceBase::SortedViolatedConstraintsListType
std::multimap< double, InactiveConstraintFactorConstraintPairType > SortedViolatedConstraintsListType
Typedef of the map type used to store a set of violated constraints sorted by their weights...
Definition: lp_inference_base.hxx:110
opengm::LPInferenceBase::GetIndicatorVariablesOrderEndFunctor
Functor used to access the method indicatorVariablesOrderEnd() of the underlying linear constraint fu...
Definition: lp_inference_base.hxx:129
opengm::AddViolatedLinearConstraintsRelaxedFunctor
Functor used to access the method challengeRelaxed() of the underlying linear constraint function of ...
Definition: lp_inference_base.hxx:332
opengm::LPFunctionTransfer::IsTransferableFunctor::isTransferable_
bool isTransferable_
Storage for the return value of the LPFunctionTransfer::isTransferable() method.
Definition: lp_functiontransfer.hxx:43
opengm::LPInferenceBase::Parameter::nameConstraints_
bool nameConstraints_
Create unique names for the linear constraints added to the model (might be helpful for debugging mod...
Definition: lp_inference_base.hxx:78
opengm::LPInferenceBase::infer_impl
InferenceTermination infer_impl(VISITOR_TYPE &visitor)
The implementation of the inference method.
Definition: lp_inference_base.hxx:2831
opengm::AddViolatedLinearConstraintsRelaxedFunctor::sortedViolatedConstraintsList_
LP_INFERENCE_BASE_TYPE::SortedViolatedConstraintsListType * sortedViolatedConstraintsList_
Storage for the violated linear constraints sorted by their weights. Only used when LPInferenceBase::...
Definition: lp_inference_base.hxx:339
opengm::Timer::elapsedTime
double elapsedTime() const
Definition: timer.hxx:130
opengm::LPInferenceBase::nodesLPVariablesOffset_
std::vector< SolverIndexType > nodesLPVariablesOffset_
The offsets for the indices of the lp variables for each node of the graphical model.
Definition: lp_inference_base.hxx:240
opengm::AddViolatedLinearConstraintsFunctor
Functor used to access the method challenge() of the underlying linear constraint function of a graph...
Definition: lp_inference_base.hxx:310
opengm::LPFunctionTransfer::GetSlackVariablesObjectiveCoefficientsFunctor
Functor to call LPFunctionTransfer::getSlackVariablesObjectiveCoefficients() for a factor of the grap...
Definition: lp_functiontransfer.hxx:57
opengm::AddViolatedLinearConstraintsFunctor::labelingBegin_
LP_INFERENCE_BASE_TYPE::IntegerSolutionSubsequenceIterator labelingBegin_
Iterator used to iterate over the current solution.
Definition: lp_inference_base.hxx:313
opengm::LPInferenceBase::LinearConstraintType
LinearConstraint< ValueType, IndexType, LabelType > LinearConstraintType
Typedef of the opengm::LinearConstraint class with appropriate template parameter. Used to represent linear constraints.
Definition: lp_inference_base.hxx:43
opengm::LinearConstraint::getConstraintOperator
LinearConstraintOperatorValueType getConstraintOperator() const
Get the constraint operator of the linear constraint.
Definition: linear_constraint.hxx:532
opengm::LPFunctionTransfer::IsTransferableFunctor
Functor to call LPFunctionTransfer::isTransferable() for a factor of the graphical model...
Definition: lp_functiontransfer.hxx:42
opengm::LPInferenceBase::infer_impl_selectIterations
InferenceTermination infer_impl_selectIterations(VISITOR_TYPE &visitor)
Helper function for LPInferenceBase::infer_impl to select the use infinite iterations template parame...
Definition: lp_inference_base.hxx:2801
opengm::LPInferenceBase::addLocalPolytopeFactorConstraintCachePreviousFactorID_
IndexType addLocalPolytopeFactorConstraintCachePreviousFactorID_
Cache for the function LPInferenceBase::addLocalPolytopeFactorConstraint. It is used to store the fac...
Definition: lp_inference_base.hxx:248
opengm::LPInferenceBase::Parameter::useSoftConstraints_
bool useSoftConstraints_
If constraint factors are present in the model add them as soft constraints e.g. treat them as normal...
Definition: lp_inference_base.hxx:75
opengm::LPInferenceBase::GetIndicatorVariablesOrderBeginFunctor
Functor used to access the method indicatorVariablesOrderBegin() of the underlying linear constraint ...
Definition: lp_inference_base.hxx:113
opengm::LPInferenceBase::Parameter::ChallengeHeuristic
ChallengeHeuristic
This enum defines the heuristic by which the violated constraints are added to the LP/MIP model...
Definition: lp_inference_base.hxx:68
opengm::LPInferenceBase::parameter_
const Parameter parameter_
Parameter which stores the settings for the inference.
Definition: lp_inference_base.hxx:225
opengm::LPInferenceBase::AddAllViolatedLinearConstraintsRelaxedFunctor::labelingBegin_
RelaxedSolutionSubsequenceIterator labelingBegin_
Iterator used to iterate over the current solution.
Definition: lp_inference_base.hxx:200
opengm::LPInferenceBase::ConstraintStorage::operator_
LinearConstraintType::LinearConstraintOperatorValueType operator_
The operator type used to compare the left hand side of the constraint against the right hand side (<...
Definition: lp_inference_base.hxx:101
opengm::LPInferenceBase::addIndicatorVariableConstraints
void addIndicatorVariableConstraints(const IndexType factor, const IndicatorVariableType &indicatorVariable, const SolverIndexType indicatorVariableLPVariable, const bool addToModel)
Add constraints for an indicator variable to the lp model.
Definition: lp_inference_base.hxx:2556
subsequence_iterator.hxx
Provides implementation for class SubsequenceIterator.
opengm::LPInferenceBase::AddAllViolatedLinearConstraintsFunctor
Functor used to access the method challenge() of the underlying linear constraint function of a graph...
Definition: lp_inference_base.hxx:177
opengm::LPInferenceBase::fillLinearConstraintLPVariablesSubsequenceIndices
void fillLinearConstraintLPVariablesSubsequenceIndices()
Fill the variable LPInferenceBase::linearConstraintLPVariablesSubsequenceIndices_ with the appropriat...
Definition: lp_inference_base.hxx:2085
opengm::LPInferenceBase::getLPVariableIndexFromIndicatorVariable
bool getLPVariableIndexFromIndicatorVariable(const HIGHER_ORDER_FACTORS_MAP_TYPE &higherOrderFactorVariablesLookupTable, const INDICATOR_VARIABLES_MAP_TYPE &indicatorVariablesLookupTable, const IndicatorVariableType &indicatorVariable, const IndexType linearConstraintFactorIndex, SolverIndexType &lpVariableIndex) const
Get the index of the lp variable associated with an indicator variable.
Definition: lp_inference_base.hxx:2414
opengm::LPInferenceBase::RelaxedSolutionSubsequenceIterator
SubsequenceIterator< SolverSolutionIteratorType, typename std::vector< size_t >::const_iterator > RelaxedSolutionSubsequenceIterator
Typedef of the iterator type used to iterate over a subset of the computed solution. This iterator type is used to challenge the linear constraint functions present in the model. Only used when the problem is solved as a LP.
Definition: lp_inference_base.hxx:61
opengm::LPInferenceBase::Parameter::Random
Random will add violated constraints in a random order.
Definition: lp_inference_base.hxx:68
opengm::LinearConstraintTraits::LinearConstraintOperator::ValueType
ValueType
This enum defines the operator type for the linear constraint.
Definition: linear_constraint.hxx:17
opengm::LPInferenceBase::nodeLPVariableIndex
SolverIndexType nodeLPVariableIndex(const IndexType nodeID, const LabelType label) const
Get the lp variable which corresponds to the variable label pair of the graphical model...
Definition: lp_inference_base.hxx:2376
opengm::LPFunctionTransfer::LinearConstraintsContainerType
std::vector< LinearConstraintType > LinearConstraintsContainerType
Defines the linear constraints container type which is used to store multiple linear constraints...
Definition: lp_functiontransfer.hxx:22
opengm::LPInferenceBase::Parameter
Parameter class for opengm::LPInferenceBase.
Definition: lp_inference_base.hxx:63
opengm::LPInferenceBase::numNodesLPVariables_
SolverIndexType numNodesLPVariables_
The number of lp variables for the nodes of the graphical model.
Definition: lp_inference_base.hxx:233
opengm::LPInferenceBase::addLocalPolytopeConstraints
void addLocalPolytopeConstraints()
Add all constraints to the lp model which are required by the local polytope relaxation.
Definition: lp_inference_base.hxx:2198
opengm::LPInferenceBase::graphicalModel
virtual const GraphicalModelType & graphicalModel() const
Get graphical model.
Definition: lp_inference_base.hxx:1763
opengm::AddViolatedLinearConstraintsRelaxedFunctor::linearConstraintID_
LP_INFERENCE_BASE_TYPE::IndexType linearConstraintID_
Index of the linear constraint factor.
Definition: lp_inference_base.hxx:338
opengm::LPInferenceTraits
Traits class for lp inference classes.
Definition: lp_inference_base.hxx:26
opengm::LPInferenceBase::AddAllViolatedLinearConstraintsFunctor::linearConstraintID_
IndexType linearConstraintID_
Index of the linear constraint factor.
Definition: lp_inference_base.hxx:183
opengm::AddViolatedLinearConstraintsFunctor::AddViolatedLinearConstraintsFunctor_impl
Helper struct to distinguish between linear constraint functions and other function types...
Definition: lp_inference_base.hxx:323
opengm::AddViolatedLinearConstraintsFunctor::sortedViolatedConstraintsList_
LP_INFERENCE_BASE_TYPE::SortedViolatedConstraintsListType * sortedViolatedConstraintsList_
Storage for the violated linear constraints sorted by their weights. Only used when LPInferenceBase::...
Definition: lp_inference_base.hxx:317
opengm::LPInferenceBase::infer_impl_selectRelaxation
InferenceTermination infer_impl_selectRelaxation(VISITOR_TYPE &visitor)
Helper function for LPInferenceBase::infer_impl to select the relaxation template parameter...
Definition: lp_inference_base.hxx:2766
opengm::AddViolatedLinearConstraintsRelaxedFunctor::tolerance_
LP_INFERENCE_BASE_TYPE::ValueType tolerance_
The tolerance used for the method challengeRelaxed() of the underlying linear constraint function of ...
Definition: lp_inference_base.hxx:334
opengm::LPInferenceBase::FactorIndexConstraintPointerPairType
std::pair< IndexType, const LinearConstraintType * > FactorIndexConstraintPointerPairType
Typedef of the pair type used to store a pointer to a linear constraint in combination with the linea...
Definition: lp_inference_base.hxx:108
opengm::LPInferenceBase::transferableFactors_
std::vector< IndexType > transferableFactors_
List of all transferable factors.
Definition: lp_inference_base.hxx:230
opengm::LPFunctionTransfer::GetIndicatorVariablesFunctor
Functor to call LPFunctionTransfer::getIndicatorVariables() for a factor of the graphical model...
Definition: lp_functiontransfer.hxx:62
opengm::LPInferenceBase::AddAllViolatedLinearConstraintsRelaxedFunctor::violatedConstraintAdded_
bool violatedConstraintAdded_
Indicator used to tell if at least one constraint was added to the LP/MIP model.
Definition: lp_inference_base.hxx:201
opengm::LPInferenceBase::linearConstraintsLPVariablesIndicesLookupTable_
std::vector< std::map< const IndicatorVariableType, SolverIndexType > > linearConstraintsLPVariablesIndicesLookupTable_
Lookup table for the lp variable indices of each linear constraint.
Definition: lp_inference_base.hxx:243
opengm::LinearConstraint
Define a linear constraint for a set of indicatorVariables.
Definition: linear_constraint.hxx:21
opengm::LPInferenceBase::ConstraintStorage::coefficients_
std::vector< SolverValueType > coefficients_
The coefficients for the variables of the LP/MIP model which are used in the constraint.
Definition: lp_inference_base.hxx:99
opengm::LPInferenceBase::inferenceStarted_
bool inferenceStarted_
Tell if inference was already started.
Definition: lp_inference_base.hxx:231
opengm::LPInferenceBase::factorsLPVariablesOffset_
std::vector< SolverIndexType > factorsLPVariablesOffset_
The offsets for the indices of the lp variables for each factor of the graphical model.
Definition: lp_inference_base.hxx:241
opengm::LPInferenceBase::VariableLabelPairsIteratorType
LinearConstraintType::VariableLabelPairsIteratorType VariableLabelPairsIteratorType
Typedef of the iterator type used to iterate over a set of varible label pairs used within an indicat...
Definition: lp_inference_base.hxx:49
opengm::RuntimeError
OpenGM runtime error.
Definition: opengm.hxx:100
marray::Marray::resize
void resize(ShapeIterator, ShapeIterator, const T &=T())
Resize (existing entries are preserved, new entries are initialized).
Definition: marray.hxx:3886
opengm::LPInferenceBase::GetLinearConstraintsBeginFunctor::linearConstraintsBegin_
LinearConstraintsIteratorType linearConstraintsBegin_
Storage for the iterator returned by the method linearConstraintsBegin().
Definition: lp_inference_base.hxx:147
opengm::LPInferenceBase::AddAllViolatedLinearConstraintsFunctor::labelingBegin_
IntegerSolutionSubsequenceIterator labelingBegin_
Iterator used to iterate over the current solution.
Definition: lp_inference_base.hxx:180
marray::View::size
const size_t size() const
Get the number of data items.
Definition: marray.hxx:1698
opengm::LPInferenceBase::AddAllViolatedLinearConstraintsFunctor::AddAllViolatedLinearConstraintsFunctor_impl
Helper struct to distinguish between linear constraint functions and other function types...
Definition: lp_inference_base.hxx:189
opengm::abs
T abs(const T &x)
Definition: opengm.hxx:111
opengm::LPInferenceBase::InactiveConstraintFactorConstraintPairType
std::pair< InactiveConstraintsListIteratorType, FactorIndexConstraintPointerPairType > InactiveConstraintFactorConstraintPairType
Typedef of the pair type used to store a pointer to an inactive constraint of the local polytope cons...
Definition: lp_inference_base.hxx:109
opengm::InferenceTermination
InferenceTermination
Definition: inference.hxx:24
opengm::LinearConstraint::getBound
BoundType getBound() const
Get the bound of the linear constraint.
Definition: linear_constraint.hxx:527
opengm::LPInferenceBase::linearConstraintLPVariablesSubsequenceIndices_
std::vector< std::vector< size_t > > linearConstraintLPVariablesSubsequenceIndices_
The indices of the subset of the solution variables which are relevant for each linear constraint...
Definition: lp_inference_base.hxx:245
Generated by   doxygen 1.8.12