Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
47
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 };
239
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
Home class for posting propagators
Definition core.hpp:856
Integer sets.
Definition int.hh:174
Passing integer variables.
Definition int.hh:662
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.
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)
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.
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.
ExecStatus bk(NodeSet &p, NodeSet &x)
Run Bosch-Kerbron algorithm for finding max cliques.
unsigned int bins
Number of bins.
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.
Clique max
Largest clique so far.
IntSet maxclique(void) const
Return maximal clique found.
Item combining bin and size information.
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
ViewArray< OffsetView > l
Views for load of bins.
static ExecStatus post(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Post propagator for loads l and items bs.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
ViewArray< Item > bs
Items with bin and size.
Pack(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Constructor for posting.
int t
Total size of all items.
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.
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.
int operator[](int i) const
Return size of item i.
void minus(int s)
Discard size s.
SizeSetMinusOne(void)
Default constructor.
int p
Position of discarded item.
int total(void) const
Return total size.
int card(void) const
Return cardinality of set (number of entries)
int t
Total size of the set.
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.
int operator[](int i) const
Return size of item i.
int n
Number of size entries in the set.
int * s
Array of sizes (will have more elements)
int card(void) const
Return cardinality of set (number of entries)
Integer view for integer variables.
Definition view.hpp:129
Propagation cost.
Definition core.hpp:486
friend class Space
Definition core.hpp:1068
ModEventDelta med
A set of modification events (used during propagation)
Definition core.hpp:1077
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3505
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1744
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
Bin-packing propagators
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
Finite domain integers.
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
ExecStatus
Definition core.hpp:472
Post propagator for SetVar x
Definition set.hh:773