this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Contributing authors:
7 * Stefano Gualandi <stefano.gualandi@gmail.com>
8 *
9 * Copyright:
10 * Stefano Gualandi, 2013
11 * Christian Schulte, 2010
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#ifndef GECODE_INT_BIN_PACKING_HH
39#define GECODE_INT_BIN_PACKING_HH
40
41#include <gecode/int.hh>
42
43/**
44 * \namespace Gecode::Int::BinPacking
45 * \brief %Bin-packing propagators
46 */
47
48namespace Gecode { namespace Int { namespace BinPacking {
49
50 /**
51 * \brief Item combining bin and size information
52 */
53 class Item : public DerivedView<IntView> {
54 protected:
55 using DerivedView<IntView>::x;
56 /// Size of item
57 int s;
58 public:
59 /// Default constructor
60 Item(void);
61 /// Constructor
62 Item(IntView b, int s);
63
64 /// Return bin of item
65 IntView bin(void) const;
66 /// Set bin of item to \a b
67 void bin(IntView b);
68 /// Return size of item
69 int size(void) const;
70 /// Set size of item to \a s
71 void size(int s);
72
73 /// Update item during cloning
74 void update(Space& home, Item& i);
75 };
76
77 /// Whether two items are the same
78 bool operator ==(const Item& i, const Item& j);
79 /// Whether two items are not the same
80 bool operator !=(const Item& i, const Item& j);
81
82 /// Order, also for sorting according to size
83 bool operator <(const Item& i, const Item& j);
84
85
86 /// Size sets
87 class SizeSet {
88 protected:
89 /// Number of size entries in the set
90 int n;
91 /// Total size of the set
92 int t;
93 /// Array of sizes (will have more elements)
94 int* s;
95 public:
96 /// Default constructor
97 SizeSet(void);
98 /// Initialize for at most \a n_max items
99 SizeSet(Region& region, int n_max);
100 /// Add new size \a s
101 void add(int s);
102 /// Return cardinality of set (number of entries)
103 int card(void) const;
104 /// Return total size
105 int total(void) const;
106 /// Return size of item \a i
107 int operator [](int i) const;
108 };
109
110 /// Size sets with one element discarded
111 class SizeSetMinusOne : public SizeSet {
112 protected:
113 /// Position of discarded item
114 int p;
115 public:
116 /// Default constructor
117 SizeSetMinusOne(void);
118 /// Initialize for at most \n n_max entries
119 SizeSetMinusOne(Region& region, int n);
120 /// Discard size \a s
121 void minus(int s);
122 /// Return cardinality of set (number of entries)
123 int card(void) const;
124 /// Return total size
125 int total(void) const;
126 /// Return size of item \a i
127 int operator [](int i) const;
128 };
129
130
131 /**
132 * \brief Bin-packing propagator
133 *
134 * The algorithm is taken from:
135 * Paul Shaw. A Constraint for Bin Packing. CP 2004.
136 *
137 * Requires \code #include <gecode/int/bin-packing.hh> \endcode
138 *
139 * \ingroup FuncIntProp
140 */
141 class Pack : public Propagator {
142 protected:
143 /// Views for load of bins
144 ViewArray<OffsetView> l;
145 /// Items with bin and size
146 ViewArray<Item> bs;
147 /// Total size of all items
148 int t;
149 /// Constructor for posting
150 Pack(Home home, ViewArray<OffsetView>& l, ViewArray<Item>& bs);
151 /// Constructor for cloning \a p
152 Pack(Space& home, Pack& p);
153 public:
154 /// Post propagator for loads \a l and items \a bs
155 GECODE_INT_EXPORT
156 static ExecStatus post(Home home,
157 ViewArray<OffsetView>& l, ViewArray<Item>& bs);
158 /// Detect non-existence of sums in \a a .. \a b
159 template<class SizeSet>
160 bool nosum(const SizeSet& s, int a, int b, int& ap, int& bp);
161 /// Detect non-existence of sums in \a a .. \a b
162 template<class SizeSet>
163 bool nosum(const SizeSet& s, int a, int b);
164 /// Perform propagation
165 GECODE_INT_EXPORT
166 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
167 /// Cost function
168 GECODE_INT_EXPORT
169 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
170 /// Schedule function
171 GECODE_INT_EXPORT
172 virtual void reschedule(Space& home);
173 /// Copy propagator during cloning
174 GECODE_INT_EXPORT
175 virtual Actor* copy(Space& home);
176 /// Destructor
177 virtual size_t dispose(Space& home);
178 };
179
180
181 /// Graph containing conflict information
182 class ConflictGraph {
183 protected:
184 /// Home space
185 Home& home;
186 /// Bin variables
187 const IntVarArgs& b;
188 /// Number of bins
189 unsigned int bins;
190 /// Return number of nodes
191 int nodes(void) const;
192
193 /// Sets of graph nodes
194 class NodeSet : public Support::RawBitSetBase {
195 public:
196 /// Keep uninitialized
197 NodeSet(void);
198 /// Initialize node set for \a n nodes
199 NodeSet(Region& r, int n);
200 /// Initialize node set as copy of \a ns with \a n nodes
201 NodeSet(Region& r, int n, const NodeSet& ns);
202 /// Allocate node set for \a n nodes
203 void allocate(Region& r, int n);
204 /// Initialize node set for \a n nodes
205 void init(Region& r, int n);
206 /// Test whether node \a i is included
207 bool in(int i) const;
208 /// Include node \a i
209 void incl(int i);
210 /// Exclude node \a i
211 void excl(int i);
212 /// Copy elements from node set \a ns with \a n nodes
213 void copy(int n, const NodeSet& ns);
214 /// Clear the whole node set for \a n nodes
215 void empty(int n);
216 /**
217 * Initialize \a ac as intersection of \a a and \a c,
218 * \a bc as intersection of \a b and \a c where \a n
219 * is the maximal number of nodes. Return whether both \ac
220 * and \a bc are empty.
221 */
222 static bool iwn(NodeSet& iwa, const NodeSet& a,
223 NodeSet& iwb, const NodeSet& b,
224 const NodeSet& c, int n);
225 };
226
227 /// Class for node in graph
228 class Node {
229 public:
230 /// The neighbors
231 NodeSet n;
232 /// Degree
233 unsigned int d;
234 /// Weight (initialized with degree before graph is reduced)
235 unsigned int w;
236 /// Default constructor
237 Node(void);
238 };
239 /// The nodes in the graph
240 Node* node;
241
242 /// Iterator over node sets
243 class Nodes {
244 private:
245 /// The node set to iterate over
246 const NodeSet& ns;
247 /// Current node
248 unsigned int c;
249 public:
250 /// Initialize for nodes in \a ns
251 Nodes(const NodeSet& ns);
252 /// \name Iteration control
253 //@{
254 /// Move iterator to next node (if possible)
255 void operator ++(void);
256 //@}
257
258 /// \name %Node access
259 //@{
260 /// Return current node
261 int operator ()(void) const;
262 //@}
263 };
264
265 /// \name Routines for Bosch-Kerbron algorithm
266 //@{
267 /// Clique information
268 class Clique {
269 public:
270 /// Nodes in the clique
271 NodeSet n;
272 /// Cardinality of clique
273 unsigned int c;
274 /// Weight of clique
275 unsigned int w;
276 /// Constructor for \a m nodes
277 Clique(Region& r, int m);
278 /// Include node \a i with weight \a w
279 void incl(int i, unsigned int w);
280 /// Exclude node \a i with weight \a w
281 void excl(int i, unsigned int w);
282 };
283
284 /// Find a pivot node with maximal degree from \a a or \a b
285 int pivot(const NodeSet& a, const NodeSet& b) const;
286 /// Run Bosch-Kerbron algorithm for finding max cliques
287 GECODE_INT_EXPORT
288 ExecStatus bk(NodeSet& p, NodeSet& x);
289 //@}
290
291 /// \name Managing cliques
292 //@{
293 /// Current clique
294 Clique cur;
295 /// Largest clique so far
296 Clique max;
297 /// Report the current clique
298 ExecStatus clique(void);
299 /// Found a clique of node \a i
300 ExecStatus clique(int i);
301 /// Found a clique of nodes \a i and \a j
302 ExecStatus clique(int i, int j);
303 /// Found a clique of nodes \a i, \a j, and \a k
304 ExecStatus clique(int i, int j, int k);
305 //@}
306 public:
307 /// Initialize graph
308 ConflictGraph(Home& home, Region& r, const IntVarArgs& b,
309 int m);
310 /// Add or remove an edge between nodes \a i and \a j (\a i must be less than \a j)
311 void edge(int i, int j, bool add=true);
312 /// Test whether nodes \a i and \a j are adjacent
313 bool adjacent(int i, int j) const;
314 /// Post additional constraints
315 ExecStatus post(void);
316 /// Return maximal clique found
317 IntSet maxclique(void) const;
318 /// Destructor
319 ~ConflictGraph(void);
320 };
321
322}}}
323
324#include <gecode/int/bin-packing/propagate.hpp>
325#include <gecode/int/bin-packing/conflict-graph.hpp>
326
327#endif
328
329// STATISTICS: int-prop
330