bin-packing.hh
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Contributing authors:
* Stefano Gualandi <stefano.gualandi@gmail.com>
*
* Copyright:
* Stefano Gualandi, 2013
* Christian Schulte, 2010
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#ifndef __GECODE_INT_BIN_PACKING_HH__
#define __GECODE_INT_BIN_PACKING_HH__
#include <gecode/int.hh>
namespace Gecode { namespace Int { namespace BinPacking {
class Item : public DerivedView<IntView> {
protected:
using DerivedView<IntView>::x;
int s;
public:
Item(void);
Item(IntView b, int s);
IntView bin(void) const;
void bin(IntView b);
int size(void) const;
void size(int s);
void update(Space& home, Item& i);
};
bool operator ==(const Item& i, const Item& j);
bool operator !=(const Item& i, const Item& j);
bool operator <(const Item& i, const Item& j);
class SizeSet {
protected:
int n;
int t;
int* s;
public:
SizeSet(void);
SizeSet(Region& region, int n_max);
void add(int s);
int card(void) const;
int total(void) const;
int operator [](int i) const;
};
class SizeSetMinusOne : public SizeSet {
protected:
int p;
public:
SizeSetMinusOne(void);
SizeSetMinusOne(Region& region, int n);
void minus(int s);
int card(void) const;
int total(void) const;
int operator [](int i) const;
};
class Pack : public Propagator {
protected:
ViewArray<OffsetView> l;
ViewArray<Item> bs;
int t;
Pack(Home home, ViewArray<OffsetView>& l, ViewArray<Item>& bs);
Pack(Space& home, Pack& p);
public:
GECODE_INT_EXPORT
static ExecStatus post(Home home,
ViewArray<OffsetView>& l, ViewArray<Item>& bs);
template<class SizeSet>
bool nosum(const SizeSet& s, int a, int b, int& ap, int& bp);
template<class SizeSet>
bool nosum(const SizeSet& s, int a, int b);
GECODE_INT_EXPORT
virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
GECODE_INT_EXPORT
virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
GECODE_INT_EXPORT
virtual void reschedule(Space& home);
GECODE_INT_EXPORT
virtual Actor* copy(Space& home);
virtual size_t dispose(Space& home);
};
class ConflictGraph {
protected:
Home& home;
const IntVarArgs& b;
unsigned int bins;
int nodes(void) const;
class NodeSet : public Support::RawBitSetBase {
public:
NodeSet(void);
NodeSet(Region& r, int n);
NodeSet(Region& r, int n, const NodeSet& ns);
void allocate(Region& r, int n);
void init(Region& r, int n);
bool in(int i) const;
void incl(int i);
void excl(int i);
void copy(int n, const NodeSet& ns);
void empty(int n);
static bool iwn(NodeSet& iwa, const NodeSet& a,
NodeSet& iwb, const NodeSet& b,
const NodeSet& c, int n);
};
class Node {
public:
NodeSet n;
unsigned int d;
unsigned int w;
Node(void);
};
Node* node;
class Nodes {
private:
const NodeSet& ns;
unsigned int c;
public:
Nodes(const NodeSet& ns);
void operator ++(void);
int operator ()(void) const;
};
class Clique {
public:
NodeSet n;
unsigned int c;
unsigned int w;
Clique(Region& r, int m);
void incl(int i, unsigned int w);
void excl(int i, unsigned int w);
};
int pivot(const NodeSet& a, const NodeSet& b) const;
GECODE_INT_EXPORT
ExecStatus bk(NodeSet& p, NodeSet& x);
Clique cur;
Clique max;
ExecStatus clique(void);
ExecStatus clique(int i);
ExecStatus clique(int i, int j);
ExecStatus clique(int i, int j, int k);
public:
ConflictGraph(Home& home, Region& r, const IntVarArgs& b,
int m);
void edge(int i, int j, bool add=true);
bool adjacent(int i, int j) const;
ExecStatus post(void);
IntSet maxclique(void) const;
~ConflictGraph(void);
};
}}}
#include <gecode/int/bin-packing/propagate.hpp>
#include <gecode/int/bin-packing/conflict-graph.hpp>
#endif
// STATISTICS: int-prop
propagate.hpp
Gecode::ActorLink::Actor
friend class Actor
Definition core.hpp:590
Gecode::DerivedView< IntView >::x
IntView x
Definition view.hpp:238
Gecode::DerivedView< IntView >::DerivedView
DerivedView(void)
Definition view.hpp:584
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntVarArgs
Passing integer variables.
Definition int.hh:656
Gecode::Int::BinPacking::ConflictGraph::Clique
Clique information.
Definition bin-packing.hh:268
Gecode::Int::BinPacking::ConflictGraph::Clique::Clique
Clique(Region &r, int m)
Constructor for m nodes.
Definition conflict-graph.hpp:127
Gecode::Int::BinPacking::ConflictGraph::Clique::excl
void excl(int i, unsigned int w)
Exclude node i with weight w.
Definition conflict-graph.hpp:134
Gecode::Int::BinPacking::ConflictGraph::Clique::n
NodeSet n
Nodes in the clique.
Definition bin-packing.hh:271
Gecode::Int::BinPacking::ConflictGraph::Clique::incl
void incl(int i, unsigned int w)
Include node i with weight w.
Definition conflict-graph.hpp:130
Gecode::Int::BinPacking::ConflictGraph::Clique::c
unsigned int c
Cardinality of clique.
Definition bin-packing.hh:273
Gecode::Int::BinPacking::ConflictGraph::Clique::w
unsigned int w
Weight of clique.
Definition bin-packing.hh:275
Gecode::Int::BinPacking::ConflictGraph::NodeSet
Sets of graph nodes.
Definition bin-packing.hh:194
Gecode::Int::BinPacking::ConflictGraph::NodeSet::empty
void empty(int n)
Clear the whole node set for n nodes.
Definition conflict-graph.hpp:80
Gecode::Int::BinPacking::ConflictGraph::NodeSet::incl
void incl(int i)
Include node i.
Definition conflict-graph.hpp:68
Gecode::Int::BinPacking::ConflictGraph::NodeSet::NodeSet
NodeSet(void)
Keep uninitialized.
Definition conflict-graph.hpp:47
Gecode::Int::BinPacking::ConflictGraph::NodeSet::iwn
static bool iwn(NodeSet &iwa, const NodeSet &a, NodeSet &iwb, const NodeSet &b, const NodeSet &c, int n)
Definition conflict-graph.hpp:84
Gecode::Int::BinPacking::ConflictGraph::NodeSet::init
void init(Region &r, int n)
Initialize node set for n nodes.
Definition conflict-graph.hpp:60
Gecode::Int::BinPacking::ConflictGraph::NodeSet::in
bool in(int i) const
Test whether node i is included.
Definition conflict-graph.hpp:64
Gecode::Int::BinPacking::ConflictGraph::NodeSet::allocate
void allocate(Region &r, int n)
Allocate node set for n nodes.
Definition conflict-graph.hpp:56
Gecode::Int::BinPacking::ConflictGraph::NodeSet::copy
void copy(int n, const NodeSet &ns)
Copy elements from node set ns with n nodes.
Definition conflict-graph.hpp:76
Gecode::Int::BinPacking::ConflictGraph::NodeSet::excl
void excl(int i)
Exclude node i.
Definition conflict-graph.hpp:72
Gecode::Int::BinPacking::ConflictGraph::Node
Class for node in graph.
Definition bin-packing.hh:228
Gecode::Int::BinPacking::ConflictGraph::Node::n
NodeSet n
The neighbors.
Definition bin-packing.hh:231
Gecode::Int::BinPacking::ConflictGraph::Node::w
unsigned int w
Weight (initialized with degree before graph is reduced).
Definition bin-packing.hh:235
Gecode::Int::BinPacking::ConflictGraph::Node::Node
Node(void)
Default constructor.
Definition conflict-graph.hpp:112
Gecode::Int::BinPacking::ConflictGraph::Node::d
unsigned int d
Degree.
Definition bin-packing.hh:233
Gecode::Int::BinPacking::ConflictGraph::Nodes::operator++
void operator++(void)
Move iterator to next node (if possible).
Definition conflict-graph.hpp:118
Gecode::Int::BinPacking::ConflictGraph::Nodes::Nodes
Nodes(const NodeSet &ns)
Initialize for nodes in ns.
Definition conflict-graph.hpp:115
Gecode::Int::BinPacking::ConflictGraph::Nodes::operator()
int operator()(void) const
Return current node.
Definition conflict-graph.hpp:122
Gecode::Int::BinPacking::ConflictGraph::cur
Clique cur
Current clique.
Definition bin-packing.hh:294
Gecode::Int::BinPacking::ConflictGraph::clique
ExecStatus clique(void)
Report the current clique.
Definition conflict-graph.hpp:201
Gecode::Int::BinPacking::ConflictGraph::nodes
int nodes(void) const
Return number of nodes.
Definition conflict-graph.hpp:42
Gecode::Int::BinPacking::ConflictGraph::post
ExecStatus post(void)
Post additional constraints.
Definition conflict-graph.hpp:256
Gecode::Int::BinPacking::ConflictGraph::ConflictGraph
ConflictGraph(Home &home, Region &r, const IntVarArgs &b, int m)
Initialize graph.
Definition conflict-graph.hpp:139
Gecode::Int::BinPacking::ConflictGraph::home
Home & home
Home space.
Definition bin-packing.hh:185
Gecode::Int::BinPacking::ConflictGraph::pivot
int pivot(const NodeSet &a, const NodeSet &b) const
Find a pivot node with maximal degree from a or b.
Definition conflict-graph.hpp:175
Gecode::Int::BinPacking::ConflictGraph::~ConflictGraph
~ConflictGraph(void)
Destructor.
Definition conflict-graph.hpp:152
Gecode::Int::BinPacking::ConflictGraph::adjacent
bool adjacent(int i, int j) const
Test whether nodes i and j are adjacent.
Definition conflict-graph.hpp:169
Gecode::Int::BinPacking::ConflictGraph::node
Node * node
The nodes in the graph.
Definition bin-packing.hh:240
Gecode::Int::BinPacking::ConflictGraph::bk
ExecStatus bk(NodeSet &p, NodeSet &x)
Run Bosch-Kerbron algorithm for finding max cliques.
Definition conflict-graph.cpp:39
Gecode::Int::BinPacking::ConflictGraph::bins
unsigned int bins
Number of bins.
Definition bin-packing.hh:189
Gecode::Int::BinPacking::ConflictGraph::edge
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).
Definition conflict-graph.hpp:156
Gecode::Int::BinPacking::ConflictGraph::b
const IntVarArgs & b
Bin variables.
Definition bin-packing.hh:187
Gecode::Int::BinPacking::ConflictGraph::max
Clique max
Largest clique so far.
Definition bin-packing.hh:296
Gecode::Int::BinPacking::ConflictGraph::maxclique
IntSet maxclique(void) const
Return maximal clique found.
Definition conflict-graph.hpp:330
Gecode::Int::BinPacking::Item
Item combining bin and size information.
Definition bin-packing.hh:53
Gecode::Int::BinPacking::Item::bin
IntView bin(void) const
Return bin of item.
Definition propagate.hpp:48
Gecode::Int::BinPacking::Item::update
void update(Space &home, Item &i)
Update item during cloning.
Definition propagate.hpp:65
Gecode::Int::BinPacking::Item::s
int s
Size of item.
Definition bin-packing.hh:57
Gecode::Int::BinPacking::Item::Item
Item(void)
Default constructor.
Definition propagate.hpp:41
Gecode::Int::BinPacking::Item::size
int size(void) const
Return size of item.
Definition propagate.hpp:56
Gecode::Int::BinPacking::Pack::l
ViewArray< OffsetView > l
Views for load of bins.
Definition bin-packing.hh:144
Gecode::Int::BinPacking::Pack::post
static ExecStatus post(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Post propagator for loads l and items bs.
Definition propagate.cpp:360
Gecode::Int::BinPacking::Pack::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition propagate.cpp:113
Gecode::Int::BinPacking::Pack::bs
ViewArray< Item > bs
Items with bin and size.
Definition bin-packing.hh:146
Gecode::Int::BinPacking::Pack::Pack
Pack(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Constructor for posting.
Definition propagate.hpp:150
Gecode::Int::BinPacking::Pack::t
int t
Total size of all items.
Definition bin-packing.hh:148
Gecode::Int::BinPacking::Pack::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition propagate.cpp:55
Gecode::Int::BinPacking::Pack::nosum
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
Gecode::Int::BinPacking::Pack::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition propagate.cpp:44
Gecode::Int::BinPacking::Pack::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition propagate.cpp:49
Gecode::Int::BinPacking::Pack::dispose
virtual size_t dispose(Space &home)
Destructor.
Definition propagate.hpp:166
Gecode::Int::BinPacking::SizeSetMinusOne::operator[]
int operator[](int i) const
Return size of item i.
Definition propagate.hpp:137
Gecode::Int::BinPacking::SizeSetMinusOne::minus
void minus(int s)
Discard size s.
Definition propagate.hpp:119
Gecode::Int::BinPacking::SizeSetMinusOne::SizeSetMinusOne
SizeSetMinusOne(void)
Default constructor.
Definition propagate.hpp:114
Gecode::Int::BinPacking::SizeSetMinusOne::p
int p
Position of discarded item.
Definition bin-packing.hh:114
Gecode::Int::BinPacking::SizeSetMinusOne::total
int total(void) const
Return total size.
Definition propagate.hpp:132
Gecode::Int::BinPacking::SizeSetMinusOne::card
int card(void) const
Return cardinality of set (number of entries).
Definition propagate.hpp:127
Gecode::Int::BinPacking::SizeSet
Size sets.
Definition bin-packing.hh:87
Gecode::Int::BinPacking::SizeSet::t
int t
Total size of the set.
Definition bin-packing.hh:92
Gecode::Int::BinPacking::SizeSet::SizeSet
SizeSet(void)
Default constructor.
Definition propagate.hpp:92
Gecode::Int::BinPacking::SizeSet::add
void add(int s)
Add new size s.
Definition propagate.hpp:97
Gecode::Int::BinPacking::SizeSet::total
int total(void) const
Return total size.
Definition propagate.hpp:105
Gecode::Int::BinPacking::SizeSet::operator[]
int operator[](int i) const
Return size of item i.
Definition propagate.hpp:109
Gecode::Int::BinPacking::SizeSet::n
int n
Number of size entries in the set.
Definition bin-packing.hh:90
Gecode::Int::BinPacking::SizeSet::s
int * s
Array of sizes (will have more elements).
Definition bin-packing.hh:94
Gecode::Int::BinPacking::SizeSet::card
int card(void) const
Return cardinality of set (number of entries).
Definition propagate.hpp:101
Gecode::Int::IntView
Integer view for integer variables.
Definition view.hpp:129
Gecode::PropCost
Propagation cost.
Definition core.hpp:486
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::med
ModEventDelta med
A set of modification events (used during propagation).
Definition core.hpp:1075
Gecode::Propagator::Propagator
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3498
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Support::RawBitSetBase
Basic bitset support (without stored size information).
Definition bitset-base.hpp:137
Gecode::ViewArray
View arrays.
Definition array.hpp:253
conflict-graph.hpp
int.hh
GECODE_INT_EXPORT
#define GECODE_INT_EXPORT
Definition int.hh:81
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
Gecode::Int::BinPacking
Bin-packing propagators
Gecode::Int::BinPacking::operator<
bool operator<(const Item &i, const Item &j)
Order, also for sorting according to size.
Definition propagate.hpp:82
Gecode::Int::BinPacking::operator!=
bool operator!=(const Item &i, const Item &j)
Whether two items are not the same.
Definition propagate.hpp:76
Gecode::Int::BinPacking::operator==
bool operator==(const Item &i, const Item &j)
Whether two items are the same.
Definition propagate.hpp:72
Gecode::Int
Finite domain integers.
Gecode
Gecode toplevel namespace
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472