Generated on Fri Aug 24 2012 04:52:10 for Gecode by doxygen 1.8.1.2
post.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2002
8  *
9  * Last modified:
10  * $Date: 2011-08-12 23:27:20 +1000 (Fri, 12 Aug 2011) $ by $Author: tack $
11  * $Revision: 12285 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <algorithm>
39 #include <climits>
40 
41 namespace Gecode { namespace Int { namespace Linear {
42 
43  template<class View>
44  inline void
45  estimate(Term<View>* t, int n, int c, int& l, int &u) {
46  double min = c;
47  double max = c;
48  for (int i=n; i--; ) {
49  double a = t[i].a;
50  if (a > 0) {
51  min += a*t[i].x.min();
52  max += a*t[i].x.max();
53  } else {
54  max += a*t[i].x.min();
55  min += a*t[i].x.max();
56  }
57  }
58  if (min < Limits::min)
59  min = Limits::min;
60  if (min > Limits::max)
61  min = Limits::max;
62  l = static_cast<int>(min);
63  if (max < Limits::min)
64  max = Limits::min;
65  if (max > Limits::max)
66  max = Limits::max;
67  u = static_cast<int>(max);
68  }
69 
71  template<class View>
72  class TermLess {
73  public:
74  forceinline bool
75  operator ()(const Term<View>& a, const Term<View>& b) {
76  return before(a.x,b.x);
77  }
78  };
79 
80  template<class View>
81  inline bool
82  normalize(Term<View>* t, int &n,
83  Term<View>* &t_p, int &n_p,
84  Term<View>* &t_n, int &n_n) {
85  /*
86  * Join coefficients for aliased variables:
87  *
88  */
89  {
90  // Group same variables
91  TermLess<View> tl;
92  Support::quicksort<Term<View>,TermLess<View> >(t,n,tl);
93 
94  // Join adjacent variables
95  int i = 0;
96  int j = 0;
97  while (i < n) {
98  Limits::check(t[i].a,"Int::linear");
99  double a = t[i].a;
100  View x = t[i].x;
101  while ((++i < n) && same(t[i].x,x)) {
102  a += t[i].a;
103  Limits::check(a,"Int::linear");
104  }
105  if (a != 0.0) {
106  t[j].a = static_cast<int>(a); t[j].x = x; j++;
107  }
108  }
109  n = j;
110  }
111 
112  /*
113  * Partition into positive/negative coefficents
114  *
115  */
116  if (n > 0) {
117  int i = 0;
118  int j = n-1;
119  while (true) {
120  while ((t[j].a < 0) && (--j >= 0)) ;
121  while ((t[i].a > 0) && (++i < n)) ;
122  if (j <= i) break;
123  std::swap(t[i],t[j]);
124  }
125  t_p = t; n_p = i;
126  t_n = t+n_p; n_n = n-n_p;
127  } else {
128  t_p = t; n_p = 0;
129  t_n = t; n_n = 0;
130  }
131 
132  /*
133  * Make all coefficients positive
134  *
135  */
136  for (int i=n_n; i--; )
137  t_n[i].a = -t_n[i].a;
138 
139  /*
140  * Test for unit coefficients only
141  *
142  */
143  for (int i=n; i--; )
144  if (t[i].a != 1)
145  return false;
146  return true;
147  }
148 
149 }}}
150 
151 // STATISTICS: int-post
152