post.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2002 00008 * 00009 * Last modified: 00010 * $Date: 2010-07-13 22:35:02 +0200 (Tue, 13 Jul 2010) $ by $Author: tack $ 00011 * $Revision: 11183 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 #include <algorithm> 00039 #include <climits> 00040 00041 namespace Gecode { namespace Int { namespace Linear { 00042 00043 template<class View> 00044 inline void 00045 estimate(Term<View>* t, int n, int c, int& l, int &u) { 00046 double min = c; 00047 double max = c; 00048 for (int i=n; i--; ) 00049 if (t[i].a > 0) { 00050 min += t[i].a*t[i].x.min(); 00051 max += t[i].a*t[i].x.max(); 00052 } else { 00053 max += t[i].a*t[i].x.min(); 00054 min += t[i].a*t[i].x.max(); 00055 } 00056 if (min < Limits::min) 00057 min = Limits::min; 00058 if (min > Limits::max) 00059 min = Limits::max; 00060 l = static_cast<int>(min); 00061 if (max < Limits::min) 00062 max = Limits::min; 00063 if (max > Limits::max) 00064 max = Limits::max; 00065 u = static_cast<int>(max); 00066 } 00067 00069 template<class View> 00070 class TermLess { 00071 public: 00072 forceinline bool 00073 operator ()(const Term<View>& a, const Term<View>& b) { 00074 return before(a.x,b.x); 00075 } 00076 }; 00077 00078 template<class View> 00079 inline bool 00080 normalize(Term<View>* t, int &n, 00081 Term<View>* &t_p, int &n_p, 00082 Term<View>* &t_n, int &n_n) { 00083 /* 00084 * Join coefficients for aliased variables: 00085 * 00086 */ 00087 { 00088 // Group same variables 00089 TermLess<View> tl; 00090 Support::quicksort<Term<View>,TermLess<View> >(t,n,tl); 00091 00092 // Join adjacent variables 00093 int i = 0; 00094 int j = 0; 00095 while (i < n) { 00096 Limits::check(t[i].a,"Int::linear"); 00097 double a = t[i].a; 00098 View x = t[i].x; 00099 while ((++i < n) && same(t[i].x,x)) { 00100 a += t[i].a; 00101 Limits::check(a,"Int::linear"); 00102 } 00103 if (a != 0.0) { 00104 t[j].a = static_cast<int>(a); t[j].x = x; j++; 00105 } 00106 } 00107 n = j; 00108 } 00109 00110 /* 00111 * Partition into positive/negative coefficents 00112 * 00113 */ 00114 if (n > 0) { 00115 int i = 0; 00116 int j = n-1; 00117 while (true) { 00118 while ((t[j].a < 0) && (--j >= 0)) ; 00119 while ((t[i].a > 0) && (++i < n)) ; 00120 if (j <= i) break; 00121 std::swap(t[i],t[j]); 00122 } 00123 t_p = t; n_p = i; 00124 t_n = t+n_p; n_n = n-n_p; 00125 } else { 00126 t_p = t; n_p = 0; 00127 t_n = t; n_n = 0; 00128 } 00129 00130 /* 00131 * Make all coefficients positive 00132 * 00133 */ 00134 for (int i=n_n; i--; ) 00135 t_n[i].a = -t_n[i].a; 00136 00137 /* 00138 * Test for unit coefficients only 00139 * 00140 */ 00141 for (int i=n; i--; ) 00142 if (t[i].a != 1) 00143 return false; 00144 return true; 00145 } 00146 00147 }}} 00148 00149 // STATISTICS: int-post 00150