Generated on Fri Oct 19 11:25:01 2018 for Gecode by doxygen 1.6.3

bin-packing.hh

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Stefano Gualandi <stefano.gualandi@gmail.com>
00008  *
00009  *  Copyright:
00010  *     Stefano Gualandi, 2013
00011  *     Christian Schulte, 2010
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #ifndef __GECODE_INT_BIN_PACKING_HH__
00039 #define __GECODE_INT_BIN_PACKING_HH__
00040 
00041 #include <gecode/int.hh>
00042 
00048 namespace Gecode { namespace Int { namespace BinPacking {
00049 
00053   class Item : public DerivedView<IntView> {
00054   protected:
00055     using DerivedView<IntView>::x;
00057     int s;
00058   public:
00060     Item(void);
00062     Item(IntView b, int s);
00063 
00065     IntView bin(void) const;
00067     void bin(IntView b);
00069     int size(void) const;
00071     void size(int s);
00072 
00074     void update(Space& home, Item& i);
00075   };
00076 
00078   bool operator ==(const Item& i, const Item& j);
00080   bool operator !=(const Item& i, const Item& j);
00081 
00083   bool operator <(const Item& i, const Item& j);
00084 
00085 
00087   class SizeSet {
00088   protected:
00090     int n;
00092     int t;
00094     int* s;
00095   public:
00097     SizeSet(void);
00099     SizeSet(Region& region, int n_max);
00101     void add(int s);
00103     int card(void) const;
00105     int total(void) const;
00107     int operator [](int i) const;
00108   };
00109 
00111   class SizeSetMinusOne : public SizeSet {
00112   protected:
00114     int p;
00115   public:
00117     SizeSetMinusOne(void);
00119     SizeSetMinusOne(Region& region, int n);
00121     void minus(int s);
00123     int card(void) const;
00125     int total(void) const;
00127     int operator [](int i) const;
00128   };
00129 
00130 
00141   class Pack : public Propagator {
00142   protected:
00144     ViewArray<OffsetView> l;
00146     ViewArray<Item> bs;
00148     int t;
00150     Pack(Home home, ViewArray<OffsetView>& l, ViewArray<Item>& bs);
00152     Pack(Space& home, Pack& p);
00153   public:
00155     GECODE_INT_EXPORT
00156     static ExecStatus post(Home home,
00157                            ViewArray<OffsetView>& l, ViewArray<Item>& bs);
00159     template<class SizeSet>
00160     bool nosum(const SizeSet& s, int a, int b, int& ap, int& bp);
00162     template<class SizeSet>
00163     bool nosum(const SizeSet& s, int a, int b);
00165     GECODE_INT_EXPORT
00166     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00168     GECODE_INT_EXPORT
00169     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00171     GECODE_INT_EXPORT
00172     virtual void reschedule(Space& home);
00174     GECODE_INT_EXPORT
00175     virtual Actor* copy(Space& home);
00177     virtual size_t dispose(Space& home);
00178   };
00179 
00180 
00182   class ConflictGraph {
00183   protected:
00185     Home& home;
00187     const IntVarArgs& b;
00189     unsigned int bins;
00191     int nodes(void) const;
00192 
00194     class NodeSet : public Support::RawBitSetBase {
00195     public:
00197       NodeSet(void);
00199       NodeSet(Region& r, int n);
00201       NodeSet(Region& r, int n, const NodeSet& ns);
00203       void allocate(Region& r, int n);
00205       void init(Region& r, int n);
00207       bool in(int i) const;
00209       void incl(int i);
00211       void excl(int i);
00213       void copy(int n, const NodeSet& ns);
00215       void empty(int n);
00222       static bool iwn(NodeSet& iwa, const NodeSet& a,
00223                       NodeSet& iwb, const NodeSet& b,
00224                       const NodeSet& c, int n);
00225     };
00226 
00228     class Node {
00229     public:
00231       NodeSet n;
00233       unsigned int d;
00235       unsigned int w;
00237       Node(void);
00238     };
00240     Node* node;
00241 
00243     class Nodes {
00244     private:
00246       const NodeSet& ns;
00248       unsigned int c;
00249     public:
00251       Nodes(const NodeSet& ns);
00253 
00254 
00255       void operator ++(void);
00257 
00259 
00260 
00261       int operator ()(void) const;
00263     };
00264 
00266 
00267 
00268     class Clique {
00269     public:
00271       NodeSet n;
00273       unsigned int c;
00275       unsigned int w;
00277       Clique(Region& r, int m);
00279       void incl(int i, unsigned int w);
00281       void excl(int i, unsigned int w);
00282     };
00283 
00285     int pivot(const NodeSet& a, const NodeSet& b) const;
00287     GECODE_INT_EXPORT
00288     ExecStatus bk(NodeSet& p, NodeSet& x);
00290 
00292 
00293 
00294     Clique cur;
00296     Clique max;
00298     ExecStatus clique(void);
00300     ExecStatus clique(int i);
00302     ExecStatus clique(int i, int j);
00304     ExecStatus clique(int i, int j, int k);
00306   public:
00308     ConflictGraph(Home& home, Region& r, const IntVarArgs& b,
00309                   int m);
00311     void edge(int i, int j, bool add=true);
00313     bool adjacent(int i, int j) const;
00315     ExecStatus post(void);
00317     IntSet maxclique(void) const;
00319     ~ConflictGraph(void);
00320   };
00321 
00322 }}}
00323 
00324 #include <gecode/int/bin-packing/propagate.hpp>
00325 #include <gecode/int/bin-packing/conflict-graph.hpp>
00326 
00327 #endif
00328 
00329 // STATISTICS: int-prop
00330