Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.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
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.
int n
Number of negative literals for node type.
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
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.
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.
Graph containing conflict information.
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
Bin-packing propagator.
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.
Size sets with one element discarded.
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
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