Generated on Thu Jul 21 2022 00:00:00 for Gecode by doxygen 1.9.4
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 * 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
48namespace Gecode { namespace Int { namespace BinPacking {
49
53 class Item : public DerivedView<IntView> {
54 protected:
57 int s;
58 public:
60 Item(void);
62 Item(IntView b, int s);
63
65 IntView bin(void) const;
67 void bin(IntView b);
69 int size(void) const;
71 void size(int s);
72
74 void update(Space& home, Item& i);
75 };
76
78 bool operator ==(const Item& i, const Item& j);
80 bool operator !=(const Item& i, const Item& j);
81
83 bool operator <(const Item& i, const Item& j);
84
85
87 class SizeSet {
88 protected:
90 int n;
92 int t;
94 int* s;
95 public:
97 SizeSet(void);
99 SizeSet(Region& region, int n_max);
101 void add(int s);
103 int card(void) const;
105 int total(void) const;
107 int operator [](int i) const;
108 };
109
111 class SizeSetMinusOne : public SizeSet {
112 protected:
114 int p;
115 public:
117 SizeSetMinusOne(void);
119 SizeSetMinusOne(Region& region, int n);
121 void minus(int s);
123 int card(void) const;
125 int total(void) const;
127 int operator [](int i) const;
128 };
129
130
141 class Pack : public Propagator {
142 protected:
148 int t;
152 Pack(Space& home, Pack& p);
153 public:
156 static ExecStatus post(Home home,
159 template<class SizeSet>
160 bool nosum(const SizeSet& s, int a, int b, int& ap, int& bp);
162 template<class SizeSet>
163 bool nosum(const SizeSet& s, int a, int b);
166 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
169 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
172 virtual void reschedule(Space& home);
175 virtual Actor* copy(Space& home);
177 virtual size_t dispose(Space& home);
178 };
179
180
183 protected:
187 const IntVarArgs& b;
189 unsigned int bins;
191 int nodes(void) const;
192
195 public:
197 NodeSet(void);
199 NodeSet(Region& r, int n);
201 NodeSet(Region& r, int n, const NodeSet& ns);
203 void allocate(Region& r, int n);
205 void init(Region& r, int n);
207 bool in(int i) const;
209 void incl(int i);
211 void excl(int i);
213 void copy(int n, const NodeSet& ns);
215 void empty(int n);
222 static bool iwn(NodeSet& iwa, const NodeSet& a,
223 NodeSet& iwb, const NodeSet& b,
224 const NodeSet& c, int n);
225 };
226
228 class Node {
229 public:
233 unsigned int d;
235 unsigned int w;
237 Node(void);
238 };
241
243 class Nodes {
244 private:
246 const NodeSet& ns;
248 unsigned int c;
249 public:
251 Nodes(const NodeSet& ns);
253
254
255 void operator ++(void);
257
259
260
261 int operator ()(void) const;
263 };
264
266
267
268 class Clique {
269 public:
273 unsigned int c;
275 unsigned int w;
277 Clique(Region& r, int m);
279 void incl(int i, unsigned int w);
281 void excl(int i, unsigned int w);
282 };
283
285 int pivot(const NodeSet& a, const NodeSet& b) const;
290
292
293
298 ExecStatus clique(void);
300 ExecStatus clique(int i);
302 ExecStatus clique(int i, int j);
304 ExecStatus clique(int i, int j, int k);
306 public:
309 int m);
311 void edge(int i, int j, bool add=true);
313 bool adjacent(int i, int j) const;
315 ExecStatus post(void);
317 IntSet maxclique(void) const;
319 ~ConflictGraph(void);
320 };
321
322}}}
323
326
327#endif
328
329// STATISTICS: int-prop
330
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Example: Bin packing
Base-class for both propagators and branchers.
Definition: core.hpp:628
Base-class for derived views.
Definition: view.hpp:230
IntView x
View from which this view is derived.
Definition: view.hpp:238
Home class for posting propagators
Definition: core.hpp:856
Integer sets.
Definition: int.hh:174
Passing integer variables.
Definition: int.hh:656
Clique(Region &r, int m)
Constructor for m nodes.
void excl(int i, unsigned int w)
Exclude node i with weight w.
void incl(int i, unsigned int w)
Include node i with weight w.
unsigned int c
Cardinality of clique.
Definition: bin-packing.hh:273
void empty(int n)
Clear the whole node set for n nodes.
static bool iwn(NodeSet &iwa, const NodeSet &a, NodeSet &iwb, const NodeSet &b, const NodeSet &c, int n)
void init(Region &r, int n)
Initialize node set for n nodes.
bool in(int i) const
Test whether node i is included.
void allocate(Region &r, int n)
Allocate node set for n nodes.
void copy(int n, const NodeSet &ns)
Copy elements from node set ns with n nodes.
unsigned int w
Weight (initialized with degree before graph is reduced)
Definition: bin-packing.hh:235
void operator++(void)
Move iterator to next node (if possible)
Nodes(const NodeSet &ns)
Initialize for nodes in ns.
int operator()(void) const
Return current node.
Graph containing conflict information.
Definition: bin-packing.hh:182
ExecStatus clique(void)
Report the current clique.
int nodes(void) const
Return number of nodes.
ExecStatus post(void)
Post additional constraints.
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.
bool adjacent(int i, int j) const
Test whether nodes i and j are adjacent.
Node * node
The nodes in the graph.
Definition: bin-packing.hh:240
ExecStatus bk(NodeSet &p, NodeSet &x)
Run Bosch-Kerbron algorithm for finding max cliques.
unsigned int bins
Number of bins.
Definition: bin-packing.hh:189
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)
const IntVarArgs & b
Bin variables.
Definition: bin-packing.hh:187
Clique max
Largest clique so far.
Definition: bin-packing.hh:296
IntSet maxclique(void) const
Return maximal clique found.
Item combining bin and size information.
Definition: bin-packing.hh:53
IntView bin(void) const
Return bin of item.
Definition: propagate.hpp:48
void update(Space &home, Item &i)
Update item during cloning.
Definition: propagate.hpp:65
Item(void)
Default constructor.
Definition: propagate.hpp:41
int size(void) const
Return size of item.
Definition: propagate.hpp:56
Bin-packing propagator.
Definition: bin-packing.hh:141
ViewArray< OffsetView > l
Views for load of bins.
Definition: bin-packing.hh:144
static ExecStatus post(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Post propagator for loads l and items bs.
Definition: propagate.cpp:360
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: propagate.cpp:113
ViewArray< Item > bs
Items with bin and size.
Definition: bin-packing.hh:146
Pack(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Constructor for posting.
Definition: propagate.hpp:150
int t
Total size of all items.
Definition: bin-packing.hh:148
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: propagate.cpp:55
bool nosum(const SizeSet &s, int a, int b, int &ap, int &bp)
Detect non-existence of sums in a .. b.
Definition: propagate.hpp:175
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: propagate.cpp:44
virtual void reschedule(Space &home)
Schedule function.
Definition: propagate.cpp:49
virtual size_t dispose(Space &home)
Destructor.
Definition: propagate.hpp:166
Size sets with one element discarded.
Definition: bin-packing.hh:111
int operator[](int i) const
Return size of item i.
Definition: propagate.hpp:137
void minus(int s)
Discard size s.
Definition: propagate.hpp:119
SizeSetMinusOne(void)
Default constructor.
Definition: propagate.hpp:114
int p
Position of discarded item.
Definition: bin-packing.hh:114
int total(void) const
Return total size.
Definition: propagate.hpp:132
int card(void) const
Return cardinality of set (number of entries)
Definition: propagate.hpp:127
int t
Total size of the set.
Definition: bin-packing.hh:92
SizeSet(void)
Default constructor.
Definition: propagate.hpp:92
void add(int s)
Add new size s.
Definition: propagate.hpp:97
int total(void) const
Return total size.
Definition: propagate.hpp:105
int operator[](int i) const
Return size of item i.
Definition: propagate.hpp:109
int n
Number of size entries in the set.
Definition: bin-packing.hh:90
int * s
Array of sizes (will have more elements)
Definition: bin-packing.hh:94
int card(void) const
Return cardinality of set (number of entries)
Definition: propagate.hpp:101
Integer view for integer variables.
Definition: view.hpp:129
Propagation cost.
Definition: core.hpp:486
Base-class for propagators.
Definition: core.hpp:1064
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1075
Handle to region.
Definition: region.hpp:55
Computation spaces.
Definition: core.hpp:1742
Basic bitset support (without stored size information)
View arrays.
Definition: array.hpp:253
#define GECODE_INT_EXPORT
Definition: int.hh:81
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
bool operator<(const Item &i, const Item &j)
Order, also for sorting according to size.
Definition: propagate.hpp:82
bool operator!=(const Item &i, const Item &j)
Whether two items are not the same.
Definition: propagate.hpp:76
bool operator==(const Item &i, const Item &j)
Whether two items are the same.
Definition: propagate.hpp:72
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
ExecStatus
Definition: core.hpp:472
Post propagator for SetVar x
Definition: set.hh:767
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})