cumulatives.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Mikael Lagerkvist <lagerkvist@gecode.org> 00005 * 00006 * Copyright: 00007 * Mikael Lagerkvist, 2005 00008 * 00009 * Last modified: 00010 * $Date: 2010-03-03 17:40:32 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $ 00011 * $Revision: 10365 $ 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 <gecode/scheduling/cumulatives.hh> 00039 #include <gecode/int/linear.hh> 00040 00041 namespace Gecode { 00042 00043 using namespace Int; 00044 00045 namespace { 00046 ViewArray<IntView> 00047 make_view_array(Space& home, const IntVarArgs& in) { 00048 return ViewArray<Int::IntView>(home, in); 00049 } 00050 00051 ViewArray<ConstIntView> 00052 make_view_array(Space& home, const IntArgs& in) { 00053 ViewArray<Int::ConstIntView> res(home, in.size()); 00054 for (int i = in.size(); i--; ) { 00055 Int::Limits::check(in[i],"Scheduling::cumulatives"); 00056 res[i] = Int::ConstIntView(in[i]); 00057 } 00058 00059 return res; 00060 } 00061 00062 template<class In> class ViewType; 00063 00064 template<> 00065 class ViewType<IntArgs> { 00066 public: 00067 typedef Int::ConstIntView Result; 00068 }; 00069 00070 template<> 00071 class ViewType<IntVarArgs> { 00072 public: 00073 typedef Int::IntView Result; 00074 }; 00075 00076 void 00077 sum(Home home, IntVar s, IntVar d, IntVar e) { 00078 Int::Linear::Term<Int::IntView> t[3]; 00079 t[0].a= 1; t[0].x=s; 00080 t[1].a= 1; t[1].x=d; 00081 t[2].a=-1; t[2].x=e; 00082 Int::Linear::post(home, t, 3, IRT_EQ, 0); 00083 } 00084 00085 void 00086 sum(Home home, IntVar s, int d, IntVar e) { 00087 Int::Linear::Term<Int::IntView> t[2]; 00088 t[0].a= 1; t[0].x=s; 00089 t[1].a=-1; t[1].x=e; 00090 Int::Linear::post(home, t, 2, IRT_EQ, -d); 00091 } 00092 00093 template<class Machine, class Duration, class Height> 00094 void 00095 post_cumulatives(Home home, const Machine& machine, 00096 const IntVarArgs& start, const Duration& duration, 00097 const IntVarArgs& end, const Height& height, 00098 const IntArgs& limit, bool at_most, 00099 IntConLevel) { 00100 if (machine.size() != start.size() || 00101 start.size() != duration.size() || 00102 duration.size() != end.size() || 00103 end.size() != height.size()) 00104 throw Int::ArgumentSizeMismatch("Scheduling::cumulatives"); 00105 if (home.failed()) return; 00106 00107 ViewArray<typename ViewType<Machine>::Result> 00108 vmachine = make_view_array(home, machine); 00109 ViewArray<typename ViewType<Duration>::Result> 00110 vduration = make_view_array(home, duration); 00111 ViewArray<typename ViewType<Height>::Result> 00112 vheight = make_view_array(home, height); 00113 ViewArray<IntView> 00114 vstart = make_view_array(home, start), 00115 vend = make_view_array(home, end); 00116 00117 SharedArray<int> limit_s(limit.size()); 00118 for (int i=limit.size(); i--;) 00119 limit_s[i] = limit[i]; 00120 00121 // There is only the value-consistent propagator for this constraint 00122 GECODE_ES_FAIL((Scheduling::Cumulatives::Val< 00123 typename ViewType<Machine>::Result, 00124 typename ViewType<Duration>::Result, 00125 typename ViewType<Height>::Result, 00126 IntView>::post(home, vmachine,vstart, vduration, 00127 vend, vheight,limit_s, at_most))); 00128 00129 // By definition, s+d=e should hold. 00130 // We enforce this using basic linear constraints, since the 00131 // sweep-algorithm does not check for it. 00132 for (int i = start.size(); i--; ) 00133 sum(home, start[i], duration[i], end[i]); 00134 } 00135 } 00136 00137 00138 void 00139 cumulatives(Home home, const IntVarArgs& machine, 00140 const IntVarArgs& start, const IntVarArgs& duration, 00141 const IntVarArgs& end, const IntVarArgs& height, 00142 const IntArgs& limit, bool at_most, 00143 IntConLevel cl) { 00144 post_cumulatives(home, machine, start, duration, end, 00145 height, limit, at_most, cl); 00146 } 00147 00148 void 00149 cumulatives(Home home, const IntArgs& machine, 00150 const IntVarArgs& start, const IntVarArgs& duration, 00151 const IntVarArgs& end, const IntVarArgs& height, 00152 const IntArgs& limit, bool at_most, 00153 IntConLevel cl) { 00154 post_cumulatives(home, machine, start, duration, end, 00155 height, limit, at_most, cl); 00156 } 00157 00158 void 00159 cumulatives(Home home, const IntVarArgs& machine, 00160 const IntVarArgs& start, const IntArgs& duration, 00161 const IntVarArgs& end, const IntVarArgs& height, 00162 const IntArgs& limit, bool at_most, 00163 IntConLevel cl) { 00164 post_cumulatives(home, machine, start, duration, end, 00165 height, limit, at_most, cl); 00166 } 00167 00168 void 00169 cumulatives(Home home, const IntArgs& machine, 00170 const IntVarArgs& start, const IntArgs& duration, 00171 const IntVarArgs& end, const IntVarArgs& height, 00172 const IntArgs& limit, bool at_most, 00173 IntConLevel cl) { 00174 post_cumulatives(home, machine, start, duration, end, 00175 height, limit, at_most, cl); 00176 } 00177 00178 void 00179 cumulatives(Home home, const IntVarArgs& machine, 00180 const IntVarArgs& start, const IntVarArgs& duration, 00181 const IntVarArgs& end, const IntArgs& height, 00182 const IntArgs& limit, bool at_most, 00183 IntConLevel cl) { 00184 post_cumulatives(home, machine, start, duration, end, 00185 height, limit, at_most, cl); 00186 } 00187 00188 void 00189 cumulatives(Home home, const IntArgs& machine, 00190 const IntVarArgs& start, const IntVarArgs& duration, 00191 const IntVarArgs& end, const IntArgs& height, 00192 const IntArgs& limit, bool at_most, 00193 IntConLevel cl) { 00194 post_cumulatives(home, machine, start, duration, end, 00195 height, limit, at_most, cl); 00196 } 00197 00198 void 00199 cumulatives(Home home, const IntVarArgs& machine, 00200 const IntVarArgs& start, const IntArgs& duration, 00201 const IntVarArgs& end, const IntArgs& height, 00202 const IntArgs& limit, bool at_most, 00203 IntConLevel cl) { 00204 post_cumulatives(home, machine, start, duration, end, 00205 height, limit, at_most, cl); 00206 } 00207 00208 void 00209 cumulatives(Home home, const IntArgs& machine, 00210 const IntVarArgs& start, const IntArgs& duration, 00211 const IntVarArgs& end, const IntArgs& height, 00212 const IntArgs& limit, bool at_most, 00213 IntConLevel cl) { 00214 post_cumulatives(home, machine, start, duration, end, 00215 height, limit, at_most, cl); 00216 } 00217 00218 } 00219 00220 // STATISTICS: scheduling-post