Generated on Sat Feb 7 2015 02:01:19 for Gecode by doxygen 1.8.9.1
bin-packing.hh
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  * Contributing authors:
7  * Stefano Gualandi <stefano.gualandi@gmail.com>
8  *
9  * Copyright:
10  * Stefano Gualandi, 2013
11  * Christian Schulte, 2010
12  *
13  * Last modified:
14  * $Date: 2014-08-28 14:29:11 +0200 (Thu, 28 Aug 2014) $ by $Author: schulte $
15  * $Revision: 14203 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #ifndef __GECODE_INT_BIN_PACKING_HH__
43 #define __GECODE_INT_BIN_PACKING_HH__
44 
45 #include <gecode/int.hh>
46 
52 namespace Gecode { namespace Int { namespace BinPacking {
53 
57  class Item : public DerivedView<IntView> {
58  protected:
61  int s;
62  public:
64  Item(void);
66  Item(IntView b, int s);
67 
69  IntView bin(void) const;
71  void bin(IntView b);
73  int size(void) const;
75  void size(int s);
76 
78  void update(Space& home, bool share, Item& i);
79  };
80 
82  bool same(const Item& i, const Item& j);
84  bool before(const Item& i, const Item& j);
85 
87  bool operator <(const Item& i, const Item& j);
88 
89 
91  class SizeSet {
92  protected:
94  int n;
96  int t;
98  int* s;
99  public:
101  SizeSet(void);
103  SizeSet(Region& region, int n_max);
105  void add(int s);
107  int card(void) const;
109  int total(void) const;
111  int operator [](int i) const;
112  };
113 
115  class SizeSetMinusOne : public SizeSet {
116  protected:
118  int p;
119  public:
121  SizeSetMinusOne(void);
123  SizeSetMinusOne(Region& region, int n);
125  void minus(int s);
127  int card(void) const;
129  int total(void) const;
131  int operator [](int i) const;
132  };
133 
134 
145  class Pack : public Propagator {
146  protected:
152  int t;
156  Pack(Space& home, bool share, Pack& p);
157  public:
160  static ExecStatus post(Home home,
163  template<class SizeSet>
164  bool nosum(const SizeSet& s, int a, int b, int& ap, int& bp);
166  template<class SizeSet>
167  bool nosum(const SizeSet& s, int a, int b);
170  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
173  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
176  virtual Actor* copy(Space& home, bool share);
178  virtual size_t dispose(Space& home);
179  };
180 
181 
184  protected:
188  const IntVarArgs& b;
190  unsigned int bins;
192  int nodes(void) const;
193 
196  public:
198  NodeSet(void);
200  NodeSet(Region& r, int n);
202  NodeSet(Region& r, int n, const NodeSet& ns);
204  void allocate(Region& r, int n);
206  void init(Region& r, int n);
208  bool in(int i) const;
210  void incl(int i);
212  void excl(int i);
214  void copy(int n, const NodeSet& ns);
216  void empty(int n);
223  static bool iwn(NodeSet& iwa, const NodeSet& a,
224  NodeSet& iwb, const NodeSet& b,
225  const NodeSet& c, int n);
226  };
227 
229  class Node {
230  public:
234  unsigned int d;
236  unsigned int w;
238  Node(void);
239  };
242 
244  class Nodes {
245  private:
247  const NodeSet& ns;
249  unsigned int c;
250  public:
252  Nodes(const NodeSet& ns);
254 
255  void operator ++(void);
258 
260 
261  int operator ()(void) const;
264  };
265 
267 
268  class Clique {
270  public:
274  unsigned int c;
276  unsigned int w;
278  Clique(Region& r, int m);
280  void incl(int i, unsigned int w);
282  void excl(int i, unsigned int w);
283  };
284 
286  int pivot(const NodeSet& a, const NodeSet& b) const;
291 
293 
294  Clique cur;
299  ExecStatus clique(void);
301  ExecStatus clique(int i);
303  ExecStatus clique(int i, int j);
305  ExecStatus clique(int i, int j, int k);
307  public:
309  ConflictGraph(Space& home, Region& r, const IntVarArgs& b,
310  int m);
312  void edge(int i, int j, bool add=true);
314  bool adjacent(int i, int j) const;
316  ExecStatus post(void);
318  IntSet maxclique(void) const;
320  ~ConflictGraph(void);
321  };
322 
323 }}}
324 
327 
328 #endif
329 
330 // STATISTICS: int-prop
331 
int * s
Array of sizes (will have more elements)
Definition: bin-packing.hh:98
int card(void) const
Return cardinality of set (number of entries)
Definition: propagate.hpp:106
void empty(int n)
Clear the whole node set for n nodes.
int p
Position of discarded item.
Definition: bin-packing.hh:118
SizeSetMinusOne(void)
Default constructor.
Definition: propagate.hpp:119
bool nosum(const SizeSet &s, int a, int b, int &ap, int &bp)
Detect non-existence of sums in a .. b.
Definition: propagate.hpp:180
IntView bin(void) const
Return bin of item.
Definition: propagate.hpp:52
Item combining bin and size information.
Definition: bin-packing.hh:57
int nodes(void) const
Return number of nodes.
int size(void) const
Return size of item.
Definition: propagate.hpp:60
ViewArray< Item > bs
Items with bin and size.
Definition: bin-packing.hh:150
Node * node
The nodes in the graph.
Definition: bin-packing.hh:241
int t
Total size of all items.
Definition: bin-packing.hh:152
unsigned int c
Cardinality of clique.
Definition: bin-packing.hh:274
int operator[](int i) const
Return size of item i.
Definition: propagate.hpp:114
int card(void) const
Return cardinality of set (number of entries)
Definition: propagate.hpp:132
Basic bitset support (without stored size information)
Base-class for propagators.
Definition: core.hpp:755
int n
Number of size entries in the set.
Definition: bin-packing.hh:94
Pack(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Constructor for posting.
Definition: propagate.hpp:155
ViewArray< OffsetView > l
Views for load of bins.
Definition: bin-packing.hh:148
ConflictGraph(Space &home, Region &r, const IntVarArgs &b, int m)
Initialize graph.
Handle to region.
Definition: region.hpp:61
Computation spaces.
Definition: core.hpp:1362
void copy(int n, const NodeSet &ns)
Copy elements from node set ns with n nodes.
static ExecStatus post(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Post propagator for loads l and items bs.
Definition: propagate.cpp:358
Base-class for derived views.
Definition: view.hpp:208
ExecStatus clique(void)
Report the current clique.
Base-class for both propagators and branchers.
Definition: core.hpp:666
ExecStatus post(void)
Post additional constraints.
Graph containing conflict information.
Definition: bin-packing.hh:183
IntSet maxclique(void) const
Return maximal clique found.
void update(Space &home, bool share, Item &i)
Update item during cloning.
Definition: propagate.hpp:69
SizeSet(void)
Default constructor.
Definition: propagate.hpp:97
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:764
bool operator<(const Item &i, const Item &j)
For sorting according to size.
Definition: propagate.hpp:87
bool adjacent(int i, int j) const
Test whether nodes i and j are adjacent.
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: propagate.cpp:53
Nodes(const NodeSet &ns)
Initialize for nodes in ns.
int operator[](int i) const
Return size of item i.
Definition: propagate.hpp:142
Clique(Region &r, int m)
Constructor for m nodes.
void init(Region &r, int n)
Initialize node set for n nodes.
unsigned int w
Weight (initialized with degree before graph is reduced)
Definition: bin-packing.hh:236
void edge(int i, int j, bool add=true)
Add or remove an edge between nodes i and j (i must be less than j)
Integer sets.
Definition: int.hh:171
View arrays.
Definition: array.hpp:234
void add(int s)
Add new size s.
Definition: propagate.hpp:102
ExecStatus bk(NodeSet &p, NodeSet &x)
Run Bosch-Kerbron algorithm for finding max cliques.
void operator++(void)
Move iterator to next node (if possible)
bool in(int i) const
Test whether node i is included.
Passing integer variables.
Definition: int.hh:636
Item(void)
Default constructor.
Definition: propagate.hpp:45
bool before(const Item &i, const Item &j)
Test whether one item is before another.
Definition: propagate.hpp:80
Bin-packing propagator.
Definition: bin-packing.hh:145
Example: Bin packing
Integer view for integer variables.
Definition: view.hpp:129
virtual size_t dispose(Space &home)
Destructor.
Definition: propagate.hpp:171
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Propagation cost.
Definition: core.hpp:537
ExecStatus
Definition: core.hpp:523
bool same(const Item &i, const Item &j)
Whether two items are the same.
Definition: propagate.hpp:76
Clique max
Largest clique so far.
Definition: bin-packing.hh:297
Size sets with one element discarded.
Definition: bin-packing.hh:115
int t
Total size of the set.
Definition: bin-packing.hh:96
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: propagate.cpp:48
void allocate(Region &r, int n)
Allocate node set for n nodes.
const IntVarArgs & b
Bin variables.
Definition: bin-packing.hh:188
void minus(int s)
Discard size s.
Definition: propagate.hpp:124
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: propagate.cpp:111
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
int operator()(void) const
Return current node.
unsigned int bins
Number of bins.
Definition: bin-packing.hh:190
int pivot(const NodeSet &a, const NodeSet &b) const
Find a pivot node with maximal degree from a or b.
#define GECODE_INT_EXPORT
Definition: int.hh:78
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
int total(void) const
Return total size.
Definition: propagate.hpp:110
int total(void) const
Return total size.
Definition: propagate.hpp:137
void incl(int i, unsigned int w)
Include node i with weight w.
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
void excl(int i, unsigned int w)
Exclude node i with weight w.
static bool iwn(NodeSet &iwa, const NodeSet &a, NodeSet &iwb, const NodeSet &b, const NodeSet &c, int n)