Generated on Thu Jan 31 2019 20:56:34 for Gecode by doxygen 1.8.15
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: 2016-09-02 11:28:30 +0200 (Fri, 02 Sep 2016) $ by $Author: schulte $
15  * $Revision: 15160 $
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 void reschedule(Space& home);
179  virtual Actor* copy(Space& home, bool share);
181  virtual size_t dispose(Space& home);
182  };
183 
184 
187  protected:
191  const IntVarArgs& b;
193  unsigned int bins;
195  int nodes(void) const;
196 
199  public:
201  NodeSet(void);
203  NodeSet(Region& r, int n);
205  NodeSet(Region& r, int n, const NodeSet& ns);
207  void allocate(Region& r, int n);
209  void init(Region& r, int n);
211  bool in(int i) const;
213  void incl(int i);
215  void excl(int i);
217  void copy(int n, const NodeSet& ns);
219  void empty(int n);
226  static bool iwn(NodeSet& iwa, const NodeSet& a,
227  NodeSet& iwb, const NodeSet& b,
228  const NodeSet& c, int n);
229  };
230 
232  class Node {
233  public:
237  unsigned int d;
239  unsigned int w;
241  Node(void);
242  };
245 
247  class Nodes {
248  private:
250  const NodeSet& ns;
252  unsigned int c;
253  public:
255  Nodes(const NodeSet& ns);
257 
258  void operator ++(void);
261 
263 
264  int operator ()(void) const;
267  };
268 
270 
271  class Clique {
273  public:
277  unsigned int c;
279  unsigned int w;
281  Clique(Region& r, int m);
283  void incl(int i, unsigned int w);
285  void excl(int i, unsigned int w);
286  };
287 
289  int pivot(const NodeSet& a, const NodeSet& b) const;
294 
296 
297  Clique cur;
302  ExecStatus clique(void);
304  ExecStatus clique(int i);
306  ExecStatus clique(int i, int j);
308  ExecStatus clique(int i, int j, int k);
310  public:
313  int m);
315  void edge(int i, int j, bool add=true);
317  bool adjacent(int i, int j) const;
319  ExecStatus post(void);
321  IntSet maxclique(void) const;
323  ~ConflictGraph(void);
324  };
325 
326 }}}
327 
330 
331 #endif
332 
333 // STATISTICS: int-prop
334 
int * s
Array of sizes (will have more elements)
Definition: bin-packing.hh:98
int operator [](int i) const
Return size of item i.
Definition: propagate.hpp:114
bool adjacent(int i, int j) const
Test whether nodes i and j are adjacent.
void empty(int n)
Clear the whole node set for n nodes.
bool in(int i) const
Test whether node i is included.
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
Item combining bin and size information.
Definition: bin-packing.hh:57
ViewArray< Item > bs
Items with bin and size.
Definition: bin-packing.hh:150
Node * node
The nodes in the graph.
Definition: bin-packing.hh:244
int t
Total size of all items.
Definition: bin-packing.hh:152
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: propagate.cpp:48
int operator [](int i) const
Return size of item i.
Definition: propagate.hpp:142
int card(void) const
Return cardinality of set (number of entries)
Definition: propagate.hpp:132
unsigned int c
Cardinality of clique.
Definition: bin-packing.hh:277
Basic bitset support (without stored size information)
Base-class for propagators.
Definition: core.hpp:1092
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(Home &home, Region &r, const IntVarArgs &b, int m)
Initialize graph.
int pivot(const NodeSet &a, const NodeSet &b) const
Find a pivot node with maximal degree from a or b.
int size(void) const
Return size of item.
Definition: propagate.hpp:60
Handle to region.
Definition: region.hpp:61
Computation spaces.
Definition: core.hpp:1748
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:364
Base-class for derived views.
Definition: view.hpp:222
ExecStatus clique(void)
Report the current clique.
Base-class for both propagators and branchers.
Definition: core.hpp:696
ExecStatus post(void)
Post additional constraints.
Graph containing conflict information.
Definition: bin-packing.hh:186
void update(Space &home, bool share, Item &i)
Update item during cloning.
Definition: propagate.hpp:69
SizeSet(void)
Default constructor.
Definition: propagate.hpp:97
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
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
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1103
int total(void) const
Return total size.
Definition: propagate.hpp:137
bool operator<(const Item &i, const Item &j)
For sorting according to size.
Definition: propagate.hpp:87
int card(void) const
Return cardinality of set (number of entries)
Definition: propagate.hpp:106
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: propagate.cpp:59
Nodes(const NodeSet &ns)
Initialize for nodes in ns.
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:239
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:174
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)
Passing integer variables.
Definition: int.hh:639
Item(void)
Default constructor.
Definition: propagate.hpp:45
int operator()(void) const
Return current node.
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
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
IntSet maxclique(void) const
Return maximal clique found.
Integer view for integer variables.
Definition: view.hpp:129
virtual size_t dispose(Space &home)
Destructor.
Definition: propagate.hpp:171
Propagation cost.
Definition: core.hpp:554
ExecStatus
Definition: core.hpp:540
IntView bin(void) const
Return bin of item.
Definition: propagate.hpp:52
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:300
Size sets with one element discarded.
Definition: bin-packing.hh:115
int t
Total size of the set.
Definition: bin-packing.hh:96
int nodes(void) const
Return number of nodes.
Post propagator for SetVar x
Definition: set.hh:784
void allocate(Region &r, int n)
Allocate node set for n nodes.
const IntVarArgs & b
Bin variables.
Definition: bin-packing.hh:191
void minus(int s)
Discard size s.
Definition: propagate.hpp:124
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: propagate.cpp:117
Gecode toplevel namespace
unsigned int bins
Number of bins.
Definition: bin-packing.hh:193
int total(void) const
Return total size.
Definition: propagate.hpp:110
#define GECODE_INT_EXPORT
Definition: int.hh:81
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
virtual void reschedule(Space &home)
Schedule function.
Definition: propagate.cpp:53
void incl(int i, unsigned int w)
Include node i with weight w.
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)